Verschachtelte Schönheit

Wöchentliche Herausforderung 300

Jede Woche verschickt Mohammad S. Anwar die Weekly Challenge, eine Chance für uns alle, Lösungen für zwei wöchentliche Aufgaben zu finden. Meine Lösungen werden zunächst in Python geschrieben und dann in Perl konvertiert. Es ist eine großartige Möglichkeit für uns alle, etwas Programmieren zu üben.

Herausforderung, meine Lösungen

Da dies die dreihundertste Herausforderung ist, möchte ich Mohammad persönlich für all die Arbeit danken, die er jede Woche im Namen aller im Team PWC leistet.

Aufgabe 1: Schönes Arrangement

Aufgabe

Sie erhalten eine positive Ganzzahl, $int.

Schreiben Sie ein Skript, um die Anzahl der schönen Arrangements zurückzugeben, die Sie erstellen können.

Eine Permutation von n ganzen Zahlen, 1-indiziert, gilt als schöne Anordnung, wenn für jedes i (1 <= i <= n) eine der folgenden Aussagen zutrifft:

1. perm[i] ist durch i teilbar
2. i ist durch perm[i] teilbar

Meine Lösung

Für diese Aufgabe verwende ich die Permutationsfunktion aus dem itertool-Modul, um alle Permutationen durchzuarbeiten.

Dann geht es nur noch darum, festzustellen, ob diese Permutation die angegebenen Kriterien erfüllt. Wenn nicht, gehe ich zur nächsten Permutation über. Wenn ja, füge ich eins zur Zählvariablen hinzu.

def beautiful_arrangement(n: list) -> str:
    count = 0

    for p in permutations(range(1, n+1)):
        for i in range(n):
            if p[i] % (i+1) != 0 and (i+1) % p[i] != 0:
                break
        else:
            count += 1

    return count




</p>
<p>Möglicherweise gibt es eine effizientere Methode zur Berechnung der Ergebnisse, die ohne rohe Gewalt auskommt. Mein Code würde bei größeren Zahlen sehr ineffizient werden. Ich habe keine Zeit damit verbracht, dies zu untersuchen.</p>

<h3>
  
  
  Beispiele
</h3>



<pre class="brush:php;toolbar:false">$ ./ch-1.py 1
1

$ ./ch-1.py 2
2

$ ./ch-1.py 10
700

Aufgabe 2: Verschachteltes Array

Aufgabe

Sie erhalten ein Array von Ganzzahlen, @ints der Länge n, das Permutationen der Zahlen im Bereich [0, n - 1] enthält.

Schreiben Sie ein Skript, um eine Menge zu erstellen, set[i] = ints[i], ints[ints[i]], ints[ints[ints[i]]], ..., unterliegt den folgenden Regeln:

1. Das erste Element in set[i] beginnt mit der Auswahl der Elemente ints[i].
2. Das nächste Element in set[i] sollte ints[ints[i]] sein, dann ints[ints[ints[i]]] und so weiter.
3. Wir hören mit dem Hinzufügen auf, unmittelbar bevor ein doppeltes Element in set[i] auftritt.

Meine Lösung

Das ist relativ einfach. Ich beginne mit einer Variablen namens longest_set, die auf 0 gesetzt ist. Anschließend iteriere ich durch jede Startposition und setze die this_set-Liste als erstes Element der Menge (d. h. ints[i]). Ich füge diesem Satz immer wieder hinzu, während ints[this_set[-1]] nicht in der this_set-Liste erscheint. Nachdem dies erledigt ist, vergleiche ich die Länge der this_set-Liste mit dem longest_set-Wert. Wenn er größer ist, aktualisiere ich den longest_set-Wert.

def nested_array(ints: list) -> int:
    longest_set = 0

    for start in range(len(ints)):
        this_set = [ints[start]]

        while ints[this_set[-1]] not in this_set:
            this_set.append(ints[this_set[-1]])

        if longest_set < len(this_set):
            longest_set = len(this_set)

    return longest_set

Beispiele

$ ./ch-2.py 5 4 0 3 1 6 2
4

$ ./ch-2.py 0 1 2
1

$ ./ch-2.py 1 2 0 4 5 2
5

Das obige ist der detaillierte Inhalt vonVerschachtelte Schönheit. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!