Cuo sam za legendu, ali mi se cini da je bilo 64 prstena . Kad bi to radio covjek definitivno bi mu trebalo nekih milion godina da rijesi problem ne zbog njegove tezine koliko zbog velikog broja kombinacija koje se moraju napraviti da bi se svi prsteni prebacili sa jednog na drugi stap koriscenjem treceg naravno. To ti je nesto kao koliko covjeku treba da izbroji do 1 000 000 000 (uz pretpostavku da mu za svaki broj treba 1 sekund) - oko 30 godina... . Znaci nije problem u tezini koliko u glomaznosti resenja.

Nije jasno, a sve lepo piše. Rešenje je čista filozofija.

Pitanje je: kako prebaciti sve prstenove s prvog štapa na treći uz pomoć drugog?

Odgovor je: lako, iz najviše 3 poteza.

- Ako imaš samo jedan prsten prebaci ga s prvog na treći štap i gotova priča.
- Inače, prebaci sve osim poslednjeg prstena s prvog štapa na drugi, pa preostali prsten s prvog na treći i na kraju još samo prebaci i ove s drugog na treći.

Ne smes da pomeras vise od jednog prstena. Znaci jedan po jedan. Najmanji broj pomeranja je (2^n) - 1 gde je n broj prstenova, sto bi znacilo da za 64 prstena treba 18446744073709551615 pomeranja... nacekacemo se mi do kraja sveta

Iza svake rekurzivne funkcije, krije se neka matematicka formula (za koju treba naravno i dokazati da je rekurzivna). Najcesci primer koji se koristi za opis ovoga je npr izracunavanje faktorijala:

6! := 6*5*4*3*2*1

Dva primera izracunavanja faktorijala:
1.
function Izracunaj(const N: Integer): Integer; //<-- bez upotrebe rekurzije
var
I: integer;
begin
Result := 1;
for i:=2 to N do // program ne ulazi u petlju ako je N = 1
Result := Result * I;
end;

2.
function Fact( var N: integer): integer; //<--- upotrebom rekurzije
begin
if N = 0 then
Result := 1
else
Result := N * Fact(N-1); // <--- funkcija Fact poziva samu sebe!
end;

I kod Hanojskih kula, isto se mogu resiti obicnim petljama (for, while, repeat). Probaj da resis problem na taj nacin, bice ti onda jasnije kako funkcionise rekurzija. Tu naravno postoje neka pravila: uvek mozes da pomeras samo jedan disk u jednom potezu, veci disk ne moze da se stavi na manji.

PS: Pogledaj temu http://www.elitesecurity.org/tema/83275/1, tamo sam postovao hanoi.zip, igrica, probaj... : )

btw: ne koristim rekurziju, cesto veoma brzo napuni stek...

Pozdav!

O čemu se ovde priča? Rešenje je dato u početnoj poruci uz konstataciju da nije jasno kako to funkcioniše.

Tu sve piše, a treba još i pojašnjenje. Pa dobro, vidim da u oči posebno upada primedba da se u jednom potezu prebacuje tačno jedan prsten. Ova funkcija uvek rešava problem (ne ubijajte se u pojam postavljanjem nekog povelikog početnog n jer je to samo ograničenje za računar).

Radi se dekompozicija problema.
... ako je samo jedan prsten, prebaci ga na cilj
... inače ide ta dekompozicija - "Prebaci sve osim poslednjeg na pomoćni" - rekurzivni poziv funkcije i pošto se u potpunosti izvrši ide se dalje. Hajde, meni nažalost nije jasno šta tu ne može da bude jasno. Evo da samo izmenim malo funkciju...