UC知道一个c的汉诺塔问题？
来源：百度知道 编辑：UC知道 时间：2024/05/29 23:14:29
好心人啊，请阅读一下吧。
汉诺塔
这是个著名难题, 虽然说起来简单, 如果不用递归, 就很难解决。
题目介绍: 有三个塔, 每个都堆放 n 个盘子。开始时, 所有盘子均在塔A上,并且,盘从上到下, 按直径增大的次序放置。此难题的目的是设计一个盘子移动的序列。使得塔 A 上的所有盘子借助于塔 B 移动到塔 C 上。
有两个限制: 1. 一次只能搬动一个盘子。2. 任何时候不能把盘子放在比它小的盘子的上面。
解题方法如下进行. 若你只有一个盘子, 则是直接从 A 移到 C。若你有一个以上的盘子(设为 n 个), 则考虑三个步骤。
第一步, 把 n-1 个盘子从塔 A 搬到塔 B。第一步不违反说明的第一条限制(一次只能搬动一个盘子); 所有 n-1 个盘子不能作为一个整体一起搬动, 而是符合要求地从一个塔移到另一个塔上。注意尽管最终目标是把盘子从 A 搬到 C, 但是你可以用相同的算法把盘子从一个塔移到另一个塔上, 只要把源塔和目塔的名字改变一下即可。
第二步: 将剩下的一只盘 (也就是最大的一只) 直接从 A 塔搬到那个仍然空着的塔 C 。
第三步: 用第一步所说的方法, 再次将 B 塔上的盘搬到 C 塔。和第一步一样. 这一步实际上是由一序列更小的一次仅搬一个盘的操作组成。这一步是没有问题的, 因为 C 塔上仅有的一只盘是最大的盘。
这个算法达到了预期的目标, 即在 C 塔上按正确的顺序堆放了所有的盘。
注意: 前面的讨论是按照递归算法的标准形式表达的。显而易见的情形 (一只盘的情况)能够直接了当地解决。而其它情况, 将用一个"变简单"的参数(即减少一只盘)去调用函数。最终, 将到达仅有一个盘的情形, 这时, 递归就终止了。
这个例子的 C 语言程序如下。
main()
{
int disks;
void towers(int,char,char,char);
printf("Number of disks: ");
scanf("%d&
汉诺塔
这是个著名难题, 虽然说起来简单, 如果不用递归, 就很难解决。
题目介绍: 有三个塔, 每个都堆放 n 个盘子。开始时, 所有盘子均在塔A上,并且,盘从上到下, 按直径增大的次序放置。此难题的目的是设计一个盘子移动的序列。使得塔 A 上的所有盘子借助于塔 B 移动到塔 C 上。
有两个限制: 1. 一次只能搬动一个盘子。2. 任何时候不能把盘子放在比它小的盘子的上面。
解题方法如下进行. 若你只有一个盘子, 则是直接从 A 移到 C。若你有一个以上的盘子(设为 n 个), 则考虑三个步骤。
第一步, 把 n-1 个盘子从塔 A 搬到塔 B。第一步不违反说明的第一条限制(一次只能搬动一个盘子); 所有 n-1 个盘子不能作为一个整体一起搬动, 而是符合要求地从一个塔移到另一个塔上。注意尽管最终目标是把盘子从 A 搬到 C, 但是你可以用相同的算法把盘子从一个塔移到另一个塔上, 只要把源塔和目塔的名字改变一下即可。
第二步: 将剩下的一只盘 (也就是最大的一只) 直接从 A 塔搬到那个仍然空着的塔 C 。
第三步: 用第一步所说的方法, 再次将 B 塔上的盘搬到 C 塔。和第一步一样. 这一步实际上是由一序列更小的一次仅搬一个盘的操作组成。这一步是没有问题的, 因为 C 塔上仅有的一只盘是最大的盘。
这个算法达到了预期的目标, 即在 C 塔上按正确的顺序堆放了所有的盘。
注意: 前面的讨论是按照递归算法的标准形式表达的。显而易见的情形 (一只盘的情况)能够直接了当地解决。而其它情况, 将用一个"变简单"的参数(即减少一只盘)去调用函数。最终, 将到达仅有一个盘的情形, 这时, 递归就终止了。
这个例子的 C 语言程序如下。
main()
{
int disks;
void towers(int,char,char,char);
printf("Number of disks: ");
scanf("%d&
（1）首先第一个函数，
void move_disk(char src, char dst)
{
printf("%c ====> %c",src,dst);
} 的作用是输出src（从原来的盘子）到dst（目的盘），这样一种移
动方法。这个应该不难理解，因为汉诺塔的三个盘座是用三个字符标
记的，'A','B','C'。
（2）第二个函数：
void towers(int n, char src, char mid, char dst)
{
void move_disk(char,char);
if (n==1)
{
move_disk(src,dst);
return;
}
towers(n-1,src,dst,mid);
move_disk(src,dst); //这里就输出移动路线了！
towers(n-1,mid,src,dst);
}
递归结束的条件可以称为临界条件，或者是阀值。本题的阀值就
是n=1了，因为要移动多个盘子是基于移动一个盘子的。
使用递归的条件是：原问题与其子问题的求解原理和过程是相同
的。比如本题，移动n个盘子和移动n-1个盘子的原理是相同的，所不
同的只是初始位置和结束位置。也就是src,dst,mid这三个盘座的位
置。
再仔细看一下递归的基本原理那部分，从基本的求n！看起。慢
慢来理解！o(∩_∩)o...
int jiecheng(int data)
{
if(data==1)
return data;
else
return data*jiecheng(data-1);
}
这是个递归示例函数,简单地说,这里的递归就是把底层的