斐波那契
漢諾塔
0 1 1 2 3 5 8 13 21
int fibonacci(int a){
if(a==0)
return 0;
else if(a==1)
return 1;
else
return fibonacci(a-1)+fibonacci(a-2);
}
我也來搞一下這個 漢諾塔的調調：
先來講一下這個 東西怎麼玩兒
需要做的事情是把 1針上的盤子都放到3針上面。
要求每次只能移動一個盤子，並且只能是大盤子在下，小盤子在上，對於每兩個盤子來說。
所以為了實現這一目的
Step1: 把1針上的最後一個盤子放到3針上面。//移動
【前提：這樣就需要先把n-1盤子放到2針上面。 也就是Step0:】
Step0:這樣就需要先把n-1盤子放到2針上面。//邏輯
//對於代碼，這句話本質上相當於 2針是目標，也就是 2針上是需要盛盤子的針。所以2針是目的針，要把n-1個盤子從1針放到2針上，借助3針，所以abc三根針的關系在hanoi(n,a,b,c)的本質是：a作為移出針，b作為借助針，c作為目標針。所以 這裡面這句話應該寫作：hanoi(n-1,a,c,b);
Step1:
Step2:前提把n-2個盤子放到1針上。//邏輯
所以從2針出來，放到1針上，借助，3針。這幾個參數就是213.
Step3:把2針上的最後一個盤子放到3針上。//移動
然後 把n-3個盤子放到2針上面，也就是 Step0:
然後再 Step1
所以 大概是這樣的：
void hanoi(int n,int a,int b,int c){
if(n==1)
printf("%d -> %d \n",a,c);//移動
else{
hanoi(n-1,a,c,b);
printf("%d -> %d \n",a,c);//移動
hanoi(n-1,b,a,c);
}
}
運行結果：
代碼：
/**
#include <iostream>
int fibonacci(int);
void hanoi(int n ,int a,int b, int c);
int main(int argc, char** argv) {
//printf("%d",fibonacci(1));
hanoi(3,1,2,3);
return 0;
}
void hanoi(int n,int a,int b,int c){
if(n==1)
printf("%d -> %d \n",a,c);//移動
else{
hanoi(n-1,a,c,b);
printf("%d -> %d \n",a,c);//移動
hanoi(n-1,b,a,c);
}
}
/**
返回第a個數的大小，從0開始。
*/
int fibonacci(int a){
if(a==0)
return 0;
else if(a==1)
return 1;
else
return fibonacci(a-1)+fibonacci(a-2);
}
*/
試試4個的：
大概那眼睛移動了一下，應該是沒有問題的。
再來回顧一下代碼：
/**
n代表要移動的盤子的個數。
a 代表從哪跟針往外移出。 移出針
b代表借助哪跟針。 借助針
c代表要移動到哪根針。 目的針
*/
void hanoi(int n,int a,int b,int c){
if(n==1)
printf("%d -> %d \n",a,c);//移動
else{
hanoi(n-1,a,c,b);//邏輯
printf("%d -> %d \n",a,c);//移動
hanoi(n-1,b,a,c);//邏輯
}
}
如果只有一個盤子，就把盤子直接從1移動到3.
否則就把n-1個盤子移動到2.
然後把盤子放到3上。
再把剩下的盤子從2移到3上。
應該可以開始默寫了
Hanoi(int n,int from,int rent,int destination){
If(n==1)
printf("%d -> %d",from,destination);
Else{
Hanoi(n-1,from,destination,rent);
Printf("%d ->%d",from,destination);
Hanoi(n-1,rent,from,destination);
}
不看還是會忘的。總之這就是這麼個事兒，算法麼~大都是背下來的。哪有那麼多真正會的人。。。
以下源代碼：
#include <iostream>
int fibonacci(int);
void hanoi(int n ,int a,int b, int c);
int main(int argc, char** argv) {
//printf("%d",fibonacci(1));
hanoi(4,1,2,3);
return 0;
}
/**
n代表要移動的盤子的個數。
a 代表從哪跟針往外移出。 移出針
b代表借助哪跟針。 借助針
c代表要移動到哪根針。 目的針
*/
void hanoi(int n,int a,int b,int c){
if(n==1)
printf("%d -> %d \n",a,c);//移動
else{
hanoi(n-1,a,c,b);//邏輯
printf("%d -> %d \n",a,c);//移動
hanoi(n-1,b,a,c);//邏輯
}
}
/**
返回第a個數的大小，從0開始。
*/
int fibonacci(int a){
if(a==0)
return 0;
else if(a==1)
return 1;
else
return fibonacci(a-1)+fibonacci(a-2);
}
