Ilość możliwości przejścia N metrów.

Hej, mam taki problem i nie bardzo wiem jak się do niego zabrać. Mianiowicie potrzebuję skonstruować algorytm programowaniem dynamicznym obliczający ilość możliwości przejścia n metrów, jakie ma robot, który robi kroki o długości 1 metr, 2 metry lub 3metry. Kolejność kroków jest istotna. Najpierw skupiam się na pseudokodzie, implementacją już zajmę się sam.

Póki co widzę to tak:
Interesuje nas aby robot przeszedł dany dystans najmniejszą liczbą kroków, a więc najfajniej by było gdyby cały dystans udało się przejść 3metrowymi krokami ponieważ wtedy będzie ich najmniej, natomiast dystans może nie byc podzielny przez 3 więc co krok będziemy sprawdzać podzielność dystansu i wybierać jak duży krok wykonujemy.

Każda pomoc mile widziana.

To się nazywa: Problem wydawania reszty.
W wielkim skrócie: masz tablicę o długości N i w każdej komórce wpisujesz na ile sposobów mozna przejść daną długość. Jak nie trudno zauważyć można łatwo policzyć wartość w K-tej komórce znając wszystkie poprzednie, bo K metrów można przejść na tab[K-1]+tab[K-2]+tab[K-3] sposobów. Wynika to z faktu, że K metrów można przejść robiąc to samo co dla K-1 metrów a na koniec zrobić 1 metrowy krok, lub robiąc to samo co dla K-2 metrów i na koniec robiąc 2-metrowy krok, lub analogicznie dla K-3.
Obliczasz sobie komórki w tablicy od początku i voila.

Długo mi to zajęło, ale coś takiego? :D

 
ROBOT(n)
tablica T[1....n]
T[1]=1
T[2]=2
T[3]=3
for i<-3 to n do
T[n]=T[n-1]+T[n-2]+T[n-3]
return T[n]

Nie bo źle wypełniłeś pierwsze 3 kroki ;]
1 metr można przejść na 1 sposób
2 metry można przejść na 2 sposoby
ale 3 metry można przejść za pomocą 1+1+1, 1+2, 2+1 oraz 3
dalej powinno być ok

Faktycznie, teraz powinno być juć ok , dzięki.

 ROBOT(n)
tablica T[1....n]
T[1]=1
T[2]=2
T[3]=4
for i<-4 to n do
T[n]=T[n-1]+T[n-2]+T[n-3]
return T[n]

Nie no nadal jest źle bo pętla idzie po i a nie po n więc indeksy w tablicy też...

Kurcze już długo nad tym myślałem i wg mnie się zgadza, zakładam więc że nie widzę swojego błędu, czy mogę prosić o jeszcze jedną wskazówkę ?

Jejku, jej! Jak masz pętlę
for i<-4 to n do
czyli taką gdzie i przyjmuje kolejne wartości to wypadałoby żeby przypisywać wartości do T[i] a nie do T[n] skoro n jest stałe.

chodzi o ten głupi błąd?

 ROBOT(n)
tablica T[1....n]
T[1]=1
T[2]=2
T[3]=4
for i<-4 to n do
T[i]=T[i-1]+T[i-2]+T[i-3]
return T[i]

Ja powoli dochodzę do wniosku że ty zgadujesz z tym pseudokodem :D :D Na samym końcu ma być return T[n] bo ten return jest juz poza pętlą gdzie zmienna i już nie istnieje. Zresztą ty chcesz zwrócić ostatni element tablicy.