递归4--汉诺塔问题

一、总结：

1、递归终止条件n==1的时候移动的是第一块盘子，

if(n==1){//只需移动一个盘子
cout<<src<<"->"<<dest<<" 移动的是第："<<n<<" 块盘子"<<endl;//直接将盘子从src移动到dest即可
return ;
}
Hanoi2(n-1,src,dest,mid);//先将n-1个盘子从src移动到mid
cout<<src<<"->"<<dest<<" 移动的是第："<<n<<" 块盘子"<<endl;//再将一个盘子从src移动到dest
Hanoi2(n-1,mid,src,dest);//先将n-1个盘子从mid移动到dest

2、最后三句话中间的那句话才是移动其它盘子

二、题目

三、分析

n=3 时候的递归过程及移动路径分析

四、代码

 1 #include <iostream>
 2 using namespace std;
 3 void Hanoi(int n,char src,char mid,char dest)
 4 //将src座上的n个盘子，以mid为中转，移动到dest座 
 5 {
 6     if(n==1){//只需移动一个盘子 
 7         cout<<src<<"->"<<dest<<endl;//直接将盘子从src移动到dest即可
 8         return ; 
 9     } 
10     Hanoi(n-1,src,dest,mid);//先将n-1个盘子从src移动到mid
11     cout<<src<<"->"<<dest<<endl;//再将一个盘子从src移动到dest
12     Hanoi(n-1,mid,src,dest);//先将n-1个盘子从mid移动到dest 
13     
14     return ;
15 } 
16 
17 void Hanoi2(int n,char src,char mid,char dest)//输出移动的盘子号 
18 //将src座上的n个盘子，以mid为中转，移动到dest座 
19 {
20     if(n==1){//只需移动一个盘子 
21         cout<<src<<"->"<<dest<<" 移动的是第："<<n<<" 块盘子"<<endl;//直接将盘子从src移动到dest即可
22         return ; 
23     } 
24     Hanoi2(n-1,src,dest,mid);//先将n-1个盘子从src移动到mid
25     cout<<src<<"->"<<dest<<" 移动的是第："<<n<<" 块盘子"<<endl;//再将一个盘子从src移动到dest
26     Hanoi2(n-1,mid,src,dest);//先将n-1个盘子从mid移动到dest 
27     
28     return ;
29 } 
30 int main(){
31     //Hanoi(3,'a','b','c');//将3个盘子从a移动到c 
32     Hanoi2(3,'a','b','c');//将3个盘子从a移动到c 
33     return 0;
34 }