发布时间 : 星期四 文章pascal中级教程第二章递归与递推更新完毕开始阅读0fc19442336c1eb91a375db7
准备。
从第一个字符开始到最后一个字符重复上面的过程，检查处理完毕。
输出时考虑到不增加嵌套的层数，以就近的原则，将出现不匹配的一个括号时，输出两个匹配的括号。
2.7 新汉诺塔
源程序名 hanoi.???（pas, c, cpp） 可执行文件名 hanoi.exe 输入文件名 hanoi.in 输出文件名 hanoi.out 【问题描述】
设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。 现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。 移动时有如下要求： ·一次只能移一个盘；
·不允许把大盘移到小盘上面。 【输入】
文件第一行是状态中圆盘总数；
第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号； 第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。
【输出】 每行一步移动方案，格式为：move I from P to Q 最后一行输出最少的步数。 【样例】
Hanoi.in 5 3 3 2 1 2 5 4 0
Hanoi.out
move 1 from A to B move 2 from A to C move 1 from B to C move 3 from A to B
1 2 move 1 from C to B 3 5 4 3 move 2 from C to A 1 1 move 1 from B to C 7 【算法分析】 要从初始状态到目标状态．就是要把每个圆盘分别移到自己的目标状态。
怎样才能保证总的移动步数最少呢?关键是首先考虑把编号最大的圆盘移到它的目标状态，因为编号最大的圆盘移到目标位置后就不再移动了，而在编号最大的圆盘没有移到目标之前，编号小的圆盘可能还要移动，即使它已在目标状态。所以编号最大的圆盘一旦固定，对以后的移动不会造成影响。最大的移动好后，再考虑剩余的没有到达目标状态的最大号圆盘??直到最小的编号为1的圆盘到目标状态为止。
设计一个移动过程：move(k,w)，表示把编号k的圆盘移到w柱。
2.8 排序集合
源程序名 sort.???（pas, c, cpp） 可执行文件名 sort.exe 输入文件名 sort.in 输出文件名 sort.out 【问题描述】 对于集合N={1,2,?,n}的子集，定义一个称之为“小于”的关系： 设S1={X1,X2,?,Xi}，（X1 输出文件仅一行，使该子集的元素，由小到大排列。空集输出0。 【样例】 sort.in sort.out 3 4 1 2 3 【算法分析】 我们知道，n个元素构成的集合有2n种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k，输出第k个集合。所以排序的规则是本题的关键，其实很简单，当n＝3时，8个集合排序如下：{}<{1}<{l,2}<{l,2,3}<{1,3}<{2}<{2,3}<{3}，你发现规律了吗?具体算法为：先推出第k小的一个子集的第一个数宇是多少，第一个数字确定了之后，再推出第二个数字，从第一个数字加1一直计算累加集合个数，直到得到不超过k的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。要注意：终止条件是有了n个数字或者第i个数字为空，这时递推终止，输出最后的结果。 2.9 青蛙过河 源程序名 frog.???（pas, c, cpp） 可执行文件名 frog.exe 输入文件名 frog.in 输出文件名 frog.out 【问题描述】 有一条河，左边一个石墩(A区)上有编号为1，2，3，4，?，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图2—5所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为： h个石礅 河心石礅D 左岸石礅A 荷叶C k个荷叶 右岸石礅B (1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)； (2)青蛙可以：A→B(表示可以从A跳到B，下同)，A→C，A→D，C→B，D→B，D→C，C→D； (3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。 你的任务是对于给出的h，k，计算并输出最多能有多少只青蛙可以根据以上规则顺利 过河? 【样例】 frog.in 2 3 {河中间有2个石礅，3个荷叶} frog.out 16 {最多有16只青蛙可以按照规则过 河} 【算法分析】 结论为：f(h,k)=2h(k+1) 从具体到一般，推导过程如下： f(0,0)=1 f(0,k)=k+1; f(1,k)=2(k+1); （如k=3时，有4只青蛙可以过河） （递推思想） ?? 2 依此类推：f(2,k)=(2*(k+1))*2=2(k+1); ??