hanoi（遞回）-有解無憂

漢諾塔規則：
有n個盤子，從第一個柱子，移動到第三個柱子。要求每個盤子從柱子下到柱子上，序號是從小到大。

uj5u.com熱心網友回復：

“給定一個小點的輸入，完整單步跟蹤(同時按Alt+7鍵查看Call Stack里面從上到下列出的對應從里層到外層的函式呼叫歷史)一遍。”是理解遞回函式作業原理的不二法門！
遞回函式關注以下幾個因素
·退出條件
·引數有哪些
·回傳值是什么
·區域變數有哪些
·全域變數有哪些
·何時輸出
·會不會導致堆疊溢位

uj5u.com熱心網友回復：

這不是最經典的遞回嗎？
先借助第三個柱子把第一個柱子的n-1個盤子都移到第二個柱子，然后把第一個柱子的第n個盤子已到第三個柱子；然后借助第一個柱子把第二個柱子的n-1個盤子移動到第三個柱子。

void hanoi(char one, char tow, char three, int n) {

    if (n==1) {

        printf("從第%c個柱子移動第%d個盤子到第%c個柱子\n", one, n, three);

        return;

    }

    //printf("借助第%c個柱子把第%c個柱子的%d個盤子移動到第%c個柱子\n", three, one, n-1, tow);

    hanoi(one, three, tow, n-1);

    printf("從第%c個柱子移動第%d個盤子到第%c個柱子\n", one, n, three);

    //printf("借助第%c個柱子把第%c個柱子的%d個盤子移動到第%c個柱子\n", one, tow, n-1, three);

    hanoi(tow, one, three, n-1);

}



int main() {

    int n=5;

    char a='1', b='2', c='3';

    hanoi(a, b, c, n);

    return 0;

}

uj5u.com熱心網友回復：

參考 2 樓 qybao的回復:

void hanoi(char one, char tow, char three, int n) {

    if (n==1) {

        printf("從第%c個柱子移動第%d個盤子到第%c個柱子\n", one, n, three);

        return;

    }

    //printf("借助第%c個柱子把第%c個柱子的%d個盤子移動到第%c個柱子\n", three, one, n-1, tow);

    hanoi(one, three, tow, n-1);

    printf("從第%c個柱子移動第%d個盤子到第%c個柱子\n", one, n, three);

    //printf("借助第%c個柱子把第%c個柱子的%d個盤子移動到第%c個柱子\n", one, tow, n-1, three);

    hanoi(tow, one, three, n-1);

}



int main() {

    int n=5;

    char a='1', b='2', c='3';

    hanoi(a, b, c, n);

    return 0;

}

不是這個意思

uj5u.com熱心網友回復：

參考 3 樓 m0_50813063 的回復:

不是這個意思

怎么不是這個意思？盤子序號和盤子大小有什么要求嗎？序號編號的時候盤子大小越大盤子序號越小不就好了嗎？如果是亂序，就有可能出現大盤子壓在小盤子上面，是這樣的嗎？

uj5u.com熱心網友回復：

參考 4 樓 qybao的回復:

Quote: 參考 3 樓 m0_50813063 的回復:

不是這個意思

怎么不是這個意思？盤子序號和盤子大小有什么要求嗎？序號編號的時候盤子大小越大盤子序號越小不就好了嗎？如果是亂序，就有可能出現大盤子壓在小盤子上面，是這樣的嗎？

它跟盤子大小沒有關系，就是每個塔的序號都是從下往上增大

uj5u.com熱心網友回復：

參考 5 樓 m0_50813063 的回復:

它跟盤子大小沒有關系，就是每個塔的序號都是從下往上增大

看你發的圖片，是想要這樣的結果吧（就是控制列印序號而已，遞回本身沒變）
盤子編號從下到上逐漸增大

//引數說明：x,y,z柱子名，num盤子(帶編號)，len盤子陣列長度，cnt柱子上的盤子數，step步驟

