3個漢諾塔問題A—>C

移動次數2^n-1

1. hannoni(int n,char a,char b,char c)把n個盤子借助b,從a移動到c
2. move(int n,char a,char c)把第n個盤子,從a移動到c

#include<iostream> 
#include<cmath>
using namespace std;
//漢諾塔問題A--->C
//2^n-1次移動次數 //把第n個盤子從a移動到c 
void move(int n,char a,char c)
{cout  <<"把"<<n<<"號盤子從"<<a<<"移到"<<c<<endl; 
}
//把n個盤子a借助b移到c 
void hannoni(int n,char a,char b,char c)
{if(n==1)//只需要移動一次 move(1,a,c);else{//a-->b   n-1hannoni(n-1,a,c,b);move(n,a,c);//b--->c n-1hannoni(n-1,b,a,c);
}
} 
int main()
{int n;cout <<"請輸入要移動的盤子數"<<endl; cin>>n;hannoni(n,'A','B','C');return 0;
}

要點:A—>C
1.當n==1時直接從A移動到C
2.當n>1時,
先把n-1個盤子借助C,從A移動到B
再把第n個盤子從A移動到C
最后,借助A,把n-1個盤子從B移動到C

漢諾塔移動次數

要點:A—>C
1.當n==1時直接從A移動到C 移動一次
2.當n>1時,
先把n-1個盤子借助C,從A移動到B 移動n-1次
再把第n個盤子從A移動到C 移動一次
最后,借助A,把n-1個盤子從B移動到C 移動n-1次
所以,
n=1,T(N)=1
n>1,T(N)=2T(N-1)+1

代碼示例

#include<iostream>
#include<cmath>
using namespace std;int count(int n){int number=0;if(n<=0)return -1;if(n==1)number=1;elsenumber=2*count(n-1)+1;return number;}int main()
{int n;cout <<"輸入要移動的盤子個數"<<endl; cin>>n;cout<<count(n)<<endl;return 0;}