看了一下杭電的各種漢諾塔問題，遇到些奇奇葩葩的小問題，也有很多很好的思想，比如最后一題，來來回回的顛倒很有意思。總結(jié)一下；

Pro.ID 1207 :http://acm.hdu.edu.cn/showproblem.php?pid=1207

意思是給把原始的漢諾塔問題中的3根柱子改為4根。做了半天各種WA。查了一下，有一篇文章詳細(xì)講了一下，還做出了遞歸公式以及數(shù)學(xué)公式：

地址如下：http://www.cnblogs.com/fanzhidongyzby/archive/2012/07/28/2613173.html.

代碼如下：

?

#include<cstdio> #include<cmath> #include<algorithm> //F(n)=min(2*F(n-r)+2^r-1)，（1≤r≤n） using namespace std; int main() {int n,m;long long Min,f[65];f[1]=1;f[2]=3;for(int i=3;i<=65;i++){Min=99999999;for(int j=1;j<i;j++)Min=min(2*f[j]+pow(2.0,i-j)-1,Min*1.0);f[i]=Min;}while(~scanf("%d",&n))printf("%lld\n",f[n]);return 0; }

按照公式寫就是了，寫的時(shí)候需要注意一下精度問題。2^r可以寫為1<<r，不過因?yàn)閿?shù)字常數(shù)1默認(rèn)是32位，所以如果要使用位移的話，一定要先聲明一個(gè)longlong類型的變量來進(jìn)行位移，否則 就會(huì)出現(xiàn)溢出錯(cuò)誤，這個(gè)我糾結(jié)了一陣子，感覺沒錯(cuò)，一提交就WA，然后試了試64發(fā)現(xiàn)果然是負(fù)數(shù)。

?

哎，基礎(chǔ)還是不扎實(shí)啊。

用pow函數(shù)因?yàn)榉祷氐氖且粋€(gè)double類型，min函數(shù)里比較也是用double來做的，只是在最后賦值的時(shí)候取int型就可以，所以不會(huì)出錯(cuò)。

Pro.ID ?1995?漢諾塔V

http://acm.hdu.edu.cn/showproblem.php?pid=1995

這個(gè)是普通的漢諾塔，最優(yōu)的步數(shù)是2^n-1，只不過問的第i個(gè)盤子移動(dòng)的次數(shù)。依然是用遞歸，在紙上畫畫就能出來。

注意了，第i盤子，不用考慮底下的盤子，只用看之上的經(jīng)過一個(gè)柱子到達(dá)目的地。即F[n]=2*f[n-1]

代碼：

?

#include<iostream>using namespace std;int main() {__int64 s[61] = {0, 1};int n, i, t, m;for(i = 2; i < 61; i++)s[i] = s[i - 1] * 2;cin >> t;while(t--){cin >> n >> m;cout << s[n - m + 1] << endl;} }

Pro.ID?漢諾塔VI

?

http://acm.hdu.edu.cn/showproblem.php?pid=1996

是問所有步驟，注意不是最優(yōu)的，是全部（當(dāng)然不包括錯(cuò)誤的步驟）

每一個(gè)盤子可以放到3根柱子的任意一個(gè)，所以是3^n。比如正確的是直接從a->c,現(xiàn)在可以a->b然后在b->c,就是多了2種。每一個(gè)都多了2種，所以是3^n。

代碼：

?

#include<iostream> #include<math.h> #include<stdio.h> using namespace std; int main() {__int64 t,n,i;__int64 sum,a[100]={3,};while(cin>>t)while(t--){cin>>n;for(i=1;i<n;i++)a[i]=a[i-1]*3;cout<<a[n-1]<<endl;}return 0; }

Pro.ID 1997?漢諾塔VII

?

http://acm.hdu.edu.cn/showproblem.php?pid=1997

題目是說，給定某一時(shí)刻的三個(gè)柱子上的盤子，問這個(gè)是不是符合最優(yōu)解過程中某一時(shí)刻的狀態(tài)。

思想是：

對(duì)一個(gè)含有n個(gè)盤子，從A柱移動(dòng)到C柱借助B柱的漢諾塔，第n個(gè)盤子移動(dòng)到C柱過程是這樣子的：首先將其余的n-1個(gè)盤子移動(dòng)到B柱，然后第n個(gè)盤子直接移動(dòng)到C柱。在這過程中，第n個(gè)盤子只出現(xiàn)在A柱和C柱兩個(gè)柱子上，也即第n個(gè)盤子不可能出現(xiàn)在B柱上。因此對(duì)于當(dāng)前移動(dòng)的盤子，只需檢查其所在的柱子是否符合這個(gè)要求，如果出現(xiàn)在B柱上，則顯然進(jìn)入了錯(cuò)誤移動(dòng)中。這是本題求解思想精髓所在。

