我試圖解決其中有三個樁,但相同的高度和磁盤大小的兩個塔河內塔問題的一個變種。任務是交換兩個塔。如何實現遞歸算法向後
我的解決辦法是兩個塔堆疊在一起大塔(可堆疊在彼此頂部上的相同大小的磁盤),並將它們再次分裂(至當然切換栓)。
我能夠既塔疊加在一起,但我不能夠扭轉我的算法,他們又分手了。
在這種情況下有兩個塔樓,每三個磁盤。一個在左邊,一個在中間。在我的算法之後,有一個塔上有六個磁盤在右側。
我的算法如下:(我使用Java)
public void solve() {
combineTo(3, 0, 1, 2); // parameters: (height, from, to, temp)
splitUp(?, ?, ?, ?);
}
private void moveDisk(int from, int to){
// here are also a few other things going on but
// that doesn't matter in this case
System.out.println("from: "+from+" - to: "+to);
}
private void moveTower(int i, int from, int to, int temp) {
if (i == 0) return;
else{
moveTower(i-1, from, temp, to);
moveDisk(from, to);
moveDisk(from, to);
moveTower(i-1, temp, to, from);
}
}
private void combineTo(int i, int from, int to, int temp){
if (i==0) return;
else{
combineTo(i-1, from, to, temp);
moveDisk(to, from);
moveTower(i-1, temp, to, from);
moveDisk(from, temp);
moveDisk(from, temp);
moveTower(i-1, to, temp, from);
}
}
private void splitUp(int i, int from, int to, int temp){
if (i==0) return;
else{
???
}
}
那麼,如何扭轉這種與splitUp
方法?
這是一個家庭作業的問題? – Ian
您可以使用隊列來反轉堆棧 –
是的。這是一個家庭作業問題,我想只是倒轉堆棧(因爲我把所有動作放在堆棧上,以便能夠向前和向後播放所有動作)。但是,任務是用遞歸算法完成這一切。 – sebastian