Hanoi Kulesi: Özyinelemeli Algoritma

SORU

3 AĞUSTOS 2009, PAZARTESİ

Hanoi Kulesi: Özyinelemeli Algoritma

Bir Bilgisayar mühendisliği öğrencisi olduğumu ve bu sorun her ne özyineleme anlayış var. Ancak, sorun Hanoi Kulesi için özyinelemeli çözüm başımı sarmak için görünmüyor olabilir. Burada Wikipedia: kodu

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

Tek bir disk hareket edebiliyoruz kadar temel durum ve küçük parçalara sorunu kırma kavramı anlıyorum. Ancak, temel olmayan durumda iki özyinelemeli çağrıları birlikte nasıl çalıştığını çözemedim. Belki biri bana yardım edebilir mi? Teşekkürler.

CEVAP

3 AĞUSTOS 2009, PAZARTESİ

Aslında, section from where you took that code bir açıklama sunuyor:

Peg peg C A n diskleri taşımak için:

n−1 B. Bu diskleri yaprakları hareket disk #Bir tahta üzerinde n yalnız
disk hareket #A n C için
disk üzerinde oturuyorlar yani C için n−1 disk B hareket #n

İlk kaldırmak zorunda olduğu çok açıkn− 1 ulaşmak için disklernth bir. Ve onları taşımak için başka bir peg için ilk görünmesi için tam kule istediğiniz daha.

Sonrası kod üç bağımsız disklerin sayısı ayrıca vardır: Birkaynakpeg, birhedefpeg ve birgeçici(burada boyutu ile her disk arasında saklı olabilir hangi peg ^em>n− 1 uyar).

Özyineleme aslında iki kez, bir kez sonra *2,* Daha önce bir kere olur. writeln önce bir hareket olacaktırn− 1 geçici peg üzerine, geçici depolama (özyinelemeli çağrı argümanlar farklı sırayla) olarak hedef peg kullanarak diskleri. Bundan sonra, geri kalan diskin hedef peg taşınır ve daha sonra ikinci özyineleme taşıyarak tüm kule, hareketli compeltesn− 1 Hedef peg, yukarıdaki disk temp peg kulen.

Bunu Paylaş: