Einführung

Dieser Artikel ist Kenchons Buch, das viele Erklärungen zur wettbewerbsfähigen Programmierung enthält. ** Trainieren Sie Ihre Fähigkeiten zur Problemlösung! Algorithmen und Datenstrukturen（けんちょんさん本）**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。

Auf dieser Seite stellen wir den Inhalt von Kapitel 4 vor! Bitte vergib mir, wenn es irgendwelche Fehler gibt.

Auf den folgenden Seiten finden Sie Links zu anderen Kapiteln. [Inhaltsverzeichnis] https://qiita.com/KevinST/items/002676619a583754bf76

code4.1 Rekursive Funktion zur Berechnung der Summe von 1 bis N.

Grundlegende Wiederholung.

`code4-1.py`


def func(N):
    if N == 0:
        return 0
    return N + func(n-1)

Da nur der Funktionsteil erstellt wird, erfolgt keine Ein- / Ausgabe.

code4.2 Rekursive Funktion zur Berechnung der Summe von 1 bis N.

Dies ist ein Beispiel für die Verwendung von Code4.1 (N = 5).

`code4-2.py`


#Python hat eine begrenzte Wiederholung (1000-mal usw., abhängig von der Umgebung)
#Ändern Sie dies auf einen ausreichend großen Wert (diesmal 10 bis 9 Potenz)
import sys
sys.setrecursionlimit(10**9)

def func(N):
    #Berichten Sie, dass Sie eine rekursive Funktion aufgerufen haben
    print("func({})Namens".format(N))

    #Basisfall
    if N == 0:
        return 0

    #Wenn nicht der Basisfall, fragen Sie rekursiv nach einer Antwort
    result = N + func(N-1)
    print("{}Fassen Sie zusammen= {}".format(N, result))
    return result

func(5)

[Ausgabebeispiel] Genannt func (5) Genannt func (4) Genannt func (3) Genannt func (2) Genannt func (1) Genannt func (0) Summiere bis 1 = 1 Summe bis 2 = 3 Summe bis 3 = 6 Summe bis 4 = 10 Summe bis 5 = 15

Als Methode erhöhen wir die Anzahl der rekursiven Obergrenzen. In Python wird die rekursive Obergrenze häufig standardmäßig auf das 1000-fache festgelegt Ich denke, es wäre gut, dies zu ändern, wenn bei Wettkampfprofis Wiederholungen auftreten. (In diesem Fall nicht notwendig, aber nur für den Fall)

Wenn es danach nicht notwendig ist, lassen Sie es weg.

code4.3 Rekursive Funktion, die den rekursiven Aufruf nicht stoppt

`code4-3.py`


#Achtung! Bitte tun Sie dies auf eigenes Risiko
def func(N):
    if N == 0:
        return 0
    return N + func(N+1)

An TLE besteht kein Zweifel.

code4.4 Finden Sie die maximale Anzahl von Versprechungen durch die Methode der gegenseitigen Teilung von Euklidisch

Es ist eine bekannte euklidische Methode der gegenseitigen Teilung.

** F: Was ist die maximale Verpflichtung für 51 und 15? ** **.

51 ÷ 15 = 3 zu viel 6
15 ÷ 6 = 2 zu viel 3 3,6 ÷ 3 = 2 kleiner als 0 A: ３！！ Das ist der eine.

Schreiben wir es mit einer rekursiven Funktion.

`code4-4.py`


def GCD(m, n):
    #Basisfall
    if n == 0:
        return m

    #Rekursiver Aufruf
    return GCD(n, m % n)

print(GCD(51, 15))  #3 wird ausgegeben
print(GCD(15, 51))  #3 wird ausgegeben

[Ausgabebeispiel] 3 3

Der Berechnungsbetrag beträgt übrigens $ O (log (n)) $. GCD ist schnell! !! !! !!

code4.5 Rekursive Funktion zum Finden der Fibonacci-Sequenz

Dies ist auch eine vertraute. 1 1 2 3 5 8 13 21 34 ...

`code4-5.py`


def fibo(N):
    #Basisfall
    if N == 0:
        return 0
    elif N == 1:
        return 1

    #Rekursiver Aufruf
    return fibo(N-1) + fibo(N-2)

print(fibo(5))

[Ausgabebeispiel] 5

Obwohl es nicht im Original ist, habe ich auch eine Ausgabe hinzugefügt, um den Vorgang zu überprüfen. Lassen Sie uns die detaillierte Operation mit dem folgenden Code 4.6 überprüfen.

code4.6 Vollständige Suchmethode unter Verwendung von Bits für das Teilsummenproblem

Dies ist ein konkretes Anwendungsbeispiel für Code4.5. Eine Ausgabe ist enthalten, damit Sie den internen Status überprüfen können.

`code4-6.py`


def fibo(N):
    #Berichten Sie, dass Sie eine rekursive Funktion aufgerufen haben
    print("fibo({})Namens".format(N))

    #Basisfall
    if N == 0:
        return 0
    elif N == 1:
        return 1

    #Bitten Sie rekursiv um eine Antwort und Ausgabe
    result = fibo(N-1) + fibo(N-2)
    print("{}Artikel= {}".format(N, result))

    return result

fibo(6)

[Ausgabebeispiel] Fibo genannt (6) Fibo genannt (5) Fibo genannt (4) Fibo genannt (3) Fibo genannt (2) Fibo genannt (1) Fibo genannt (0) 2 Elemente = 1 Fibo genannt (1) 3 Elemente = 2 Fibo genannt (2) Fibo genannt (1) Fibo genannt (0) 2 Elemente = 1 4 Artikel = 3 Fibo genannt (3) Fibo genannt (2) Fibo genannt (1) Fibo genannt (0) 2 Elemente = 1 Fibo genannt (1) 3 Elemente = 2 5 Artikel = 5 Fibo genannt (4) Fibo genannt (3) Fibo genannt (2) Fibo genannt (1) Fibo genannt (0) 2 Elemente = 1 Fibo genannt (1) 3 Elemente = 2 Fibo genannt (2) Fibo genannt (1) Fibo genannt (0) 2 Elemente = 1 4 Artikel = 3 6 Artikel = 8

Trotz der relativ geringen Anzahl von N = 6 gibt es viele Funktionsaufrufe. Der folgende Code (Code4.8) versucht dies zu verbessern.

code4.7 Finden Sie die Fibonacci-Zahlenfolge, indem Sie mit einer for-Anweisung iterieren

Es ist ein Versuch zu sehen, was passiert, wenn wir die Wiederholung einmal verlassen und sie mit einer for-Anweisung und einem Array implementieren.

`code4-7.py`


F = [None] * 50
F[0], F[1] = 0, 1

for N in range(2, 50):
    F[N] = F[N-1] + F[N-2]
    print("{}Artikel: {}".format(N, F[N]))

[Ausgabebeispiel] 2 Artikel: 1 3 Artikel: 2 4 Artikel: 3 5 Artikel: 5 6 Artikel: 8 7 Artikel: 13 8 Artikel: 21 9 Artikel: 34 10 Artikel: 55 11 Artikel: 89 12 Artikel: 144 13 Artikel: 233 14 Artikel: 377 15 Artikel: 610 16 Artikel: 987 17 Artikel: 1597 18 Artikel: 2584 19 Artikel: 4181 20 Artikel: 6765 21 Artikel: 10946 22 Artikel: 17711 23 Artikel: 28657 24 Artikel: 46368 25 Artikel: 75025 26 Artikel: 121393 27 Artikel: 196418 28 Artikel: 317811 29 Artikel: 514229 30 Artikel: 832040 31 Artikel: 1346269 32 Artikel: 2178309 33 Artikel: 3524578 34 Artikel: 5702887 35 Artikel: 9227465 36 Artikel: 14930352 37 Artikel: 24157817 38 Artikel: 39088169 39 Artikel: 63245986 40 Artikel: 102334155 41 Artikel: 165580141 42 Artikel: 267914296 43 Artikel: 433494437 44 Artikel: 701408733 45 Artikel: 1134903170 46 Artikel: 1836311903 47 Artikel: 2971215073 48 Artikel: 4807526976 49 Artikel: 7778742049

Es kann mit einem Berechnungsbetrag von $ O (N) $ implementiert werden.

