漢諾塔的游戲規(guī)則：

?

有三根金剛石柱子A、B、C，在A柱子上從下往上按照大小依次減小的順序摞著64片黃金環(huán)。大梵天命令婆羅門把環(huán)從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在任何一個(gè)柱子上，小環(huán)上不能放大環(huán)，在三根柱子之間一次只能移動(dòng)一個(gè)環(huán)。

即將A柱子上全部的環(huán)通過C柱子（C柱子作為中介）移動(dòng)到B柱子上

當(dāng)A只有一個(gè)環(huán)的時(shí)候：

A->B

當(dāng)A只有兩個(gè)環(huán)的時(shí)候：

A->C? A->B??C->B

當(dāng)A只有三個(gè)環(huán)的時(shí)候：

A->B??A->C? B->C??A->B??C->A??C->B??A->B

思路：

• 1、將 n-1個(gè)環(huán)先放到C柱子上
• 2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到B柱子上
• 3、將n-1個(gè)環(huán)從C柱子移動(dòng)到B柱子上

當(dāng)n=1時(shí)：

1、將0個(gè)環(huán)先放到C柱子上

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到B柱子上：A->B

3、將0個(gè)環(huán)從C柱子移動(dòng)到B柱子上

當(dāng)n=2時(shí)：

1、將1個(gè)環(huán)先放到B柱子上：A->C

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到B柱子上：A->B

3、將1個(gè)環(huán)從C柱子移動(dòng)到B柱子上:C->B

當(dāng)n=3時(shí)：

1、將2個(gè)環(huán)先放到C柱子上：使用遞歸將2個(gè)環(huán)放到C上，因?yàn)锳柱子的最后一個(gè)環(huán)是最大的因此可以先不理會(huì)，遞歸重復(fù)當(dāng)n=2時(shí)的步驟，不過是從將2個(gè)環(huán)從A放到B上改為將2個(gè)環(huán)從A放到C上了

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到B柱子上：A->B

3、將2個(gè)環(huán)從C柱子移動(dòng)到B柱子上:使用遞歸將2個(gè)環(huán)從C柱子移動(dòng)到B柱子上，此時(shí)B柱子上已經(jīng)有了最大的一個(gè)環(huán)因此可以不用再理會(huì)了，遞歸重復(fù)當(dāng)n=2的步驟，不過是從將2個(gè)環(huán)從A放到B上改為將2個(gè)環(huán)從C放到B上了

當(dāng)n=4時(shí)：

1、將3個(gè)環(huán)先放到C柱子上：遞歸重復(fù)n=3的步驟，不過是從將3個(gè)環(huán)從A放到B上改為將3個(gè)環(huán)從A放到C上了

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到B柱子上：A->B

3、將3個(gè)環(huán)從C柱子移動(dòng)到B柱子上:遞歸重復(fù)當(dāng)n=3的步驟，不過是從將3個(gè)環(huán)從A放到B上改為將3個(gè)環(huán)從C放到B上了

見代碼

 #include <stdio.h>
void hanoi(int num, char sou, char tar, char aux) {
    //統(tǒng)計(jì)移動(dòng)次數(shù)
    static int i = 1;
    //如果圓盤數(shù)量僅有 1 個(gè)，則直接從起始柱移動(dòng)到目標(biāo)柱
    if (num == 1) {
        printf("第%2d次:從 %c 移動(dòng)至 %c\n", i, sou, tar);
        i++;
    }
    else {
        //遞歸調(diào)用 hanoi() 函數(shù)，將 num-1 個(gè)圓盤從起始柱移動(dòng)到輔助柱上
        hanoi(num - 1, sou, aux, tar);
        //將起始柱上剩余的最后一個(gè)大圓盤移動(dòng)到目標(biāo)柱上
        printf("第%2d次:從 %c 移動(dòng)至 %c\n", i, sou, tar);
        i++;
        //遞歸調(diào)用 hanoi() 函數(shù)，將輔助柱上的 num-1 圓盤移動(dòng)到目標(biāo)柱上
        hanoi(num - 1, aux, tar, sou);
    }
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    //起始柱、目標(biāo)柱、輔助柱分別用 A、B、C 表示
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

運(yùn)行截圖總結(jié)

?

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論