Witam, mam za zadanie napisać wykorzystując programowanie dynamiczne algorytm obliczający na ile możliwości można przejść n metrów mając do dyspozycji kroki np 1 metr, 2 metry i 3 metry.
Jak się za to zabrać?
0
2
Tak samo jak za wydawanie reszty, bo to ten sam problem. Opis algorytmu masz na wiki.
Edit: źle przeczytałem treść - to jest zwykle równanie rekurencyjne i da się je rozwiązać na kartce w kilku linijkach i żadne algorytmy tu nie potrzebne...
0
@Shalom to byłoby takie proste, gdybyśmy dysponowali wszystkim możliwymi długościami od 1 do N (wtedy wynik to po prostu 2^N), ale jak rozumiem autora, to np. może być N=10, a możliwe długości to {2,3}.
Można to zrobić za pomocą programowania dynamicznego (http://www.algorytm.org/kurs-algorytmiki/programowanie-dynamiczne.html).
0
Ale przecież generalnie podejście do rozwiązania takiego równania rekurencyjnego jest bardzo podobne do algorytmu który trzeba napisać. Ot tworzymy sobie zależność:
dla długości {1,2,3}
F(0) = 0
F(1) = 1 bo tylko {(1)}
F(2) = F(1) + 1 = 2 bo {(1,1),(2)}
F(3) = F(1) + F(2) + 1 = 4 bo {(1,1,1),(1,2), (2,1), (3)}
F(n) = F(n-3) + F(n-2) + F(n-1)
np.
F(4) = F(1) + F(2) + F(3) = 7
bo {(1,1,1,1),(1,1,2),(1,2,1),(1,3),(2,1,1),(2,2),(3,1)}
Dlaczego tak jest? Bo do długości N możemy dojść na tyle sposobów co na dojscie do długości N-3 i stamtąd robimy krok o dlugości 3, na dojście do N-2 i robimy krok o długości 2, na dojście do N-1 i robimy krok długości 1.
A teraz idea algorytmu jest banalnie prosta: niech F będzie tablicą o dlugości N. Wypełniasz sobie tą tablicę od 0 aż do N zgodnie z podanym wyżej sposobem. Czas obliczania tego będzie O(n)*O(k) gdzie n to dlugość do przejścia a k to liczba możliwych kroków.