code4.8 Notieren Sie sich die rekursive Funktion, die die Fibonacci-Zahlenfolge findet

Wenn Sie Arrays gut verwenden, können Sie dieselben Berechnungen überspringen und Ihr Programm beschleunigen. Lassen Sie uns dies in die Wiederholung einbeziehen (= Memo).

`code4-8.py`


#fibo[N]Ein Array, um das Ergebnis von zu notieren
memo = [-1] * 50

def fibo(N):
    #Basisfall
    if N == 0:
        return 0
    elif N == 1:
        return 1

    #Überprüfen Sie die Notizen
    if memo[N] != -1:
        return memo[N]

    #Rekursiver Anruf beim Aufschreiben der Antwort
    memo[N] = fibo(N-1) + fibo(N-2)
    return memo[N]

fibo(49)
for N in range(2, 50):
    print("{}Artikel: {}".format(N, memo[N]))

[Ausgabebeispiel] 2 Artikel: 1 3 Artikel: 2 4 Artikel: 3 5 Artikel: 5 6 Artikel: 8 7 Artikel: 13 8 Artikel: 21 9 Artikel: 34 10 Artikel: 55 11 Artikel: 89 12 Artikel: 144 13 Artikel: 233 14 Artikel: 377 15 Artikel: 610 16 Artikel: 987 17 Artikel: 1597 18 Artikel: 2584 19 Artikel: 4181 20 Artikel: 6765 21 Artikel: 10946 22 Artikel: 17711 23 Artikel: 28657 24 Artikel: 46368 25 Artikel: 75025 26 Artikel: 121393 27 Artikel: 196418 28 Artikel: 317811 29 Artikel: 514229 30 Artikel: 832040 31 Artikel: 1346269 32 Artikel: 2178309 33 Artikel: 3524578 34 Artikel: 5702887 35 Artikel: 9227465 36 Artikel: 14930352 37 Artikel: 24157817 38 Artikel: 39088169 39 Artikel: 63245986 40 Artikel: 102334155 41 Artikel: 165580141 42 Artikel: 267914296 43 Artikel: 433494437 44 Artikel: 701408733 45 Artikel: 1134903170 46 Artikel: 1836311903 47 Artikel: 2971215073 48 Artikel: 4807526976 49 Artikel: 7778742049

Dies könnte auch mit dem Berechnungsbetrag $ O (N) $ implementiert werden.

code4.9 Lösen Sie das Teilsummenproblem mit einer vollständigen Suche mithilfe einer rekursiven Funktion

Lösen Sie das gleiche Problem wie Code 3.6 im vorherigen Kapitel mit einer rekursiven Funktion. Vergessen Sie Memos einmal und implementieren Sie sie mit einfachem Rekursiv.

`code4-9.py`


def func(i, w, a):
    #Basisfall
    if i == 0:
        if w == 0:
            return True
        else:
            return False

    #a[i-1]Wenn Sie nicht wählen
    if func(i-1, w, a):
        return True

    #a[i-1]Bei der Wahl
    if func(i-1, w-a[i-1], a):
        return True

    #Wenn beide falsch sind
    return False

N, W = map(int, input().split())
a = list(map(int, input().split()))
if func(N, W, a):
    print("Yes")
else:
    print("No")

【Eingabebeispiel】 4 10 1 9 100 200 [Ausgabebeispiel] Yes

Dieser Code ist ein Rechenbetrag $ O (2 ^ N) $. (Siehe Kenchons Buch für Details)

Wenn Sie interessiert sind, lassen Sie uns dies auch notieren! (Kapitelende Problem 4.6)

Klicken Sie hier für Kapitel 5 (Hinzufügen, sobald es abgeschlossen ist)

[Kenchon-Buch zu Python] -Kapitel 4- "Trainieren Sie Ihre Fähigkeiten zur Problemlösung! Algorithmen und Datenstrukturen" Ich habe den veröffentlichten Code in Python umgeschrieben!

Einführung

code4.1 Rekursive Funktion zur Berechnung der Summe von 1 bis N.

code4-1.py

code4.2 Rekursive Funktion zur Berechnung der Summe von 1 bis N.

code4-2.py

code4.3 Rekursive Funktion, die den rekursiven Aufruf nicht stoppt

code4-3.py