具體的內(nèi)容請(qǐng)參考這篇博客：http://blog.csdn.net/z690933166/article/details/8605261

代碼就不貼了，上邊這個(gè)博客里寫的很詳細(xì)。

Pro.ID 2064?漢諾塔III

http://acm.hdu.edu.cn/showproblem.php?pid=2064

還是遞推：num[i]=3*num[i-1]+2;

不解釋了，代碼如下：

?

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; unsigned long long num[36]; int main() { num[1]=2;num[2]=8;for(int i=3;i<=35;i++)num[i]=3*num[i-1]+2;int n;while(~scanf("%d",&n))cout<<num[n]<<endl;return 0; }

Pro.ID 2077?漢諾塔IV（參考了 zz_zigzag的博客）

?

http://acm.hdu.edu.cn/showproblem.php?pid=2077

好無聊啊，把上邊的規(guī)則給改了，只是最大的可以放上邊。其實(shí)感覺這個(gè)題目跟之前那個(gè)1027題目有點(diǎn)想通之處，在1027中說的是4根柱子，所以通用的這3個(gè)步驟其實(shí)并非最優(yōu)解：

?

（1）???????從1柱借助3…M柱子將n-(M-2)個(gè)盤子移動(dòng)到2柱上。

（2）???????將M-2個(gè)通過3…M-1柱簡單的移動(dòng)到M柱上【2*(M-2)-1步驟】。

（3）???????從2柱借助1，3…M-1柱子將n-(M-2)個(gè)盤子移動(dòng)到M柱上。

如果有n個(gè)盤子，則需要前n-1個(gè)挪到中間的盤子上，然后最大的盤子挪到最右面，需要兩步，把前（n-1）個(gè)盤子從左邊挪到中間是和從中間挪到右邊需要相同的次數(shù)。而a數(shù)組中存放的就是那個(gè)前n-1個(gè)盤子挪動(dòng)到相同位置需要的次數(shù)。結(jié)果即為a[i-1]*2+2。

所以我直接想成了是f[n]=2*f[n-1]+2，結(jié)果錯(cuò)了。【因?yàn)槭切枰猲-1個(gè)盤子前進(jìn)一步】

而求a數(shù)組需要用到遞推。公式為第i個(gè)為前n-1個(gè)移動(dòng)次數(shù)的三倍加一，簡化到兩個(gè)盤子，小的先移動(dòng)兩次到最右邊，大的移到中間，然后小的在移回中間，小的移動(dòng)了三次，而大的移動(dòng)了一次，就使他們?nèi)颗矂?dòng)了一個(gè)位置

所以代碼如下：

?

#include<stdio.h> int a[20]={0,1};int main() {int i,T;for(i=2;i<21;i++){a[i]=3*a[i-1]+1; }scanf("%d",&T);while(T--){scanf("%d",&i);printf("%d\n",2*a[i-1]+2);}return 0; }

Pro.ID 2175?漢諾塔IX

?

http://acm.hdu.edu.cn/showproblem.php?pid=2175

普通漢諾塔，問在最優(yōu)步驟中的第i步是哪一個(gè)盤子，跟1995那個(gè)題目剛好相反。不過這個(gè)有點(diǎn)像數(shù)論題。

這樣想，假設(shè)是4個(gè)盤子，考慮第三個(gè)，在第4步的時(shí)候?qū)?盤從A移動(dòng)到C【設(shè)目的地是B】，此時(shí)1,2盤在B上，設(shè)時(shí)間為T，然后將1,2盤移動(dòng)到C上，（需要3步）再把4盤移動(dòng)到B上，此時(shí)的格局為4盤在B上，1,2,3,在C上，距T過去了1+3=4步，那么3號(hào)盤什么時(shí)候再動(dòng)呢？把1,2移走，3就可以放到B上了，移走1,2需要花費(fèi)3個(gè)步驟，因此距T4+3+1也就是第8步，總體是第12步時(shí)，3號(hào)盤子會(huì)再次移動(dòng)。現(xiàn)在看明白了吧，就是基數(shù)倍的2^(i-1)時(shí)，i號(hào)盤子會(huì)移動(dòng)。

代碼如下：

?

#include<iostream> using namespace std; int main() {__int64 a[65];a[1]=1;__int64 i,n,r;__int64 m;for(i=2;i<=63;i++)a[i]=2*a[i-1];while(~scanf("%I64d%I64d",&n,&m),n+m){for(i=1;i<=n;i++){r=m/a[i];if(r%2==1&&m%a[i]==0)printf("%I64d\n",i);}}return 0; }

?

Pro.ID 2184?漢諾塔VIII

感覺這個(gè)題目非常的好，挺有意思的，問普通漢諾塔，N個(gè)盤子，在最優(yōu)解的第M步時(shí)，每個(gè)柱子上的盤子的狀態(tài)。

