2016-03-19 17:01:35
问题描述:
假设有三个命名为 A B C 的塔座 ，在塔座A上插有n个直径大小不相同，由小到大编号为1 ，2 ，3 ，··· ，n的圆盘，要求将A座上的圆盘移至塔座C
并按同样的顺序叠排,圆盘移动必须遵守下列规则：
1：每次只能移动一个圆盘 2：圆盘可以插在任意一个塔座上 3：任何时刻都不能将一个较大的圆盘放在一个较小的圆盘上
f(n):原始A柱有n个圆盘,全部移动到C柱的移动次数
我们要将编号为n的圆盘移动到C柱上,首先须得将A柱上的n-1个圆盘从A->B(途中可能经过C柱),这需要f(n-1)次移动,将第n个圆盘移动到C柱需要一次移动,
再把B柱上的n-1个圆盘从B->C(途中可能经过A柱)仍然需要f(n-1)次移动
从而:f(n) =2*f(n-1)+1(n>=2),f(1) = 1递推可得
f(n) = 2^n -1
移动的方式:
思路:
当n=1,圆盘1直接从从A移动到C(此时的A、C是相对的)
否则,先将A上的前n-1个圆盘从A借助C移动到B，然后将第n个圆盘直接移动到柱C
对B柱上的n-1个圆盘进行相似的操作移动到C,这是很明显的递归
//（1）
#include <stdio.h>
void move(char x,char y,int i)
{
static int j = ;
printf("%d: %d from %c to %c\n",++j,i,x,y);
} void Hanoi(char x,char y,char z,int n)
{
if(n == )
{
move(x,z,n);
return;
}
else{
Hanoi(x,z,y,n-);
move(x,z,n);
Hanoi(y,x,z,n-);
}
} int main()
{
int n;
scanf("%d",&n);
Hanoi('A','B','C',n);
return ;
}
//(2)
#include <stdio.h>
void move(int n,char A,char B,char C)
{
if(n == )
{
printf("%d:%c-->%c\n",n,A,C);
return;
}
else{
move(n-,A,C,B);
printf("%d:%c-->%c\n",n,A,C);
move(n-,B,A,C);
}
}
int main()
{
int n;
scanf("%d",&n);
move(n,'A','B','C');
return ;
}
参照：http://www.cnblogs.com/liangyan19910818/archive/2011/08/26/2153926.html#3259652