void hanoi(char x, char y, char z, int *num, int len, int cnt, int *step) {

    if (cnt==1) {

        printf("第%d步: move %d, %c -> %c\n", *step, num[cnt-1], x, z);

        (*step)++;

        return;

    }

    hanoi(x, z, y, num, len, cnt-1, step);

    printf("第%d步: move %d, %c -> %c\n", *step, num[cnt-1], x, z);

    (*step)++;

    hanoi(y, x, z, num, len, cnt-1, step);

}



int main() {

    int num[]={5,4,3,2,1}, len=5, cnt=5, step=1; //num陣列就是盤子編號，從上到下逐漸減小（從下到上逐漸增大）

    char x='x', y='y', z='z';

    hanoi(x, y, z, num, len, cnt, &step);

    return 0;

}

uj5u.com熱心網友回復：

說白了
hanoi(char one, char tow, char three, int n) 這部分的引數不變
hanoi(char x, char y, char z, int *num, int len, int cnt, int *step)
只是多了num，len和step來控制列印的步數和盤子序號，所以它還是原來漢塔塔的思路，只不過多了一些列印控制

uj5u.com熱心網友回復：

參考 6 樓 qybao的回復:

Quote: 參考 5 樓 m0_50813063 的回復:

它跟盤子大小沒有關系，就是每個塔的序號都是從下往上增大

看你發的圖片，是想要這樣的結果吧（就是控制列印序號而已，遞回本身沒變）
盤子編號從下到上逐漸增大

//引數說明：x,y,z柱子名，num盤子(帶編號)，len盤子陣列長度，cnt柱子上的盤子數，step步驟

void hanoi(char x, char y, char z, int *num, int len, int cnt, int *step) {

    if (cnt==1) {

        printf("第%d步: move %d, %c -> %c\n", *step, num[cnt-1], x, z);

        (*step)++;

        return;

    }

    hanoi(x, z, y, num, len, cnt-1, step);

    printf("第%d步: move %d, %c -> %c\n", *step, num[cnt-1], x, z);

    (*step)++;

    hanoi(y, x, z, num, len, cnt-1, step);

}



int main() {

    int num[]={5,4,3,2,1}, len=5, cnt=5, step=1; //num陣列就是盤子編號，從上到下逐漸減小（從下到上逐漸增大）

    char x='x', y='y', z='z';

    hanoi(x, y, z, num, len, cnt, &step);

    return 0;

}

謝謝，大佬。

uj5u.com熱心網友回復：

參考 6 樓 qybao的回復:

Quote: 參考 5 樓 m0_50813063 的回復:

它跟盤子大小沒有關系，就是每個塔的序號都是從下往上增大

看你發的圖片，是想要這樣的結果吧（就是控制列印序號而已，遞回本身沒變）
盤子編號從下到上逐漸增大

//引數說明：x,y,z柱子名，num盤子(帶編號)，len盤子陣列長度，cnt柱子上的盤子數，step步驟

void hanoi(char x, char y, char z, int *num, int len, int cnt, int *step) {

    if (cnt==1) {

        printf("第%d步: move %d, %c -> %c\n", *step, num[cnt-1], x, z);

        (*step)++;

        return;

    }

    hanoi(x, z, y, num, len, cnt-1, step);

    printf("第%d步: move %d, %c -> %c\n", *step, num[cnt-1], x, z);

    (*step)++;

    hanoi(y, x, z, num, len, cnt-1, step);

}



int main() {

    int num[]={5,4,3,2,1}, len=5, cnt=5, step=1; //num陣列就是盤子編號，從上到下逐漸減小（從下到上逐漸增大）

    char x='x', y='y', z='z';

    hanoi(x, y, z, num, len, cnt, &step);

    return 0;

}

我回去試試。

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/173534.html

標籤：C++ 語言

上一篇：IOS上架2.3.1駁回n次了，說有隱藏功能，求大神SOS

下一篇：如何撰寫模塊來實作將eht0埠上收到的包發送到eth1埠上？