资源简介

程序设计与基本算法
山东青州第二中学 信息技术教研组
学习计算机语言不是学习的最终目的。语言是描述的工具，如何灵活地运用语言工具，设计和编写能解决实际问题的程序，算法是程序设计的基础。算法的作用是什么呢？著名数学家高斯（GAUSS）从小就勤于思索。1785年，刚上小学二年级的小高斯，对老师出的计算题S=1+2+3+…+99+100，第一个举手报告S的结果是5050。班上的同学都采用依次逐个相加的“算法”，要相加99次;而小高斯则采用首尾归并，得出S=（1+100）*50的“算法”，只需加一次和乘一次，大大提高了效率。可见，算法在处理问题中的重要性。学习计算机编程，离不开基本算法。刚开始学习程序设计时，就应注重学习基本算法。
第一节　递推与递归算法
递推和递归是编程中常用的基本算法。在前面的解题中已经用到了这两种方法，下面对这两种算法基本应用进行详细研究讨论。
一、递推
递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。
[例1] 植树节那天，有五位参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。到底第一位同学植了多少棵树？
解：设第一位同学植树的棵数为a1，欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”这个规律，按照一定顺序逐步进行推算：
①a5=10;
②a4=a5+2=12;
③a3=a4+2=14;
④a2=a3+2=16;
⑤a1=a2+2=18;
Pascal程序：
Program Exam1;
Var i, a: byte;
begin
a:=10; {以第五位同学的棵数为递推的起始值}
for i :=1 to 4 do {还有4人，递推计算4次}
a:= a+2; {递推运算规律}
writeln(’The Num is’, a);
readln
end.
本程序的递推运算可用如下图示描述：
递推算法以初始{起点}值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）下一步的结果。
二、递归
递归算法是把处理问题的方法定义成与原问题处理方法相同的过程，在处理问题的过程中又调用自身定义的函数或过程。
仍用上例的计算植树棵数问题来说明递归算法：
解：把原问题求第一位同学在植树棵数a1，转化为a1=a2+2;即求a2；而求a2又转化为a2=a3+2; a3=a4+2; a4=a5+2;逐层转化为求a2,a3,a4,a5且都采用与求a1相同的方法；最后的a5为已知,则用a5=10返回到上一层并代入计算出a4；又用a4的值代入上一层去求a3;...,如此,直到求出a1。
因此：


