2014-01-29 153 views
0

我試圖解決其中有三個樁,但相同的高度和磁盤大小的兩個塔河內塔問題的一個變種。任務是交換兩個塔。如何實現遞歸算法向後

我的解決辦法是兩個塔堆疊在一起大塔(可堆疊在彼此頂部上的相同大小的磁盤),並將它們再次分裂(至當然切換栓)。

我能夠既塔疊加在一起,但我不能夠扭轉我的算法,他們又分手了。

在這種情況下有兩個塔樓,每三個磁盤。一個在左邊,一個在中間。在我的算法之後,有一個塔上有六個磁盤在右側。

我的算法如下:(我使用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方法?

+0

這是一個家庭作業的問題? – Ian

+0

您可以使用隊列來反轉堆棧 –

+0

是的。這是一個家庭作業問題,我想只是倒轉堆棧(因爲我把所有動作放在堆棧上,以便能夠向前和向後播放所有動作)。但是,任務是用遞歸算法完成這一切。 – sebastian

回答

0

由於基因說,我已經有了最難的部分。 用我在問題中提供的算法,我已經在右邊有一大堆。

然後我感動的是棧的經典算法河內到左邊,增加了以下遞歸算法。

public void solve() { 
    combineTo(i, 0, 1, 2); // combines 2 stacks to the right 
    hanoi(2*i, 2, 0, 1); // moves big stack to the left 
    splitTower(2*i, 0, 1, 2); // splits tower up again 
} 

private void splitTower(int i, int from, int to, int temp) { 
    if (i == 0) return; 
    else{ 
     hanoi(i-1, from, to, temp); 
     splitTower(i-1, to, from, temp); 
    } 
} 


private void hanoi(int i, int from, int to, int temp) { 
    if (i == 0) return; 
    else{ 
     hanoi(i-1, from, temp, to); 
     moveDisk(from, to); 
     hanoi(i-1, temp, to, from); 
    } 
} 
1

你有困難的部分!考慮從卡組底部發牌。一旦將它們合併到一個堆棧中,只需將整個堆棧移動到需要底部磁盤的位置即可。然後再將整個堆棧減去底部元素移動到底部第二個需要的位置。等等也許有一個更聰明的方法,但這肯定有效。

(您也可以通過一次處理兩關底做拆垛,你沒堆疊的方式相反。這可能是一個小更高效。)

這裏有一個C版本與簡單的文本圖形。注意我用一種稍微不同的方式來構建單個堆棧。你的總動作更有效率。我們交換正標盤與負:

#include <stdio.h> 

// Three pegs with various numbers of integer-labeled disks. 
struct peg { 
    int disks[30]; 
    int n_disks; 
} pegs[3]; 

// Set up positive-labeled disks on peg 0 and negative ones on peg 1. 
void init(int n_disks) 
{ 
    for (int i = 0; i < n_disks; ++i) { 
    pegs[0].disks[i] = n_disks - i; 
    pegs[1].disks[i] = -(n_disks - i); 
    } 
    pegs[0].n_disks = pegs[1].n_disks = n_disks; 
} 

// Draw simple text graphic of pegs. 
void show(void) 
{ 
    printf("|\n"); 
    for (int i = 0; i < 3; i++) { 
    printf("|"); 
    for (int j = 0; j < pegs[i].n_disks; j++) 
     printf("|%2d|", pegs[i].disks[j]); 
    printf("\n|\n"); 
    } 
    printf("\n"); 
} 

// Move one disk and draw the pegs. 
void move_1(int a, int b) 
{ 
    struct peg *peg_a = &pegs[a], *peg_b = &pegs[b]; 
    int disk = peg_a->disks[--peg_a->n_disks]; 
    peg_b->disks[peg_b->n_disks++] = disk; 
    //printf("move disk %d from peg %c to peg %c\n", disk, 'A' + a, 'A' + b); 
    show(); 
} 

// Move top n disks of tower at from to to using tmp as storage. 
void move(int n, int from, int to, int tmp) 
{ 
    if (n == 0) return; 
    move(n - 1, from, tmp, to); 
    move_1(from, to); 
    move(n - 1, tmp, to, from); 
} 

// Stack the towers 0 and 1 of height n into a single tower on 2. 
void stack(int n) 
{ 
    if (n == 0) 
    return; 
    // Extra base case skips a couple of redundant moves. 
    if (n == 1) { 
    move_1(0, 2); 
    move_1(1, 2); 
    return; 
    } 
    stack(n - 1); 
    move_1(0, 1); 
    move(2 * (n - 1), 2, 0, 1); 
    move_1(1, 2); 
    move_1(1, 2); 
    move(2 * (n - 1), 0, 2, 1); 
} 

// Swap contents of pegs 0 and 1 using 2 as temp storage. 
void swap(void) 
{ 
    stack(pegs[0].n_disks); 
    int n = pegs[2].n_disks; 
    move(n, 2, 1, 0); 
    while (n > 0) { 
    move(--n, 1, 0, 2); 
    move(--n, 0, 1, 2); 
    } 
} 

int main(void) 
{ 
    int n = 3; 
    init(n); 
    show(); 
    swap(); 
    return 0; 
} 
+0

謝謝。這也是一個很好的解決方案。我想,拆堆部分比我的效率更高。但我很高興自己得到了它(幾天之後)。但是你的解決方案讓我更加了解。那謝謝啦。 – sebastian