Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Legenda o Hanojskim kulama

[es] :: Pascal / Delphi / Kylix :: Legenda o Hanojskim kulama

[ Pregleda: 4440 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Pomaze_Bog
Ivan Nedić
Prevodilac (ruski, engleski)
Mladenovac

Član broj: 30699
Poruke: 55
*.vdial.verat.net.



Profil

icon Legenda o Hanojskim kulama26.04.2005. u 11:01 - pre 230 meseci
Ko ne zna legendu evo je...
U jednom budističkom manastiru postoje tri štapa sa nanizanim prstenovima koji su svi različite veličine. U početku su bili nanizani na prvom štapu, i to tako da je na svakome stajao manji od njega. Ostavljeno je u amanet monasima da premeste sve prstenove (mislim oko 48) na treći štap uz pomoć drugog, i to jedan po jedan, tako da se zadrži početni poredak - da nikako ne sme doći veći prsten iznad manjeg. Legenda kaže (što je manje važno) da će, kada se premeste svi prstenovi na treći štap, doći kraj sveta.
E, sad, pretočite to u pascalov programčić...
Zapravo, to smo radili u školi, ali mi nije baš jasno šta se zapravo dešava, i na koju foru rade ove rekurzije...
Evo ga kod:
Code:
program HanojskeKule;
procedure Prebaci(n:integer; izvor, pomoc, cilj: char);
begin
  if n=1 then writeln('Sa ',izvor,' na ',cilj)
         else
         begin
           Prebaci(n-1, izvor, cilj, pomoc);
           writeln('Sa ',izvor,' na ',cilj);
           Prebaci(n-1, pomoc, izvor, cilj)
         end
end;
var n:integer;
begin
  write('n=');
  readln(n);
  Prebaci(n,'A','B','C');
  writeln('Enter...');
  readln
end.
 
Odgovor na temu

Byk
Podgorica

Član broj: 55128
Poruke: 20
*.proxy.cg.yu.



Profil

icon Re: Legenda o Hanojskim kulama26.04.2005. u 12:16 - pre 230 meseci
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.
 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
194.247.222.*

Sajt: www.novikorisnik.net


+5 Profil

icon Re: Legenda o Hanojskim kulama26.04.2005. u 12:48 - pre 230 meseci
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.
 
Odgovor na temu

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
195.252.80.*

ICQ: 246436949


+10 Profil

icon Re: Legenda o Hanojskim kulama26.04.2005. u 16:11 - pre 230 meseci
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
 
Odgovor na temu

bondja

Član broj: 10286
Poruke: 167
*.adsl.sezampro.yu.



+3 Profil

icon Re: Legenda o Hanojskim kulama28.04.2005. u 07:38 - pre 230 meseci
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!

 
Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
194.247.222.*

Sajt: www.novikorisnik.net


+5 Profil

icon Re: Legenda o Hanojskim kulama28.04.2005. u 08:40 - pre 230 meseci
O čemu se ovde priča? Rešenje je dato u početnoj poruci uz konstataciju da nije jasno kako to funkcioniše.
Code:
procedure Prebaci(n:integer; izvor, pomoc, cilj: char);
begin
  if n=1 then writeln('Sa ',izvor,' na ',cilj)
         else
         begin
           Prebaci(n-1, izvor, cilj, pomoc);
           writeln('Sa ',izvor,' na ',cilj);
           Prebaci(n-1, pomoc, izvor, cilj)
         end
end;

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.
Code:
if n=1 then writeln('Sa ',izvor,' na ',cilj)
... ako je samo jedan prsten, prebaci ga na cilj
Code:
else
         begin
           Prebaci(n-1, izvor, cilj, pomoc);
           writeln('Sa ',izvor,' na ',cilj);
           Prebaci(n-1, pomoc, izvor, cilj)
         end
... 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...
Code:
procedure Prebaci(n:integer; izvor, pomoc, cilj: char);
begin
  if n>0 then
         begin
           Prebaci(n-1, izvor, cilj, pomoc);
           writeln('Sa ',izvor,' na ',cilj);
           Prebaci(n-1, pomoc, izvor, cilj)
         end
end;

 
Odgovor na temu

[es] :: Pascal / Delphi / Kylix :: Legenda o Hanojskim kulama

[ Pregleda: 4440 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.