一、前言

漢諾塔（Tower of Hanoi），又稱(chēng)河內(nèi)塔，是一個(gè)源于印度古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤(pán)。大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。

二、漢諾塔打印步數(shù)

1、不使用遞歸計(jì)算1個(gè)n層的漢諾塔從A柱到C柱的所有步數(shù)如下

實(shí)現(xiàn)代碼：

#define _CRT_SECURE_NO_WARNINGS#include#includeint main(){  int num = 0;  scanf("%d", &num);//塔數(shù)  printf("完成%d層的漢諾塔需要%d步\n", num, (int)pow(2,num) - 1);  return 0;}

2、使用遞歸計(jì)算1個(gè)n層的漢諾塔從A柱到C柱的所有步數(shù)

原理：

• 將n-1個(gè)碟子從A桿經(jīng)C桿移動(dòng)到B桿

• 將A桿上的第n個(gè)碟子移動(dòng)到C桿

• 將n-1個(gè)碟子從B桿經(jīng)A桿移動(dòng)到C桿

所以: f (n -1 ) + 1 + f (n - 1); ?->? 2 * f (n - 1) +1; 這個(gè)式子叫做遞推式

實(shí)現(xiàn)代碼：

#define _CRT_SECURE_NO_WARNINGS#includeint Hanio_twice(int num){  if(1 == num)    return 1;  else    return 2 * Hanio_twice(num - 1) + 1;}int main(){  int num = 0;    scanf("%d", &num);//塔數(shù)  int ret = Hanio_twice(num);  printf("完成%d層的漢諾塔需要%d步\n", num, ret);  return 0;}

梵天說(shuō)假如把64個(gè)金片從A挪到C，那么這個(gè)世界就毀滅了(這里以上的代碼都不能輸出這個(gè)數(shù)字)
推理得：

2 ^ 64 - 1 -> 大約是1800億億步，這是個(gè)什么概念呢？
1年有365天，每天24小時(shí)，每小時(shí)是3600秒。如果1秒鐘移動(dòng)1次，如果把這64塊金片全部移動(dòng)完，大概需要5800億年。宇宙形成到現(xiàn)在也就138億年

三、漢諾塔打印步驟

使用遞歸打印1個(gè)n層的漢諾塔從A柱到C柱的所有步驟

原理：封裝1個(gè)函數(shù)Hanio(num, ‘A’, ‘B’, ‘C’)。

其中num是塔數(shù)；A、B、C，3個(gè)字符為抽象成的3個(gè)柱子。

如果只有1層那么輸出A；否則就有2種情況，其1是將n-1個(gè)碟子從A經(jīng)C到B。其2是將n-1個(gè)碟子從B經(jīng)A到C

實(shí)現(xiàn)代碼：

#define _CRT_SECURE_NO_WARNINGS#includevoid Hanio_Step(int n, char A, char B, char C){  if (1 == n)    printf("%c->%c\n", A, C);  else  {    Hanio_Step(n-1, A, C, B);    printf("%c->%c", A, C);    Hanio_Step(n-1, B, A, C);  }}int main(){  int n = 0;  scanf("%d", &n);  Hanio_Step(n, 'A', 'B', 'C');  return 0;}

步驟剖析圖：
注：圖片有點(diǎn)小大家可以放大點(diǎn)看
scanf -> 2

scanf -> 3 ???注：因?yàn)楹竺娴牟襟E太多了，所以省略一部分