c语言递归解决汉诺塔问题

红太狼 2023-06-03 13:58 13阅读 0赞

汉诺塔（Hanoi）是必须用递归方法才能解决的经典问题。

上帝创造世界时作了三根金刚石柱子，在第一根柱子上从下往上按大小顺序摞着64片黄金圆盘，上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放到第二根柱子上，

并且规定，每次只能移动一个圆盘，在小圆盘上不能放大圆盘。（即借助C把A上的圆盘移到B，并且从上到下圆盘增大）

\#include<stdio.h>

void Hanoi(int n, char A, char B, char C)  
\{  
if (n == 1)   \#如果只有一个直接从A移到B  
\{  
printf("Move %d: from %c to %c\\n",n,A,B);  
\}  
else  
\{  
Hanoi(n - 1, A, C, B);   \#把n-1个从A移到C借助B  
printf("Move %d: from %c to %c\\n",n,A,B);  
Hanoi(n - 1, C, B, A);   \#把n-1个从C移到B借助A  
\}  
\}  
int main()  
\{  
int n;  
char A = 'A';\#定义ABC表示三个柱子  
char B = 'B';  
char C = 'C';  
printf("Input the number of disks:");  
scanf("%d", &n);  
printf("Steps of moving 3 disks from A to B by means of C:\\n");  
Hanoi(n, A, B, C);  
return 0;  
\}

![1129246-20170409211129472-401346354.png][]

/\*根据上面的原理 增加一个计数器，并将步骤打印出来\*/

\#include<stdio.h>  
int i = 1;//定义全局变量，每次调用后加1  
void Hanoi(int n, char A, char B, char C)  
\{  
   
 if (n == 1)//如果只有一个直接从A移到B   "%2d-(%2d):%c==>%c\\n"  
 \{  
  printf("%2d-(%2d):%c==>%c\\n",i++,n,A,B);  
    
 \}  
 else  
 \{  
  Hanoi(n - 1, A, C, B);//把n - 1个从A移到C借助B  
    
   printf("%2d-(%2d):%c==>%c\\n", i++, n, A, B);  
  Hanoi(n - 1, C, B, A);//把n - 1个从C移到B借助B  
    
 \}  
   
\}  
int main()  
\{  
 int n;  
 char A = 'A'; //定义ABC表示三个柱子  
  char B = 'B';  
 char C = 'C';  
 printf("Please enter the number of discs:");  
 scanf("%d", &n);  
 Hanoi(n, A, B, C);  
 printf("\\tTotal:%d\\n",--i);  
 return 0;  
\}

转载于:https://www.cnblogs.com/didiaoxiaoguai/p/6686407.html

[1129246-20170409211129472-401346354.png]: /images/20230601/9c79db6d98ec457880cc94e3d37f82cf.png