所謂枚舉法，指的是從可能的解的集合中壹壹枚舉各元素， 用題目給定的檢驗條件判定哪些是無用的，哪些是有用的。能使命題成立，即為其解。
有些問題可以用循環語句和條件語句直接求解，有些問題用循環求解時循環次數太多，無法編寫程序，怎麽辦？下面是用“千軍萬馬過獨木橋，適者存”的方式實現窮舉策略的。
6.2 典型例題與習題
例1.將2n個0和2n個1，排成壹圈。從任壹個位置開始，每次按逆時針的方向以長度為n+1的單位進行數二進制數。要求給出壹種排法，用上面的方法產生出來的2n+1個二進制數都不相同。
例如，當n=2時，即22個0和22個1排成如下壹圈：
比如，從A位置開始，逆時針方向取三個數000，然後再從B位置上開始取三個數001，接著從C開始取三個數010，...可以得到000，001，010，101，011，111，110，100***8個二進制數且都不相同。
程序說明：
以n=4為例，即有16個0，16個1，數組a用以記錄32個0，1的排法，數組b統計二進制數出現的可能性。
程序清單
PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1; A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27
WHILE A[J]=1 DO J:=J-1;
( A[J]:=1 )
FOR I:=J+1 TO 27 DO ( A[i]:=0 )
FOR I:=0 TO 31 DO B[I]:=0;
FOR I:=1 TO 32 DO
BEGIN
( S:=0)
FOR K:=I TO I+4 DO S:=S*2+A[k];
( B[S]:=1 )
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF ( S=32 ) THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.
例2：在A、B兩個城市之間設有N個路站(如下圖中的S1，且N<100)，城市與路站之間、路站和路站之間各有若幹條路段(各路段數<=20，且每條路段上的距離均為壹個整數)。
A，B的壹條通路是指：從A出發，可經過任壹路段到達S1，再從S1出發經過任壹路段，…最後到達B。通路上路段距離之和稱為通路距離(最大距離<=1000)。當所有的路段距離給出之後，求出所有不同距離的通路個數(相同距離僅記壹次)。
例如：下圖所示是當N=1時的情況：
從A到B的通路條數為6，但因其中通路5+5=4+6，所以滿足條件的不同距離的通路條數為5。
算法說明：本題采用窮舉算法。
數據結構：N：記錄A，B間路站的個數
數組D[I，0]記錄第I-1個到第I路站間路段的個數
D[I，1]，D[I，2]，…記錄每個路段距離
數組G記錄可取到的距離
程序清單：
program CHU7_6;
var i,j,n,s:integer;
b:array[0..100] of integer;
d:array[0..100,0..20] of integer;
g:array[0..1000] of 0..1;
begin
readln(n);
for i:=1 to n+1 do
begin
readln(d[i,0]);
for j:=1 to d[i,0] do read(d[i,j]);
end;
d[0,0]:=1;
for i:=1 to n+1 do b[i]:=1;
b[0]:=0;
for i:=1 to 1000 do g[i]:=0;
while b[0]<>1 do
begin
s:=0;
for i:=1 to n+1 do
s:= s+d[i,b[i]];
g[s]:=1;j:=n+1;
while b[j]=d[j,0] do j:=j-1;
b[j]:=b[j]+1;
for i:=j+1 to n+1 do b[i]:=1;
end;
s:=0;
for i:=1 to 1000 do
s:=s+g[i];
writeln(s);readln;
end.
2.1 遞歸的概念
1.概念
壹個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數).
如:
procedure a;
begin
.
.
.
a;
.
.
.
end;
這種方式是直接調用.
又如:
procedure b; procedure c;
begin begin
. .
. .
. .
c; b;
. .
. .
. .
end; end;
這種方式是間接調用.
例1計算n!可用遞歸公式如下:
1 當 n=0 時
fac(n)={n*fac(n-1) 當n>0時
可編寫程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 樓梯有n階臺階,上樓可以壹步上1階,也可以壹步上2階,編壹程序計算***有多少種不同的走法.
設n階臺階的走法數為f(n)
顯然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可編程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何設計遞歸算法
1.確定遞歸公式
2.確定邊界(終了)條件
練習:
用遞歸的方法完成下列問題
1.求數組中的最大數
2.1+2+3+...+n
3.求n個整數的積
4.求n個整數的平均值
5.求n個自然數的最大公約數與最小公倍數
6.有壹對雌雄兔,每兩個月就繁殖雌雄各壹對兔子.問n個月後***有多少對兔子?
7.已知:數列1,1,2,4,7,13,24,44,...求數列的第 n項.
2.3典型例題
例3 梵塔問題
如圖:已知有三根針分別用1,2,3表示,在壹號針中從小放n個盤子,現要求把所有的盤子
從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動壹塊盤子,且每根針上
不能出現大盤壓小盤.找出移動次數最小的方案.
程序如下:
program fanta;
var
n:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先從數據序列中選壹個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每壹個待處理的序列的長度為1, 處理結束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
3.1 回溯的設計
1.用棧保存好前進中的某些狀態.
2.制定好約束條件
例1由鍵盤上輸入任意n個符號;輸出它的全排列.
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
例2.n個皇後問題:
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
回溯算法的公式如下:
3.2 回溯算法的遞歸實現
由於回溯算法用壹棧數組實現的,用到棧壹般可用遞歸實現。
上述例1的遞歸方法實現如下：
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procedure try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.
例2：n皇後問題的遞歸算法如下：
程序1：
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procedure try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.
程序2：
說明:當n=8 時有30條對角線分別用了l和r數組控制，
用c數組控制列.當(i,j)點放好皇後後相應的對角線和列都為false.遞歸程序如下:
program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procedure output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.
7.1 貪心策略的定義
貪心策略是：指從問題的初始狀態出發，通過若幹次的貪心選擇而得出最優值(或較優解)的壹種解題方法。
其實，從“貪心策略”壹詞我們便可以看出，貪心策略總是做出在當前看來是最優的選擇，也就是說貪心策略並不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優解，而許多問題自身的特性決定了該題運用貪心策略可以得到最優解或較優解。
例1：在n行m列的正整數矩陣中，要求從每壹行中選壹個數，使得選出的n個數的和最大。
本題可用貪心策略：選n次，每壹次選相應行中的最大值即可。
例2：在壹個N×M的方格陣中，每壹格子賦予壹個數（即為權）。規定每次移動時只能向上或向右。現試找出壹條路徑，使其從左下角至右上角所經過的權之和最大。
本題用貪心策略不能得到最優解，我們以2×4的矩陣為例。 3 4 6
1 2 10
若按貪心策略求解，所得路徑為：1,3,4,6；
若按動態規劃法求解，所得路徑為：1,2,10,6。
例3:設定有n臺處理機p1，p2，......pn,和m個作業j1,j2,...jm,處理機可並行工作,作業未完成不能中斷，作業ji在處理機上的處理時間為ti,求解最佳方案,使得完成m項工作的時間最短?
本題不能用貪心算法求解:理由是若n=3,m=6 各作業的時間分別是11 7 5 5 4 7
用貪心策略解(每次將作業加到最先空閑的機器上)time=15,用搜索策略最優時間應是14,但是貪心策略給我們提供了壹個線索那就是每臺處理上的時間不超過15,給搜索提供了方便。
總之：
1. 不能保證求得的最後解是最佳的；
2. 只能用來求某些最大或最小解問題；
3. 能確定某些問題的可行解的範圍，特別是給搜索算法提供了依據。
7. 2 貪心策略的特點
貪心算法有什麽樣的特點呢？我認為，適用於貪心算法解決的問題應具有以下2個特點：
1、貪心選擇性質：
所謂貪心選擇性質是指應用同壹規則f，將原問題變為壹個相似的、但規模更小的子問題、而後的每壹步都是當前看似最佳的選擇。這種選擇依賴於已做出的選擇，但不依賴於未做出的選擇。從全局來看，運用貪心策略解決的問題在程序的運行過程中無回溯過程。關於貪心選擇性質，讀者可在後文給出的貪心策略狀態空間圖中得到深刻地體會。
2、局部最優解：
我們通過特點2向大家介紹了貪心策略的數學描述。由於運用貪心策略解題在每壹次都取得了最優解，但能夠保證局部最優解得不壹定是貪心算法。如大家所熟悉得動態規劃算法就可以滿足局部最優解，但貪心策略比動態規劃時間效率更高站用內存更少，編寫程序更簡單。
7.3 典型例題與習題
例4：背包問題：
有壹個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。 物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
價值
10
40
30
50
35
40
30
分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所占空間最小的物品裝入是否能得到最優解？
（3）每次選取單位容量價值最大的物品，成為解本題的策略。
程序如下：
program beibao;
const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;
procedure init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;
procedure make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i]<bi[j] then begin
temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;
begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.
例5：旅行家的預算問題：
壹個旅行家想駕駛汽車以最少的費用從壹個城市到另壹個城市，給定兩個城市間的距離d1，汽車油箱的容量是c，每升汽油能行駛的距離d2，出發時每升汽油的價格是p，沿途加油站數為n（可為0），油站i離出發點的距離是di，每升汽油的價格是pi。
計算結果四舍五入保留小數點後兩位，若無法到達目的地輸出“No answer"
若輸入：
d1=275.6 c=11.9 d2=27.4 p=8 n=2
d[1]=102 p[1]=2.9
d[2]=220 p[2]=2.2
output
26.95
本問題的貪心策略是：找下壹個較便宜的油站，根據距離確定加滿、不加、加到剛好到該站。
程序如下:
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procedure buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procedure solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s<=maxway+zero then
if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.
例6:n個部件,每個部件必須經過先A後B兩道工序。
以知部件i在A,B 機器上的時間分別為ai，bi。如何安排加工順序，總加工時間最短？
輸入：
5 部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
輸出：
34
1 5 4 2 3
本問題的貪心策略是A機器上加工短的應優先，B機器上加工短的應靠後。
程序如下：
program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procedure init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a<c[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procedure sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m<t then begin t:=c[j].m;k:=j end ;
if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procedure playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procedure calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2<t1 then t2:=t1;
t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.