漢諾塔(Hanoi Tower),又稱河內(nèi)塔,傳說(shuō)大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子,在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定,任何時(shí)候,在小圓盤上都不能放大圓盤,且在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。問(wèn)應(yīng)該如何操作?
需要求兩個(gè)問(wèn)題,一是求所需要的步數(shù),二是求移動(dòng)過(guò)程中每一步的做法步驟
關(guān)于步數(shù) 是個(gè)很簡(jiǎn)單的問(wèn)題 高中大家都學(xué)過(guò) 可能也做過(guò)類似的題
如果a上有n個(gè)盤子 要借助b柱子將他們移動(dòng)到c上 那么 我們?cè)O(shè)總共需要移動(dòng)步數(shù)為F(n)
那么 我們先將 最上面的n-1個(gè)盤子 借助c柱子移動(dòng)到b上 毫無(wú)疑問(wèn)需要步數(shù) F(n-1)
那么 我們?cè)侔補(bǔ)上剩下的一個(gè)盤子 移動(dòng)到c上 需要一步 然后再把b上的n-1個(gè)借助a移動(dòng)到c上 需要F(n-1)
到這就完成了所有的移動(dòng) 總共步數(shù)F(n)=2*F(n-1)+1
n=1的時(shí)候需要一步 所以 n就需要 2的n次方再減1 (
- #include<stdio.h>
- #include<math.h>
- int main(){
- int n;
- scanf("%d",&n);
- printf("%d",(int)pow(2,n)-1);
- return 0;
- }
這里要注意范圍 如果n比較大的話可以用long long,時(shí)間上可以用快速冪優(yōu)化
關(guān)于 步驟,同樣的遞歸思想
我們假設(shè) 函數(shù) hanoi ( a , b , c , n )代表 把a(bǔ)上的n個(gè)盤子借助b移動(dòng)到c的步驟
那么 如果n==1 則步驟就是 a->c 一步就好了
n不等于1 的時(shí)候 我們先把a(bǔ)上n-1個(gè)盤子借助c移動(dòng)到b上 就是 hanoi ( a , c , b , n-1 )
再把a(bǔ)上最后一個(gè)挪到c a->c
最后再把 b上n-1個(gè)盤子借助a挪到c上 hanoi ( b , a , c , n-1 )
整個(gè)過(guò)程就完成了 主要是要理解遞歸的思想 理解了思想 遞歸的程序?qū)懫饋?lái)是最簡(jiǎn)單的
代碼
- #include<stdio.h>
- void hanoi(char a,char b,char c,int n){
- if(n==1){
- printf("%c->%c ",a,c);
- }
- else{
- hanoi(a,c,b,n-1);
- printf("%c->%c ",a,c);
- hanoi(b,a,c,n-1);
- }
- return ;
- }
- int main(){
- int n;
- scanf("%d",&n);
- hanoi('A','B','C',n);
- return 0;
- }
在原來(lái)的問(wèn)題上再加一個(gè)柱子 其他的條件不變
將a柱上的n個(gè)圓盤 移到d柱上 同樣大的不能壓到小的
我們同樣用三柱的方法分析問(wèn)題
1、我們?cè)O(shè)將a柱最上邊的x個(gè)圓盤(1<=x<n)借助b、d兩個(gè)柱子移動(dòng)到c上需要F[ x ] 步
2、然后我們?cè)侔補(bǔ)柱上剩下的n-x個(gè)盤借助b柱移動(dòng)到d柱上(不能借助c c上的都小),那么這一步驟和三柱漢諾塔是一樣的,我們剛才算過(guò)了,是
3、最后我們?cè)侔裞上的x個(gè)圓盤借助a、b移動(dòng)到d上 同樣需要F[ x ]步
那么 總步數(shù) F[n]=2*F[ x ] +
(這里 注意一下這個(gè)x的取值范圍啊 是 (1<=x<n) x不能為0 也不能為n
如果x為0的話,那么相當(dāng)于我們第一步和第三步?jīng)]做任何事,只做了第二步,那么豈不是和三柱的情況一樣了 ,有一個(gè)柱子都沒(méi)用,肯定不是最優(yōu)解。
如果x為n的話 那我們第二步?jīng)]做任何事 第一步和第三步 先借助b、d挪到了c 再借助 a、b挪到了d 那干嘛不一步直接挪到d,所以也肯定不是最優(yōu)解)
這個(gè)式子關(guān)鍵是F[ x ]的取值 F[ 1 ] = 1 F[ 2 ] = 3 這兩個(gè)我們不用說(shuō) 很清楚
那么從n=3 開始 我們求解時(shí)利用前邊已知的F[ x ] 挨個(gè)枚舉 留下最小值 就是答案了
在放代碼之前還有個(gè)小問(wèn)題 這里由于需要計(jì)算一個(gè)
那么 2的63次方 我們知道 longlong也存不下 可能有的同學(xué)會(huì)考慮高精度大數(shù)了 其實(shí)不用 我們要知道 我們?cè)诿杜e過(guò)程中 是想找到那個(gè)最小的數(shù) 那么 過(guò)大的數(shù)字 我們雖然存不下 其實(shí)他對(duì)我們也沒(méi)啥用處
而且 事實(shí)證明 64以內(nèi)的所需步數(shù)是很小的 64的時(shí)候只需要18433步
那么我們只要設(shè)定一個(gè)最大值 比如是十萬(wàn) 然后 枚舉過(guò)程中 比這個(gè)值小的 我們才更新
這樣一來(lái) int就可以解決64以內(nèi)的了
- #include<stdio.h>
- #include<iostream>
- #include<algorithm>
- #include<string.h>
- #include<math.h>
- using namespace std;
- typedef long long ll;
- int f[100];
- int INF=100000;//設(shè)定最大值
- void sv(int n){
- f[1]=1;
- f[2]=3;
- for(int i=3;i<=n;i++){
- f[i]=INF;//f[i]先置為最大值 方便后邊比較
- for(int x=1;x<i;x++){
- if( (2*f[x]+pow(2,i-x)-1) <f[i])//小于f[i]的 才更新
- f[i]=2*f[x]+(int)pow(2,i-x)-1;
- }
- }
- }
- int n;
- int main(){
- sv(65);
- while(~scanf("%d",&n)){
- printf("%d\n",f[n]);
- }
- }
聯(lián)系客服