想了半天，也沒什么思路，但有一點(diǎn)是絕對(duì)可以確定的，就是一般解簡單漢諾塔過程的問題都是使用遞歸，可以得到全部過程，但是當(dāng)N稍微到10以上的時(shí)候必然遞歸很慢，所以直接遞歸模擬必然是錯(cuò)誤的，但是根據(jù)上一題目，第i個(gè)步移動(dòng)哪一個(gè)盤子中確定的，第K個(gè)盤子在 ?奇數(shù)*2^(K-1)時(shí)移動(dòng)可以得到些思想，必然是根據(jù)步數(shù)來確定盤子。

但是想了老半天也不太清楚那個(gè)遞歸改怎么寫，好像每一次判斷都要做除法到是可以確定某一個(gè)盤子，但是如何確定所有的盤子呢？糾結(jié)啊

查了半天，找到了一個(gè)大神的代碼。

地址在：http://blog.lchx.me/index.php/hdu-2184-%E6%B1%89%E8%AF%BA%E5%A1%94viii/

講的非常的詳細(xì)，我把思路以及代碼粘過來大家分享一下：

/*定義數(shù)組a，其中a[i]表示完成一次i層漢諾塔移動(dòng)的次數(shù)。 指針o,p,q分別表示三個(gè)位置。 起始狀態(tài)為n層都在o上，要往q方向移動(dòng)。 然后分成兩種情況： 1、 m<=a[n-1]; 此時(shí)，第n層沒機(jī)會(huì)移動(dòng)，那么就相當(dāng)于o上的n-1層往p上移動(dòng)。 使其狀態(tài)和起始狀態(tài)一致，我們要交換p和q。 2、 m>a[n-1]; 此時(shí)，先進(jìn)行到下面狀態(tài)，上面n-1層移動(dòng)到p位置，第n層移動(dòng)到q位置，消耗了a[n-1]+1次移動(dòng)。 接下來就變成p上的n-1層往q上移動(dòng)，只要交換o,p，令m=m-a[n-1]-1即可。通過上述操作，都可以得到第n層的位置，并且問題變成n-1層都在o上，要往q方向移動(dòng)。 */ #include<cstdio> #include<algorithm> #include<iostream> using namespace std; int main() {unsigned __int64 m,a[64];int row[3][66];a[1]=1;a[0]=0;for(int i=2;i<=63;i++)a[i]=a[i-1]*2+1;int t;scanf("%d",&t);while(t--){int n;scanf("%d %I64u",&n,&m);int *start,*mid,*end;start=row[0];mid=row[1];end=row[2];*start=*mid=*end=1;while(n){n--;if(m<=a[n]){*(start+*start)=n+1;//從第二個(gè)位置開始記錄盤子(*start)++;//第一個(gè)位置表示的是這個(gè)柱子一共有多少個(gè)盤子swap(end,mid);}else{*(end+*end)=n+1;(*end)++;swap(start,mid);m-=(a[n]+1);} }for(int i=0;i<3;i++){printf("%d",row[i][0]-1);for(int j=1;j<row[i][0];j++)printf(" %d",row[i][j]);printf("\n");}}return 0; }

?

Pro.ID?漢諾塔 X

http://acm.hdu.edu.cn/showproblem.php?pid=2511

進(jìn)一步加強(qiáng)條件，在求第m步時(shí)是哪個(gè)盤子動(dòng)，怎么動(dòng)。

必然遞歸啊。把上上個(gè)題目修改就可以了。具體的就不多說了，在注釋里有詳細(xì)解釋

?

#include<iostream> using namespace std;__int64 a[65]; void solve(int n,__int64 m,int start,int end) {int third=6-start-end;//得到第3跟柱子__int64 mid=a[n];if(m==mid) //如果是當(dāng)前盤子移動(dòng)，直接從start-->end{printf("%d %d %d\n",n,start,end);return ;}if(m<mid)//當(dāng)前盤子無法移動(dòng)，必然是上邊的某個(gè)盤子動(dòng)，并且移動(dòng)一定是到third號(hào)柱子上，遞歸求解solve(n-1,m,start,third);else//需要先移動(dòng)當(dāng)期盤子下部的盤子（參考2184題目）solve(n-1,m-mid,third,end); }int main() {__int64 m;a[1]=1;int n;for(int i=2;i<=63;i++)a[i]=2*a[i-1];int t;while(~scanf("%d",&t)){while(t--){scanf("%d%I64d",&n,&m);solve(n,m,1,3);}}return 0; }

?

最后一個(gè)Pro.ID ?2587:很O_O的漢諾塔

http://acm.hdu.edu.cn/showproblem.php?pid=2587

真心是跪了，

感謝hr_whisper的詳細(xì)講解，這里已經(jīng)寫的很清楚了：http://blog.csdn.net/murmured/article/details/9943947

?

?

總結(jié)

以上是生活随笔為你收集整理的杭电 汉诺塔问题总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。