[PYTHON] Ich habe versucht, DP mit Fibonacci-Sequenz zu studieren

Da ich Zeit hatte, begann ich an der dynamischen Planungsmethode (DP) zu arbeiten, um 100 Runden später mit AtCoder zu beginnen.

TL;DR Ich habe gerade den Teil der Fibonacci-Sequenz in Dynamic Planning in Programming Contest in Python implementiert.

DP Führen Sie nicht zweimal dieselbe Suche durch Speichern Sie das Ergebnis nach der Berechnung und verwenden Sie es erneut

Fibonacci-Folge

Die "Fibonacci-Sequenz" ist eine Sequenz, die "die beiden vorherigen Nummern addiert, um die nächste Nummer zu erhalten". Die erste und die zweite Zahl sind jedoch beide 1.

• Die Werte in den Punkten 0 bis 21 lauten wie folgt:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …

 > - Die Fibonacci-Sequenz (Fn) wird durch den folgenden allmählichen Ausdruck definiert:

> ```math
F0 = 0\\
F1 = 1\\
F_{n+2} = F_n + F_{n+1}\,(n ≥ 0)\\

Studyplus Wikipedia

Bearbeitungszeitmessung

Ich werde eine Vermutungsfunktion einführen, die ich häufig beim Messen der Verarbeitungszeit verwende! Vereinfachte die von Kaggle-Meister Arai eingeführte Timer-Funktion (Ich bin froh, dass ich gekaggt habe, nur um das zu wissen ...)

import time
from contextlib import contextmanager


@contextmanager
def timer():
    t0 = time.time()
    msg = "start"
    print(msg)
    yield
    msg = f"done in {time.time() - t0:.2f} s"
    print(msg)

Kaggle Code Heritage

Hauptthema

Berechnen Sie die Fibonacci-Zahl normal

def fib(n: int):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Memosuche (rückwirkende Funktionsnotiz)

def fib_memo(n: int):
    global done
    global memo
    if n == 0: return 0
    if n == 1: return 1

    if done[n]:
        return memo[n]

    done[n] = True
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

Dynamische Planungsmethode (schrittweiser Ausdruck + Schleife)

def fib_loop(n: int):
    global memo
    memo[0] = 0
    memo[1] = 1

    for i in range(2, n+1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]

Lauf

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("method", help="Select to solve with which fibonacci method")
    parser.add_argument("max_num", help="Set max number")
    args = parser.parse_args()

    n = int(args.max_num)
    done = [False] * (n + 1)
    memo = [0] * (n + 1)
    with timer():
        print(eval(args.method)(n))

Befehl

python fibonacci.py fib_memo 1000

Verarbeitungsgeschwindigkeit

Von den oben genannten drei war die dynamische Planungsmethode die schnellste, gefolgt von der Memosuche, und die langsamste war bei der normalen Berechnung der Fibonacci-Zahl.

Wie in Dynamische Planungsmethode im Programmierwettbewerb beschrieben, scheint der Rechenaufwand exponentielle Zeit oder Pseudopolypolysezeit zu benötigen.

Dynamische Planungsmethode<Memosuche<<<<<<<<<<<<<<<<<<Fibonacci-Nummer normalerweise

• Wenn n = 30000
• Dynamische Planungsmethode: 0,04 s --Memo-Suche: 0,06 s
• Normalerweise Fibonacci: Es endet nicht (es braucht viel Zeit, selbst mit n = 100)

Einzelheiten finden Sie bei Github