[Spoj][Algorytmy][C++] Zmiana rekurencji na iterację

calmosc
Użytkownik
Użytkownik
Posty: 41
Rejestracja: 4 cze 2013, o 15:28
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 8 razy

[Spoj][Algorytmy][C++] Zmiana rekurencji na iterację

Post autor: calmosc »

Od razu podlinkuję zadanie, na którym się skupię:
Tak więc wymyśliłem, że rozbijam to na podproblemy, tj. szukaną liczbę możliwości w sytuacji S[x,y,z] (nad książką siedzi już \(\displaystyle{ x}\)-ty tłumacz, przetłumaczono \(\displaystyle{ y}\) stron i zrobiono przy tym \(\displaystyle{ z}\) błędów) przedstawiam jako sumę liczb możliwości w sytuacjach S[x-1,y,z] i S[x,y-1,z-bx] (bx - liczba błędów robionych na stronę przez \(\displaystyle{ x}\)-tego tłumacza). Problem w tym, że nie wiem jak tę zależność rekurencyjną zmienić na iterację, coby uniknąć nadmiernych wywołań funkcji i zmniejszyć złożoność obliczeniową. Nie bardzo wiem, jak zacząć, i jak iterować kolejne elementy, byłbym wdzięczny za jakieś wskazówki. Pozdrawiam.
Ostatnio zmieniony 20 lis 2015, o 18:27 przez Afish, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Spoj][Algorytmy][C++] Zmiana rekurencji na iterację

Post autor: Afish »

Trzymasz dwie tablice: oldState z liczbą kombinacji dla pisarzy[1 ... i-1] i newState dla stanu uwzględniającego \(\displaystyle{ i}\)-tego pisarza.
Dla każdej liczby myPages = 1 ... s, dla każdej liczby otherPages = 0 ... s - myPages, dla każdej liczby otherBugs = 0 ... b - myBugs * myPages sprawdzasz, czy oldState[otherPages][otherBugs] > 0. Jeżeli tak, to newState[otherPages + myPages][otherBugs + myBugs * myPages] ++
calmosc
Użytkownik
Użytkownik
Posty: 41
Rejestracja: 4 cze 2013, o 15:28
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 8 razy

[Spoj][Algorytmy][C++] Zmiana rekurencji na iterację

Post autor: calmosc »

Nie do końca rozumiem, ile tutaj będzie pętli?
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Spoj][Algorytmy][C++] Zmiana rekurencji na iterację

Post autor: Afish »

Trzy.
ODPOWIEDZ