import java.io.*;
public class Hanoi {
public static void main(String args[]) throws IOException {
int n;
BufferedReader buf;
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘数:");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n, 'A', 'B', 'C'); }
public void move(int n, char a, char b, char c) {
if(n == 1)
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
else {
move(n - 1, a, c, b);
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, b, a, c);
}
}
} 那位兄弟能帮我分析一下这个程序,我看不懂,分析不好。特别是那个递归,谢谢,
public class Hanoi {
public static void main(String args[]) throws IOException {
int n;
BufferedReader buf;
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘数:");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n, 'A', 'B', 'C'); }
public void move(int n, char a, char b, char c) {
if(n == 1)
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
else {
move(n - 1, a, c, b);
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, b, a, c);
}
}
} 那位兄弟能帮我分析一下这个程序,我看不懂,分析不好。特别是那个递归,谢谢,
看你的程序
else {
move(n - 1, a, c, b);
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, b, a, c);
}
当n递归到2的时候,这一段执行完n就成0了,继续递归...
也看不出这个程序是做什么的,就是从控制台输入一个数字,然后就是递归打印一些东西
请输入盘数:3
盘 1 由 A 移至 C
盘 2 由 A 移至 B
盘 1 由 C 移至 B
盘 3 由 A 移至 C
盘 1 由 B 移至 A
盘 2 由 B 移至 C
盘 1 由 A 移至 C
看完这个结果,我发现盘 3 由 A 移至 C
这句有点搞不懂
其实算法非常简单,当盘子的个数为n时,移动的次数应等于2^n – 1(有兴趣的可以自己证明试试看)。后来一位美国学者发现一种出人意料的简单方法,只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上,根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放 A B C;
若n为奇数,按顺时针方向依次摆放 A C B。
(1)按顺时针方向把圆盘1从现在的柱子移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;若圆盘1在柱子B,则把它移动到C;若圆盘1在柱子C,则把它移动到A。
(2)接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘。这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。
(3)反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。所以结果非常简单,就是按照移动规则向一个方向移动金片:
如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C汉诺塔问题也是程序设计中的经典递归问题,下面我们将给出递归和非递归的不同实现源代码。 ●汉诺塔算法的递归实现C++源代码#include <fstream>
#include <iostream>
using namespace std;
ofstream fout("out.txt");
void Move(int n,char x,char y)
{
fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}
void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}
int main()
{
fout<<"以下是7层汉诺塔的解法:"<<endl;
Hannoi(7,'a','b','c');
fout.close();
cout<<"输出完毕!"<<endl;
return 0;
}●汉诺塔算法的递归实现C源代码:#include<stdio.h>
void hanoi(int n,char A,char B,char C)
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B);
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C);
}
}
main()
{
int n;
printf("请输入数字n以解决n阶汉诺塔问题:\n");
scanf("%d",&n);
hanoi(n,'A','B','C');
}●汉诺塔算法的非递归实现C++源代码#include <iostream>
using namespace std; //圆盘的个数最多为64
const int MAX = 64; //用来表示每根柱子的信息
struct st{
int s[MAX]; //柱子上的圆盘存储情况
int top; //栈顶,用来最上面的圆盘
char name; //柱子的名字,可以是A,B,C中的一个
int Top()//取栈顶元素
{
return s[top];
}
int Pop()//出栈
{
return s[top--];
}
void Push(int x)//入栈
{
s[++top] = x;
}
} ; long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数 int main(void)
{
int n;
cin >> n; //输入圆盘的个数
st ta[3]; //三根柱子的信息用结构数组存储
Creat(ta, n); //给结构数组设置初值 long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
Hannuota(ta, max);//移动汉诺塔的主要函数 system("pause");
return 0;
} void Creat(st ta[], int n)
{
ta[0].name = 'A';
ta[0].top = n-1;
//把所有的圆盘按从大到小的顺序放在柱子A上
for (int i=0; i<n; i++)
ta[0].s[i] = n - i;
//柱子B,C上开始没有没有圆盘
ta[1].top = ta[2].top = 0;
for (int i=0; i<n; i++)
ta[1].s[i] = ta[2].s[i] = 0;
//若n为偶数,按顺时针方向依次摆放 A B C
if (n%2 == 0)
{
ta[1].name = 'B';
ta[2].name = 'C';
}
else //若n为奇数,按顺时针方向依次摆放 A C B
{
ta[1].name = 'C';
ta[2].name = 'B';
}
} long Pow(int x, int y)
{
long sum = 1;
for (int i=0; i<y; i++)
sum *= x; return sum;
} void Hannuota(st ta[], long max)
{
int k = 0; //累计移动的次数
int i = 0;
int ch;
while (k < max)
{
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch = ta[i%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " <<
"Move disk " << ch << " from " << ta[i%3].name <<
" to " << ta[(i+1)%3].name << endl;
i++;
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
if (k < max)
{ //把非空柱子上的圆盘移动到空柱子上,当两根柱子都为空时,移动较小的圆盘
if (ta[(i+1)%3].Top() == 0 ||
ta[(i-1)%3].Top() > 0 &&
ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << "Move disk "
<< ch << " from " << ta[(i-1)%3].name
<< " to " << ta[(i+1)%3].name << endl;
}
else
{
ch = ta[(i+1)%3].Pop();
ta[(i-1)%3].Push(ch);
cout << ++k << ": " << "Move disk "
<< ch << " from " << ta[(i+1)%3].name
<< " to " << ta[(i-1)%3].name << endl;
}
}
}
}
1个的时候当然是1次,2个的时候是3次,3个的时候就用了7次......
4个的时候是
“3个圆盘重新摞在一起的次数”+1次(一个盘移动的次数)+“3个圆盘重新摞在一起需要的次数”
=2x“3个圆盘重新摞在一起的次数”+1次
=15次。
那么,n个的时候是
2x“(n-1)个圆盘重新摞在一起的次数”+1次。
由于1 个的时候是1次,结果n个的时候为(2的n次方减1)次。
1个圆盘的时候 2的1次方减1
2个圆盘的时候 2的2次方减1
3个圆盘的时候 2的3次方减1
4个圆盘的时候 2的4次方减1
5个圆盘的时候 2的5次方减1
........
n个圆盘的时候 2的n次方减1
也就是说,n=64的时候是(2的64次方减1)次。
了解了数学问题再写到程序,抽象一下思维就很好理解了.
可能难以理解的是参数的传递问题,hanoi.move(n, 'A', 'B', 'C'); 这里确定了move这个方法的实参是A,B,C
public void move(int n, char a, char b, char c)
确定abc为形参,所以
move(n - 1, a, c, b);
move(n - 1, b, a, c);可以看做是改变了柱子的位置,即把问题归结为三个盘子的移动...谢谢楼主,我以前也想不通,看着上边这些不着边际的答案一气之下给想通了.这个例子还告诉我们递归分为递推和回推两个阶段你仔细看看结果是上下对称的!