資源簡介

程序設計與基本算法
山東青州第二中學 信息技術教研組
學習計算機語言不是學習的最終目的。語言是描述的工具，如何靈活地運用語言工具，設計和編寫能解決實際問題的程序，算法是程序設計的基礎。算法的作用是什么呢？著名數學家高斯（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個皇后。要求每行，每列，各對角線上的皇后都不能互相攻擊，給出所可能的擺法。

展開更多......

收起↑