其中求a x+1 又采用求ax 的方法。所以:
①定义一个处理问题的过程Num(x)：如果X < 5就递归调用过程Num(x+1);
②当递归调用到达一定条件(X=5)，就直接执行a :=10，再执行后继语句，遇End返回到调用本过程的地方，将带回的计算结果(值)参与此处的后继语句进行运算（a:=a+2）;
③最后返回到开头的原问题，此时所得到的运算结果就是原问题Num(1)的答案。
Pascal程序：
Program Exam1_1;
Var a: byte;
Procedure Num(x: integer);{过程Num(x)求x的棵数｝
begin
if x=5 then a:=10
else begin
Num(x+1); ｛递归调用过程Num(x+1)｝
a:=a+2 {求(x+1)的棵数｝
end
end;
begin
Num(1); ｛主程序调用Num(1)求第1个人的棵数｝
writeln(’The Num is ’, a);
readln
end.
程序中的递归过程图解如下：
参照图示，递归方法说明如下：
①调用原问题的处理过程时，调用程序应给出具体的过程形参值（数据）;
②在处理子问题中，如果又调用原问题的处理过程，但形参值应是不断改变的量(表达式）;
③每递归调用一次自身过程，系统就打开一“层”与自身相同的程序系列;
④由于调用参数不断改变，将使条件满足（达到一定边界），此时就是最后一“层”，不需再调用（打开新层），而是往下执行后继语句，给出边界值，遇到本过程的END，就返回到上“层”调用此过程的地方并继续往下执行;
⑤整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。
[例2] 用递归算法求X n 。
解：把X n 分解成: X 0 = 1 ( n =0 )
X 1 = X * X 0 ( n =1 )
X 2 = X * X 1 ( n >1 )
X 3 = X * X 2 ( n >1 )
…… ( n >1 )
X n = X * X n-1 ( n >1 )
因此将X n 转化为：
其中求X n -1 又用求X n 的方法进行求解。
①定义过程xn(x,n: integer)求X n ;如果n >1则递归调用xn (x, n-1) 求X n—1 ;
②当递归调用到达n=0，就执行t t :=1, 然后执行本“层”的后继语句;
③遇到过程的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:=tt*x;
④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序，输出tt的值。
Pascal程序：
Program Exam2;
Var tt, a, b: integer;
Procedure xn(x, n: integer); ｛过程xn(x, n)求xn ｝
begin if n=0 then tt:=1
else begin
xn(x, n-1); ｛递归调用过xn(x,n-1)求x n-1｝
tt:=tt*x
end;
end;
begin
write(’input x, n:’); readln(a,b); ｛输入a, b｝
xn(a,b); ｛主程序调用过程xn(a, b)求a b｝
writeln(a, ’^’, b, ’=‘, tt);
readln
end.
递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”(过程)去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。
如果处理问题的结果只需返回一个确定的计算值，可定义成递归函数。
[例3]用递归函数求x!
解：根据数学中的定义把求x! 定义为求x*(x-1)! ,其中求(x-1)! 仍采用求x! 的方法，需要定义一个求a！的过程或函数，逐级调用此过程或函数，即：
(x-1)!= (x-1)*(x-2)! ;
(x-2)!= (x-2)*(x-3)! ;
……
直到x=0时给出0!=1，才开始逐级返回并计算各值。
①定义递归函数：fac(a: integer): integer;
如果a=0，则fac:=1;
如果a>0，则调用函数fac:=fac(a-1)*a;
②返回主程序，打印fac(x)的结果。
Pascal程序：
Program Exam3;
Var x: integer;
function fac(a: integer): integer; ｛函数fac(a) 求a !｝
begin
if a=0 then fac:=1
else fac:=fac(a-1)*a ｛函数fac(a-1)递归求(a-1) !｝
end;
begin
write(’input x’); readln(x);
writeln(x, ’!=’, fac(x)); ｛主程序调用fac(x) 求x !｝
readln
end.
递归算法表现在处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。
[例4]用递归算求自然数A，B的最大公约数。
解：求最大公约数的方法有许多种，若用欧几里德发明的辗转相除方法如下：
①定义求X除以Y的余数的过程;
②如果余数不为0，则让X=Y，Y=余数，重复步骤①，即调用过程;
③如果余数为0，则终止调用过程;
④输出此时的Y值。
Pascal程序：
Program Exam4;
Var a,b,d: integer;
Procedure Gdd(x, y: nteger);{过程}
begin
if x mod y =0 then d :=y
else Gdd(y, x mod y) {递归调用过程}
end;
begin
write(’input a, b=’); readln(a, b);
Gdd(a, b);
writeln(’(’, a, ’,’, b, ’)=’, d );
readln
end.
简单地说，递归算法的本质就是自己调用自己，用调用自己的方法去处理问题，可使解决问题变得简洁明了。按正常情况有几次调用，就有几次返回。但有些程序可以只进行递归处理，不一定要返回时才进行所需要的处理。
[例5] 移梵塔。有三根柱A，B，C在柱A上有N块盘片，所有盘片都是大的在下面，小片能放在大片上面。现要将A上的N块片移到C柱上，每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，请输出移动方法。
解：先考虑简单情形。
如果N=3，则具体移动步骤为：
假设把第3步，第4步，第6步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）：
所以可按“N=2”的移动步骤设计：
①如果N=0，则退出，即结束程序;否则继续往下执行;
②用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程sub(n-1, a,b,c);
③将A柱上剩下的一片直接移到C柱上;
④用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程sub(n-1,b,c,a)。

Pascal程序：
Program Exam65;
Var x,y,z : char;
N, k : integer;
Procedure sub(n: integer; a, c , b: char);
begin
if n=0 then exit;
sub(n-1, a,b,c);
inc(k);
writeln(k, ’: from’, a, ’--＞’, c);
sub(n-1,b,c,a);
end;
begin
write(’n=’; readln(n);
k:=0;
x:=’A’; y:=’B’; Z:=’C’;
sub(n,x,z,y);
readln
end.
程序定义了把n片从A柱移到C柱的过程sub(n,a,c,b)，这个过程把移动分为以下三步来进行：
①先调用过程sub(n-1, a, b, c)，把(n-1)片从A柱移到B柱, C柱作为过渡柱;
②直接执行 writeln(a, ’--＞’, c），把A柱上剩下的一片直接移到C柱上，;
③调用sub(n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。
对于B柱上的(n-1)片如何移到，仍然调用上述的三步。只是把(n-1)当成了n，每调用一次，要移到目标柱上的片数N就减少了一片，直至减少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。
习题6.1
1.过沙漠。希望一辆吉普车以最少的耗油跨越1000 km的沙漠。已知该车总装油量500升，耗油率为1升/ km，必须利用吉普车自己沿途建立临时加油站，逐步前进。问一共要多少油才能以最少的耗油越过沙漠？
2.楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？
提示：如N级楼梯有S(N)种不同走法，则有：
S(N)=S(N-2)+S(N-1)
3.阿克曼(Ackmann)函数A(x,y)中，x,y定义域是非负整数，函数值定义为：
A(x,y)=y+1 (x = 0)
A(x,0)=A(x-1,1) (x > 0, y = 0)
A(x,y)=A(x-1, A(x, y-1)) (x, y > 0)
设计一个递归程序。
4.某人写了N封信和N个信封，结果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。可用下面公式：
Dn=(n—1) ( D n—１+D n—２)
写出递归程序。
第二节　回溯算法

在一些问题求解进程中，有时发现所选用的试探性操作不是最佳选择，需退回一步，另选一种操作进行试探，这就是回溯算法。
例[6.6] 中国象棋半张棋盘如下，马自左下角往右上角跳。现规定只许往右跳，不许往左跳。比如下图所示为一种跳行路线。编程输出所有的跳行路线，打印格式如下：
<1> (0,0)—(1,2)—(3,3)—(4,1)—(5,3)—(7,2)—(8,4)
解：按象棋规则，马往右跳行的方向如下表和图所示：
水平方向用x表示; 垂直方向用y表示。右上角点为x=8, y=4, 记为(8, 4) ; 用数组tt存放x方向能成行到达的点坐标;用数组t存放y方向能成行到达的点坐标;
①以(tt(K), t(k))为起点，按顺序用四个方向试探，找到下一个可行的点(x1, y1);
②判断找到的点是否合理 (不出界)，若合理，就存入tt和t中;如果到达目的就打印，否则重复第⑴步骤;
③如果不合理，则换一个方向试探，如果四个方向都已试过，就退回一步(回溯)，用未试过的方向继续试探。重复步骤⑴;
④如果已退回到原点，则程序结束。
Pascal程序：
Program Exam66;
Const xx: array[1..4] of 1..2 =(1,2,2,1);
yy: array[1..4] of -2..2=(2,1,-1,-2);
Var p: integer;
t, tt : array[0..10] of integer;
procedure Prn(k: integer);
Var i: integer;
Begin
inc(p); write(‘< ‘, p: 2, ’ > ‘, ’ ‘:4, ’0,0’);
for i:=1 to k do
write(‘— ( ‘, tt[ I ], ’ , ’, t[ I ], ’)’ );
writeln
End;
Procedure Sub(k: integer);
Var x1, y1, i: integer;
Begin
for I:=1 to 4 do
Begin
x1:=tt[k-1]+xx[ i ]; y1:=t[k-1]+yy[ i ];
if not( (x1 > 8) or (y1 < 0) or (y1 > 4) ) then
Begin
tt[k]:=x1; t[k]=y1;
if (y1=4) and (x1=8) then prn(k);
sub(k+1);
end;
end;
end;
Begin
p:=0; tt[0]:=0; t[0]:=0;
sub(1);
writeln( ‘ From 0,0 to 8,4 All of the ways are ’, p);
readln
end.

例[6.7] 输出自然数1到n所有不重复的排列，即n的全排列。
解：①在1～n间选择一个数，只要这个数不重复，就选中放入a数组中;
②如果这个数巳被选中，就在d数组中作一个被选中的标记 (将数组元素置1 );
③如果所选中的数已被占用（作了标记），就另选一个数进行试探;
④如果未作标记的数都已试探完毕，那就取消最后那个数的标记，退回一步，并取消这一步的选数标记，另换下一个数试探，转步骤①;
⑤如果已退回到0，说明已试探全部数据，结束。
Pascal程序：
Program Exam67;
Var p,n: integer;
a,d: array[1..500] of integer;
Procedure prn (t : integer);
Var i: integer;
Begin
write(‘ < ‘, p:3, ’ > ‘, ’ ‘:10);
for I:=1 to t do
write(a[ I ]:4);
writeln;
end;
Procedure pp(k: integer);
var x: integer;
begin
for x:=1 to n do
begin
a[k]:=x; d[x]:=1;
if k < n then pp(k+1)
else
begin
p:=p+1;
prn(k);
end;
end;
end;
Begin
write(‘Input n=‘); readln(n);
for p:=1 to n do d[p]=0;
p:=0;
pp(1);
writeln(‘All of the ways are ‘, p:6);
End.

例[6.8] 设有一个连接n个地点①—⑥的道路网，找出从起点①出发到过终点⑥的一切路径，要求在每条路径上任一地点最多只能通过一次。

解：从①出发，下一点可到达②或③，可以分支。具体步骤为：
⑴假定从起点出发数起第k个点Path[k]，如果该点是终点n就打印一条路径;
⑵如果不是终点n，且前方点是未曾走过的点，则走到前方点，定(k+1)点为到达路径，转步骤⑴;
(3)如果前方点已走过，就选另一分支点;
(4)如果前方点已选完，就回溯一步，选另一分支点为出发点;
(5)如果已回溯到起点，则结束。
为了表示各点的连通关系，建立如下的关系矩阵：

第一行表示与①相通点有②③，0是结束标志;以后各行依此类推。
集合b是为了检查不重复点。
Program Exam68;
const n=6;
roadnet: array[1..n, 1..n] of 0..n=( (2,3,0,0,0,0), (1,3,4,0,0,0), (1,2,4,5,0,0),
(2,3,5,6,0,0), (3,4,6,0,0,0), (4,5,0,0,0,0) );
var b: set of 1..n;
path: array[1..n] of 1..n;
p: byte;
procedure prn(k: byte);
var i: byte;
begin
inc(p); write(’<’, p:2, ’>’, ’ ’:4);
write (path[1]:2);
for I:=2 to k do
write (’--’, path[ i ]:2);
writeln
end;
procedure try(k: byte);
var j: byte;
begin
j:=1;
repeat
path[k]:=roadnet [path [k-1], j ];
if not (path [k] in b) then
begin b:=b+[path [k] ];
if path [k]=n then prn (k)
else try(k+1);
b:=b-[path [k] ];
end;
inc(j);
until roadnet [path [k-1], j ]=0
end;
begin
b:=[1]; p=0; path[1]:=1;
try(2);
readln
end.
习题[6.2]
1. 右下图所示的是空心框架,它是由六个单位正方体组成,问:从框架左下外顶点走到右上内顶点共有多少条最短路线

2.有M×N张(M行, N列)邮票连在一起,
但其中第X张被一个调皮的小朋友控掉了。下图是3×5的邮票的形状和编号。从这些邮票中撕出四张连在一起的邮票,问共有多少种这样四张一组的邮票 注:因为给邮票编了序号,所以1234和2345应该看作是不同的两组。
1 2 3 4 5
6 X 8 9 10
11 12 13 14 15
3.八皇后问题。在8*8的国际象棋盘上摆上8个皇后。要求每行，每列，各对角线上的皇后都不能互相攻击，给出所可能的摆法。

展开更多......

收起↑