|
递归策略讲义2
3.例3：Hanoi（汉诺塔）问题：（hanoi.pas）
有N个圆盘，依其半径大小自下而上套在A柱上，每次只允许移动一个最上面的圆盘到另外的柱子上（B柱和C柱）。但不允许任何柱子出现大盘在上、小盘在下的情况。设计出将A柱上的N个盘子移到C柱上的方法。
以5个盘子为例子，先分析具体情况。
抽象分析：
1、目标：A盘上的N个盘子从A - - (B) - - > C ，可以用B作为过渡盘。实现：
① A柱上面的N - 1个盘子（1号——N - 1号）从A - - （C） - - 〉B
② 把A最下面最大的那一个盘子（第N个）从A - - - - - 〉C
③ 再把（1号——N - 1号）那N - 1个盘子从B - - - （A） - - 〉C
2、目标：解决1之②：把一个盘从一个柱子搬到另一个柱子上，很容易解决。
3、目标：解决1之①，实现：
①A柱上面（1号——N - 2号）N - 2个盘子从A - - （） - - 〉C
②A柱此时最下面的最大的盘子（第N - 1个）从A - - - - - 〉C
③再把（1号——N - 2号）那N - 2个盘子从C - - - （） - - - 〉B
4、目标：解决1之③，实现：
①B柱上面（1号——N - 2号）N - 2个盘子从B - - （） - - 〉A
②B柱此时最下面的最大的盘子（第N - 1个）从B - - - - - 〉C
③再把（1号——N - 2号）那N - 2个盘子从A - - - （） - - - 〉C
……
一直到递归的出口的条件：当盘只有一个的时候。
程序模式：
|
procedure movedisk(a, c);
begin
……
end;
procedure hanoi(其他参数，a, b, c);
begin
if …… then
else ……
end;
Begin
用户输入N的值；
hanoi(参数表)
End.
|
|
program hanoi;
var a, b, c: char;
n: integer;
procedure movedish(a, b: char);
begin
writeln(a, '---->', b);
end;
procedure hanoi(n: integer;a, b, c: char);
begin
if n = 1 then movedish(a, c)
else
begin
hanoi(n – 1（个数）, a（原位）, c（过渡位)，b(目标位)）；
movedish(a, c);
hanoi(n - 1, b, a, c);
end;{else}
end;{end of procedure movedish}
Begin
a := 'A';b := 'B';c := 'C';
write('n=');readln(n);
hanoi(n, a, b, c);
readln;
end.
|
练习：
1.用递归的算法把数组中的N个数按颠倒的次序重新存放。
Program turnover;
{用递归的算法把数组中的N个数按颠倒的次序重新存放.}
|
type arr = array [1 .. 100] of real;
var a: arr;n: integer;
procedure exchange(var x, y: real);
var z: real;
begin
z := x; x := y; y := z;
end;{exchange}
procedure upendarray(i, j: integer;var a: arr);
begin
if j - i = 0 then
else if j - i = 1 then exchange(a[i] , a[j])
else
begin
upendarray(i + 1, j - 1, a);
exchange(a[i] , a[j]);
end;{else}
end;{proc upendarray}
procedure getarr(var a: arr;var n: integer);
var i: integer;
begin
write('n=');readln(n);
write('a[i]:');
for i := 1 to n do
read(a[i]);
writeln;
end;
procedure printa(a: arr;n: integer);
var i: integer;
begin
write('a:');
for i := 1 to n do
write(a[i] : 8: 2);
writeln;
end;
Begin
getarr(a, n);
printa(a, n);
upendarray(1, n, a);
printa(a, n);
End.
|
2.用递归算法完成：有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第一张要翻的牌超过52为止。统计最后有几张牌正面朝上，以及它们的位置号。
|
Program poke;
type
ud = - 1 .. 1;
arr = array [1 .. 1000] of ud;
var a: arr;n: integer;
procedure getcards(var a: arr;var n: integer);
var i: integer;
begin
write('total cards n=');readln(n);
for i := 1 to n do
a[i] := 1; {all the cards are facing upwards}
end;{getdata}
procedure turncards(i: integer;var a: arr;n: integer);
{There are n cards,and we turn the cards from the i'th card }
var k, j: integer;
begin
if i = n then a[i] := 0 - a[i]
else
begin
k := n div i;
for j := 1 to k do a[i * j] := 0 - a[i * j];
turncards(i + 1, a, n);
end;
end;
procedure printcards(a: arr;n: integer);
var i: integer;
begin
write('The cards:');
for i := 1 to n do
if a[i] = - 1 then write('0')
else write('1');
writeln;
end;
procedure countcards(a: arr;n: integer);
var i, count: integer;
begin
count := 0;
write('All the upwards cards are:');
for i := 1 to n do
if a[i] = 1 then {upwards}
begin count := count + 1; write(i: 3); end;
writeln;
writeln('Total:', count);
end;
Begin
getcards(a, n);
printcards(a, n);
turncards(2, a, n);
printcards(a, n);
countcards(a, n);
End.
|
3、奇偶汉诺塔问题。有N个圆盘，编号为1到n，依其半径大小自下而上套在A柱上，每次只允许移动一个最上面的圆盘到另外的柱子上（B柱和C柱）。但不允许任何柱子出现大盘在上、小盘在下的情况。设计出将A柱上的N个盘子中编号为奇数的盘子移到B柱上，编号为偶数的盘子移到C柱上的方法。
|
Program ODD_even_hanoi;{ odd and even HANOI , N disks, from 1, odd to 2, even to 3 }
var N: integer;
total: longint;
Procedure Move(num, source, target: integer);
Begin
if num <= 0 then exit;
inc(total);
Writeln('[', total, ']:Move disk ', num, ' from ', source, ' to ', target, '.');
End;
Procedure Hanoi(count, source, target: integer);
Begin
if count <= 0 then exit;
Hanoi(count - 1, source, 6 - source - target);
Move(count, source, target);
Hanoi(count - 1, 6 - source - target, target);
End;
Procedure NewHanoi(count, target: integer);
Begin
if count <= 0 then exit;
Hanoi(count - 1, 1, 5 - target);
Move(count, 1, target);
Hanoi(count - 3, 5 - target, 1);
Move(count - 2, 5 - target, target);
NewHanoi(count - 3, 5 - target);
End;
BEGIN
Writeln;
Write('Please input N:'); Readln(N);
total := 0;
if N mod 2 = 0 then NewHanoi(N, 3)
else NewHanoi(N, 2);
Writeln('Total ', total, ' steps.');
Write('Press <ENTER> to return...'); Readln;
END.
|
|
|
|
|
|
