Bardzo często na różnych olimpiadach, zadania wydają się być takie, co, jak myślę na pierwszy rzut oka, można rozwiązać z prostym rozwojem. Ale jeśli obliczymy liczbę możliwych opcji, jest natychmiast przekonany o nieskuteczności tego podejścia: na przykład prosta funkcja rekurencyjna poniżej będzie konsumować znaczne zasoby na 30. z numeru Fibonacciego, podczas gdy na olimpiadzie, czas rozwiązania jest często ograniczony do 1-5 sekund.
Int fibo (int n) (jeśli (n \u003d\u003d 1 || n \u003d\u003d 2) (zwrot 1;) inaczej (Fibo powrotu (N - 1) + Fibo (N - 2);)))))))
Pomyślmy o tym, dlaczego się dzieje. Na przykład, aby obliczyć FIBO (30), najpierw obliczamy FIBO (29) i FIBO (28). Ale jednocześnie nasz program "zapomina", który Fibo (28) my już obliczone Podczas wyszukiwania FiBo (29).
Głównym błędem tego podejścia "w czole" jest to, że te same wartości argumentów funkcyjnych są obliczane wielokrotnie - i jest to wystarczające operacje intensywne. Metoda programowania dynamicznego pomoże nam pozbyć się dynamicznych obliczeń - jest to recepcja, przy użyciu zadania, zadanie jest podzielone na powtarzające się podtask, z których każdy jest rozwiązany tylko 1 raz - to znacznie poprawia wydajność programu . Ta metoda jest szczegółowo opisana, istnieją również przykłady rozwiązywania innych zadań.
Najprostszą opcją poprawy naszej funkcji jest zapamiętanie, jakie wartości, które już obliczyliśmy. Aby to zrobić, musisz wprowadzić dodatkową tablicę, która będzie służyć jako "pamięć podręczną" dla naszych obliczeń: Przed obliczeniem nowej wartości sprawdzimy, czy został obliczony wcześniej. Jeśli obliczyli, weźmiemy gotową wartość z tablicy, a jeśli nie jest obliczony - będziesz musiał wziąć pod uwagę na podstawie poprzednich i zapamiętanych na przyszłość:
Int Cache; int fibo (int n) (jeśli (nie pamięć podręczna [n] \u003d\u003d 0) (jeśli (n \u003d\u003d 1 || n \u003d\u003d 2) (pamięć podręczna [n] \u003d 1;) inaczej (pamięć podręczna [n] \u003d fibo (n - 1) + Fibo (N - 2);)) Zwróć pamięć podręczną [n];)
Ponieważ w tym zadaniu obliczymy wartość N-umysłu, będziemy zagwarantować zagwarantowane (N-1) -e, nie będzie trudne do przepisania formuły do \u200b\u200bformuły iteracyjnej - po prostu wypełnimy naszą tablicę w Wiersz, aż dojdzie do żądanej komórki:
<= n; i++) { cache[i] = cache + cache; } cout << cache;
Teraz możemy zauważyć, że gdy obliczymy wartość F (N), wartość F (N-3) jest już gwarantowana nigdy nie potrzebuje. Oznacza to, że wystarczy przechowywać tylko dwie wartości w pamięci - F (N - 1) i F (N-2). Ponadto, gdy tylko obliczymy F (n), przechowywanie F (N-2) traci jakiekolwiek znaczenie. Spróbujmy napisać te refleksje w formie kodu:
// Dwie poprzednie wartości: int Cache1 \u003d 1; int Cache2 \u003d 1; // Nowa wartość int Cache3; dla (int i \u003d 2; ja<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 => Przez iteracja straci znaczenie Cache2, tj. Powinien być Cache1 // innymi słowy, Cache1 - F (N-2), Cache2 - F (N - 1), Cache3 - F (N). // Niech N \u003d N + 1 (liczba, którą obliczymy w następnej iteracji). Następnie N-2 \u003d N-3, N-1 \u003d N-2, N \u003d N-1. // zgodnie z nowymi rzeczywistości przepisujemy wartości naszych zmiennych: CALE1 \u003d CALE2; Cache2 \u003d Cache3; ) Cout.<< cache3;
Doświadczony programista jest jasny, że kod jest wyższy, ogólnie rzecz biorąc, nonsens, ponieważ Cache3 nigdy nie jest używany (jest natychmiast nagrany w Cache2), a można przepisać całą iterację przy użyciu tylko jednego wyrażenia:
Cache \u003d 1; cache \u003d 1; dla (int i \u003d 2; ja<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;
Dla tych, którzy nie mogą zrozumieć, jak magia współpracuje z pozostałością z podziału, lub po prostu chce zobaczyć bardziej nieuwidualną formułę, istnieje inne rozwiązanie:
Int x \u003d 1; int y \u003d 1; dla (int i \u003d 2; ja< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;
Spróbuj śledzić wykonanie tego programu: Będziesz pewien, że poprawisz algorytm.
Str.s. Ogólnie rzecz biorąc, istnieje pojedyncza formuła obliczania dowolnej liczby fibonacci, która nie wymaga żadnych iteracji ani rekurencji:
Const podwójna sqrt5 \u003d sqrt (5); Const podwójny phi \u003d (SQRT5 + 1) / 2; Int Fibo (int N) (INT zwrotny (pow (PHI, N) / SQRT5 + 0,5);)
Ale, jak myślisz, że połów jest taka, że \u200b\u200bcena obliczania stopni liczb neuropalnych jest dość duża, podobnie jak ich błąd.
Programiści liczby Fibonacci powinni już rządzić. Przykłady ich obliczeń są używane wszędzie. Wszystko od tego, że te liczby zapewniają najprostszy przykład rekurencji. I są dobrym przykładem dynamicznego programowania. Ale czy konieczne jest ich obliczenie ich w prawdziwym projekcie? Nie rób. Ani rekursja, ani dynamiczne programowanie są idealnymi opcjami. I nie zamknięta formuła, która wykorzystuje liczby pływających punktów. Teraz powiem ci, jak poprawnie. Ale najpierw przejdź przez wszystkie znane rozwiązania.Kod jest przeznaczony do Pythona 3, chociaż musi iść na Pythona 2.
Zacznij od - przypominam o definicji:
F n \u003d f n-1 + f n-2
I f 1 \u003d f 2 \u003d 1.
Zamknięta formuła
Przekonajmy szczegóły, ale ci, którzy chcą zapoznać się z zawarciem formuły. Pomysł jest założenie, że istnieje pewien X, dla którego f n \u003d x n, a następnie znajdź x.Co znaczy
Redukcja x n-2
Rozwiążymy równanie kwadratowe:
Skąd rośnie "sekcja złota" φ \u003d (1 + √5) / 2. Zastępowanie początkowymi wartości i zrobimy więcej obliczeń, otrzymujemy:
Jak używamy do obliczenia F n.
Od __FUTURE__ Podział importu Import Math Def FIB (N): SQRT5 \u003d Math.SQRT (5) PHI \u003d (SQRT5 + 1) / 2 INT (Phi ** N / SQRT5 + 0,5)
Dobrze:
Szybko i tylko dla małych n
Ubogi:
Chciałem działalność przecinków pływających. W przypadku dużej n będzie wymagana duża dokładność.
Zło:
Zastosowanie zintegrowanych numerów do obliczenia F n jest piękne od matematycznego punktu widzenia, ale brzydki - z komputerem.
Rekurencja
Najbardziej oczywistą decyzją, którą już widziałeś wiele razy - najprawdopodobniej, jako przykład, w jakiej rekurencji jest. Powtarzam go ponownie na kompletność. W Pythonie można go napisać w jednej linii:FIB \u003d LAMBDA N: FIB (N - 1) + FIB (N - 2) Jeśli N\u003e 2 ELS 1
Dobrze:
Bardzo prosta implementacja powtarzająca się definicja matematyczna
Ubogi:
Czas wykonywania wykładniczego. Dla dużych n bardzo powoli
Zło:
Przepełnienie stosu
Pamięć
Rozwiązanie z rekurencją ma duży problem: przecinające się obliczenia. Gdy nazywany jest FIB (N), FIB (N-1) i FIB (N-2) są obliczane. Ale gdy rozważa się FIB (N-1), niezależnie obliczyć FIB (N-2) - to znaczy FIB (N-2) zostanie obliczona dwukrotnie. Jeśli kontynuujesz argumenty, będzie widoczne, że FIB (N-3) zostanie obliczone trzy razy itp. Zbyt wiele skrzyżowań.Dlatego wystarczy zapamiętać wyniki, aby nie liczyć ich ponownie. Czas i pamięć tego rozwiązania są spędzane liniowo. W rozwiązywaniu używam słownika, ale można użyć prostej tablicy.
M \u003d (0: 0, 1: 1) FIB (N): Jeśli N w M: Powrót M [N] M [N] \u003d FIB (N - 1) + FIB (N - 2) Powrót M [N]
(W Pythonie można go również wykonać za pomocą dekoratora, funkcji fundaols.Lru_Cache.)
Dobrze:
Po prostu włącz rekursję w rozwiązanie zapamiętywania. Obraca czas wykładniczego, aby wykonać liniowy, dla którego spędza więcej pamięci.
Ubogi:
Spędza dużo pamięci
Zło:
Możliwe jest przepełnienie stosu, jak w rekurencji
Programowanie dynamiczne
Po decyzji z zapamiętaniem staje się jasne, że nie potrzebujemy wszystkich poprzednich wyników, ale tylko ostatnie dwa. Ponadto, zamiast zaczynając od FIB (N) i wrócić, możesz zacząć od FIB (0) i pójść naprzód. Następny kod ma realizację linii liniowej, a użycie pamięci jest stałe. W praktyce prędkość rozwiązania będzie jeszcze wyższa, ponieważ nie ma rekurencyjnych wyzwań funkcji i powiązanej operacji. A kod wygląda łatwiej.To rozwiązanie jest często przynoszone jako przykład dynamicznego programowania.
DEF FIB (N): A \u003d 0 B \u003d 1 dla __ W zasięgu (N): A, B \u003d B, A + B Rurt A
Dobrze:
Działa szybko dla małego n, prostego kodu
Ubogi:
Nadal liniowy czas wykonania
Zło:
Tak, nic nie jest niczym.
Matrix Algebra.
I wreszcie, najmniej oświetlony, ale najbardziej prawidłowy rozwiązanie, kompetentnie używając czasu i pamięci. Może być również rozszerzony na dowolną jednorodną sekwencję liniową. Pomysł w użyciu matryc. Jest wystarczająco łatwy, aby to zobaczyć
A uogólnienie to mówi
Dwie wartości dla X, uzyskane przez nas wcześniej, z których jeden reprezentowany jest złotym przekrojem, są własne znaczenie macierzy. Dlatego inny sposób wysyłania zamkniętej formuły jest stosowanie równania matrycy i liniowej algebry.
Więc co jest przydatne takie sformułowanie? Na tym, że wystawa można przeprowadzić dla czasu logarytmicznego. Odbywa się to dzięki budowie placu. Dolna linia to
Gdzie pierwsze wyrażenie jest używane nawet a, drugi dla dziwnych. Pozostaje tylko organizowanie mnożenia matryc i wszystko jest gotowe. Uzyskuje się następujący kod. Zorganizowałem rekurencyjną realizację Pow, ponieważ łatwiej jest zrozumieć. Wersja iteracyjna tutaj wygląda.
DEF POW (X, N, I, mult): "" "Powrót x do stopnia n. Zakłada, że \u200b\u200bjest jedną matrycą, która zmienia się z mult, a n jest dodatnim całością" "" Jeśli N \u003d\u003d 0: Powrót I Elif N \u003d\u003d 1: Powrót X else: y \u003d pow (x, n //2, i, mult) y \u003d mult (y, y), jeśli n% 2: y \u003d mult (x, y) powrotu Y DEF Identity_Matrix (N): "" "Zwraca jedną matrycę n na N" "" R \u003d lista (zakres (N)) Powrót [dla J w R] DEF MATRIX_Multiply (A, B): bt \u003d lista (ZIP (* b )) Powrót [dla Row_a w A] DEF FIB (N): F \u003d PO ([,], N, Identity_Matrix (2), Matrix_MultiPly) Powrót
Dobrze:
Naprawiono pamięć, czas logarytmiczny
Ubogi:
Kod jest bardziej skomplikowany
Zło:
Muszę pracować z matrycami, chociaż nie są takie złe
Porównanie prędkości
Jest to tylko wariant dynamicznego programowania i macierzy. Jeśli porównają je według liczby znaków, wśród N, okazuje się, że roztwór macierzy jest liniowo, a roztwór z dynamicznym programowaniem jest wykładniczo. Praktyczny przykład - Obliczanie FIB (10 ** 6), numer, który będzie miał więcej niż dwieście tysięcy znaków.N \u003d 10 ** 6
Oblicz FIB_Matrix: FIB (N) ma tylko 208988 cyfr, obliczenia trwało 0,24993 sekundy.
Oblicz FIB_DYNAMIC: FIB (N) to tylko 208988 cyfr, obliczenia zajęło 11.83377 sekund.
Teoretyczne komentarze
Nie dotykając bezpośrednio kodu podanego powyżej, to uwaga jest nadal interesująca. Rozważ następujący wykres:
Oblicz liczbę ścieżek n z A do B. Na przykład, dla n \u003d 1 mamy w taki sposób, 1. Dla n \u003d 2, znowu mamy w taki sposób, 01. Dla n \u003d 3 mamy dwa sposoby, 001 i 101 . Jest to dość proste, aby pokazać, że liczba ścieżek N z A do B jest równa dokładności F n. Po napisaniu matrycy układu do wykresu otrzymujemy tę samą matrycę opisaną powyżej. Jest to dobrze znany wynik z teorii wykresów, który dla danej matrycy przylegania A, wystąpienie C N jest liczbą ścieżek n w kolumnie (jedno z zadań wymienionych w filmie "Umnitsa będzie polować" ).
Dlaczego są takie oznaczenia na wędrówce? Okazuje się, że podczas rozważania nieskończonej sekwencji znaków na niekończącej się po obu stronach sekwencji ścieżek na kolumnie, otrzymasz coś "Final Type Shifts", który jest typem symbolicznym systemem głośnikowym. W szczególności, że ten końcowy napój jest znany jako "przesunięcie złotej sekcji" i jest ustawiony jako zestaw "zakazanych słów" (11). Innymi słowy, otrzymamy nieskończone sekwencje binarne w obu kierunkach, a żadne pary ich nie będą przylegać. Topologiczna entropia tego dynamicznego układu jest równa złotej sekcji φ. Zastanawiam się, jak ten numer jest okresowo pojawiający się w różnych dziedzinach matematyki.
Numery Fibonacci. - Jest to wiele liczb, w których każdy następny numer jest równy sumie dwóch poprzednich: 1, 1, 2, 3, 5, 8, 13, .... Czasami rząd zaczyna się od podstaw: 0, 1, 1, 2, 3, 5, .... W takim przypadku będziemy przestrzegać pierwszej opcji.
Formuła:
F 1 \u003d 1
F 2 \u003d 1
F n \u003d f n-1 + f n-2
Przykład obliczeń:
F 3 \u003d F 2 + F 1 \u003d 1 + 1 \u003d 2
F 4 \u003d F 3 + F 2 \u003d 2 + 1 \u003d 3
F 5 \u003d F 4 + F 3 \u003d 3 + 2 \u003d 5
F 6 \u003d F 5 + F 4 \u003d 5 + 3 \u003d 8
...
Obliczanie n-tej liczby wiersza fibonacci za pomocą cyklu
- Przypisz pierwsze pierwsze elementy serii do zmiennych FIB1 i FIB2, czyli, przypisać jednostkę do zmiennej.
- Poproś o numer użytkownika elementu, którego wartość, którą chce dostać. Przypisz liczbę zmiennej n.
- Wykonaj następujące czynności n - 2 razy, ponieważ pierwsze dwa elementy są już brane pod uwagę:
- Napraw FIB1 i FIB2, przypisując wynik zmiennej do tymczasowego przechowywania danych, na przykład FIB_SUM.
- Zmienna FIB1 przypisuje wartość FIB2.
- Zmienna FIB2 przypisuje wartość FIB_SUM.
- Wyświetl FIB2.
Uwaga. Jeśli użytkownik wejdzie do 1 lub 2, korpus cyklu nigdy nie zostanie wykonany, wyświetlana jest oryginalna wartość FIB2.
fIB1 \u003d 1 FIB2 \u003d 1 n \u003d wejście () n \u003d int (n) i \u003d 0 podczas gdy ja< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)
Opcja kompaktowa kodu:
fIB1 \u003d FIB2 \u003d 1 n \u003d int (wejście ( "Numer elementu rzędu fibonacci:")) - 2, podczas gdy N\u003e 0: FIB1, FIB2 \u003d FIB2, FIB1 + FIB2 N - \u003d 1 Drukuj (FIB2)
Wyjście numerów Fibonacci z cyklem
W tym przypadku wyświetlane jest nie tylko wartość elementu fundamentowego serii Fibonacci, ale także wszystkie numery do IT włącznie. Aby to zrobić, wyjście wartości FIB2 jest umieszczone w cyklu.
fIB1 \u003d FIB2 \u003d 1 N \u003d Int (wejście ()) Jeśli n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()
Przykład wykonania:
10 1 1 2 3 5 8 13 21 34 55
Rekursywne obliczenie N-TIt rzędu Fibonacci
- Jeśli n \u003d 1 lub n \u003d 2, powrócić do zespołu dzwonienia, ponieważ pierwsze i drugie elementy zakresu Fibonacci są równe jednemu.
- We wszystkich innych przypadkach powodują, że ta sama funkcja z argumentami N - 1 i N - 2. Wynik dwóch połączeń do składania i powrót do oddziału dzwoniącego programu.
def Fibonacci (N): Jeśli N w (1, 2): Zwrot 1 Powrót Fibonacci (N - 1) + Fibonacci (N - 2) Drukuj (Fibonacci (10))
Załóżmy, że N \u003d 4. Następnie odbędzie się rekurencyjne połączenie Fibonacci (3) i Fibonacci (2). Drugi zwróci jednostkę, a pierwsza doprowadzi do dwóch kolejnych wyzwań działania: Fibonacci (2) i Fibonacci (1). Oba połączenia zostaną zwrócone przez jednego, w kwocie będzie dwa. W ten sposób wywołanie Fibonacci (3) zwraca numer 2, który jest podsumowany za pomocą numeru 1 z połączenia Fibonacci (2). Wynik 3 powraca do głównej gałęzi programu. Czwarty element zakresu Fibonacci wynosi trzy: 1 1 2 3.
