国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP
漢諾塔問(wèn)題(三柱及四柱)詳解

 漢諾塔(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ò)程中每一步的做法步驟

漢諾塔問(wèn)題-步數(shù)

關(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   ( 

  )

  1. #include<stdio.h>
  2. #include<math.h>
  3. int main(){
  4. int n;
  5. scanf("%d",&n);
  6. printf("%d",(int)pow(2,n)-1);
  7. return 0;
  8. }

這里要注意范圍  如果n比較大的話可以用long long,時(shí)間上可以用快速冪優(yōu)化

漢諾塔問(wèn)題-步驟

關(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)單的

代碼

  1. #include<stdio.h>
  2. void hanoi(char a,char b,char c,int n){
  3. if(n==1){
  4. printf("%c->%c ",a,c);
  5. }
  6. else{
  7. hanoi(a,c,b,n-1);
  8. printf("%c->%c ",a,c);
  9. hanoi(b,a,c,n-1);
  10. }
  11. return ;
  12. }
  13. int main(){
  14. int n;
  15. scanf("%d",&n);
  16. hanoi('A','B','C',n);
  17. return 0;
  18. }

漢諾塔問(wèn)題拓展之四柱漢諾塔

在原來(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è)

的值  我們?cè)诿杜e的時(shí)候可能會(huì)枚舉到x等于1 n等于64的情況

那么   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)的了

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<string.h>
  5. #include<math.h>
  6. using namespace std;
  7. typedef long long ll;
  8. int f[100];
  9. int INF=100000;//設(shè)定最大值
  10. void sv(int n){
  11. f[1]=1;
  12. f[2]=3;
  13. for(int i=3;i<=n;i++){
  14. f[i]=INF;//f[i]先置為最大值 方便后邊比較
  15. for(int x=1;x<i;x++){
  16. if( (2*f[x]+pow(2,i-x)-1) <f[i])//小于f[i]的 才更新
  17. f[i]=2*f[x]+(int)pow(2,i-x)-1;
  18. }
  19. }
  20. }
  21. int n;
  22. int main(){
  23. sv(65);
  24. while(~scanf("%d",&n)){
  25. printf("%d\n",f[n]);
  26. }
  27. }

 

 

 

 

 

 

 

 

 

 

本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊舉報(bào)。
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
Hanoi塔
漢諾塔的圖解遞歸算法
算法詳解--漢諾塔
關(guān)于C語(yǔ)言漢諾塔問(wèn)題,當(dāng)程序執(zhí)行到001、002、003步時(shí),不知道具體是個(gè)什么步驟,求大神解惑!
用非遞歸算法解決Hanoi漢諾塔問(wèn)題
C|用遞歸和非遞歸方法求解漢諾塔問(wèn)題
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長(zhǎng)圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服