來源：http://a.nxw.so/1iDyQD

一、前言

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

二、漢諾塔打印步數(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;}

梵天說假如把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太多了，所以省略一部分

版權(quán)申明：內(nèi)容來源網(wǎng)絡(luò)，版權(quán)歸原創(chuàng)者所有。除非無法確認(rèn)，都會(huì)標(biāo)明作者及出處，如有侵權(quán)，煩請告知，我們會(huì)立即刪除并致歉!