暑期 每日一练acm题 第四题 经典汉诺塔 求递归算法 楼主泪奔啊
/***********************************************汉诺塔问题不多说了；输入： 输入正整数n表示有n个盘子在第一个柱子上；输出： move 移动的盘子标号 from 起始位置 to 移动后位置输入样例：3输出样例：move 1 from a to cmove 2 from a to bmove 1 from c to bmove 3 from a to cmove 1 from b to amove 2 from b to cmove 1 from a to c*****************************************************/#include<stdio.h>int main(){ int x[3][64] = {0},n,t = 0,t1 = 0,t2 = 0,k = 0,i,j,e,f; char q,p; scanf("%d",&n); for( i = 0 ; i < n ; i++ ) x[0][i] = n - i; if( n % 2 == 0) { while ( x[0][0]!=0 || x[1][0]!=0 ) { if( k == 0 ) { for( i = j = 0; x[j][i] != 1 ; i++ ) { if( x[j][i] == 0 ) { i = -1; j++; continue; } } x[j][i] = 0; switch(j) { case 0 : q = 'a'; break; case 1 : q = 'b'; break; case 2 : q = 'c'; break; } j++; if( j == 3 ) j -= 3; switch(j) { case 0 : p = 'a'; break; case 1 : p = 'b'; break; case 2 : p = 'c'; break; } for( i = 0 ; x[j][i] != 0 ; i++ ); x[j][i] = 1; k = 1; printf("move 1 from %c to %c\n",q,p); } else if( k == 1 ) { j++; if( j == 3 ) j -= 3; for( i = 1; x[j][i] != 0 ; i++ ) { if( x[j][0] == 0 ) { i = 0; break; } } i--; t1 = x[j][i]; e = j; e++; if( e == 3 ) e -= 3; for( f = 1; x[e][f] != 0 ; f++ ) { if( x[e][0] == 0 ) { f = 0; break; } } f--; t2 = x[e][f]; if( t1 == 0 ) t1 = 65; else if ( t2 == 0 ) t2 = 65; if( t1 > t2 ) { if( t1 != 65 ) i++; x[j][i] = x[e][f]; x[e][f] = 0; t = t2; switch(e) { case 0 : q = 'a'; break; case 1 : q = 'b'; break; case 2 : q = 'c'; break; } switch(j) { case 0 : p = 'a'; break; case 1 : p = 'b'; break; case 2 : p = 'c'; break; } } else { if( t2 != 65 ) f++; x[e][f] = x[j][i]; x[j][i] = 0; t = t1; switch(j) { case 0 : q = 'a'; break; case 1 : q = 'b'; break; case 2 : q = 'c'; break; } switch(e) { case 0 : p = 'a'; break; case 1 : p = 'b'; break; case 2 : p = 'c'; break; } } printf("move %d from %c to %c\n",t,q,p); k = 0; } } } else { while ( x[0][0]!=0 || x[1][0]!=0 ) { if( k == 0 ) { for( i = j = 0; x[j][i] != 1 ; i++ ) { if( x[j][i] == 0 ) { i = -1; j++; continue; } } x[j][i] = 0; switch(j) { case 0 : q = 'a'; break; case 1 : q = 'b'; break; case 2 : q = 'c'; break; } j--; if( j == -1 ) j += 3; switch(j) { case 0 : p = 'a'; break; case 1 : p = 'b'; break; case 2 : p = 'c'; break; } for( i = 0 ; x[j][i] != 0 ; i++ ); x[j][i] = 1; k = 1; printf("move 1 from %c to %c\n",q,p); } else if( k == 1 ) { j++; if( j == 3 ) j -= 3; for( i = 1; x[j][i] != 0 ; i++ ) { if( x[j][0] == 0 ) { i = 0; break; } } i--; t1 = x[j][i]; e = j; e++; if( e == 3 ) e -= 3; for( f = 1; x[e][f] != 0 ; f++ ) { if( x[e][0] == 0 ) { f = 0; break; } } f--; t2 = x[e][f]; if( t1 == 0 ) t1 = 65; else if ( t2 == 0 ) t2 = 65; if( t1 > t2 ) { if( t1 != 65 ) i++; x[j][i] = x[e][f]; x[e][f] = 0; t = t2; switch(e) { case 0 : q = 'a'; break; case 1 : q = 'b'; break; case 2 : q = 'c'; break; } switch(j) { case 0 : p = 'a'; break; case 1 : p = 'b'; break; case 2 : p = 'c'; break; } } else { if( t2 != 65 ) f++; x[e][f] = x[j][i]; x[j][i] = 0; t = t1; switch(j) { case 0 : q = 'a'; break; case 1 : q = 'b'; break; case 2 : q = 'c'; break; } switch(e) { case 0 : p = 'a'; break; case 1 : p = 'b'; break; case 2 : p = 'c'; break; } } printf("move %d from %c to %c\n",t,q,p); k = 0; } } } return 0;}
/****************************************************************汉诺塔的要求就是有A,B,C三个位置，最终目的就是从A->C基本算法有两种：递归和迭代你这种是递归void hanoi(int n, char A, char B, char C);n表示A位置最下面的盘子，B表示借助作用（不一定就是真正的B盘子（这个B表示借助），这个要想清楚）*****************************************************************/#include <stdio.h>void hanoi(int n, char A, char B, char C) //递归函数{ if(n == 1) { printf("Move sheet %d from %c to %c\n", n, A, C); //如果A位置只有一个盘子，不需要借助B，直接移动 } else { hanoi(n-1, A, C, B); //当n>1，要将最A最下面的盘子移置C，需要先将该盘子上面的n-1的盘子先移到B printf("Move sheet %d from %c to %c\n", n, A, C); //然后将n从A移置C hanoi(n-1, B, A, C); //接着就是将这n-1的盘子借助A从B->C //上述就是个将第n个盘子从A->C 完整的操作 //接下来就是将hanoi(n-1, B, A, C)也就是n-1个盘子继续操作，继续做递归循环n-1,n-2,n-3 .... 3,2,1直到只剩一个盘子 }}int main() { int n; printf("请输入盘数："); scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); return 0;}