信息学奥赛 基础算法 汇总版
文档属性
| 名称 | 信息学奥赛 基础算法 汇总版 |  | |
| 格式 | zip | ||
| 文件大小 | 180.1KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 通用版 | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2014-06-01 19:59:21 | ||
图片预览
文档简介
基础算法教案 目录
TOC \o "1-1" \h \z \u 第一课 算法简介 1
HYPERLINK \l "_Toc66721565" 第二课 多精度数值处理 1
第三课 排列与组合 6
HYPERLINK \l "_Toc66721567" 第四课 枚举法 9
第五课 递归与回溯法 25
HYPERLINK \l "_Toc66721569" 第六课 递推法 42
第七课 贪心法 50
HYPERLINK \l "_Toc66721571" 第八课 分治法 64
第九课 模拟法 70
HYPERLINK \l "_Toc66721573" 习题 79
第一课 算法简介
算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征：
有穷性：一个算法必须能在执行有限步之后结束；
确切性：算法的每一步骤必须确切定义；
输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件；
输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的；
可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。
为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。
第二课 多精度数值处理
课题：多精度数值的处理
目标：
知识目标：多精度值的加、减、乘、除
能力目标：多精度值的处理，优化！
重点：多精度的加、减、乘
难点：进位与借位处理
板书示意：
输入两个正整数，求它们的和
输入两个正整数，求它们的差
输入两个正整数，求它们的积
输入两个正整数，求它们的商
授课过程：
所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。
例1 从键盘读入两个正整数，求它们的和。
分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。
这样，我们方便写出两个整数相加的算法。
如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上例有
A[1]=6, A[2]=5, A[3]=8, B[1]=5,B[2]=5, B[3]=2, C[4]=1,C[3]=1, C[2]=1,C[1]=1,两数相加如图2所示。由上图可以看出：
C[i]:= A[i]+B[i];
if C[i]>10 then begin C[i]:= C[i] mod 10; C[i+1]:= C[i+1]+1 end;
因此，算法描述如下：
procedure add(a,b;var c);
{ a,b,c都为数组，a存储被加数，b存储加数，c存储结果 }
var i,x:integer;
begin
i:=1
while (i<=a数组长度>0) or(i<=b数组的长度) do begin
x := a[i] + b[i] + x div 10; {第i位相加并加上次的进位}
c[i] := x mod 10; {存储第i位的值}
i := i + 1 {位置指针变量}
end
end;
通常，读入的两个整数用可用字符串来存储，程序设计如下：
program exam1;
const
max=200;
var
a,b,c:array[1..max] of 0..9;
n:string;
lena,lenb,lenc,i,x:integer;
begin
write('Input augend:'); readln(n);
lena:=length(n); {加数放入a数组}
for i:=1 to lena do a[lena-i+1]:=ord(n[i])-ord('0');
write('Input addend:'); readln(n);
lenb:=length(n); {被加数放入b数组}
for i:=1 to lenb do b[lenb-i+1]:=ord(n[i])-ord('0');
i:=1;
while (i<=lena) or(i<=lenb) do begin
x := a[i] + b[i] + x div 10; {两数相加，然后加前次进位}
c[i] := x mod 10; {保存第i位的值}
i := i + 1
end;
if x>=10 then {处理最高进位}
begin lenc:=i;c[i]:=1 end
else lenc:=i-1;
for i:=lenc downto 1 do write(c[i]); {输出结果}
writeln
end.
例2 高精度减法。
从键盘读入两个正整数，求它们的差。
分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。
因此，可以写出如下关系式
if a[i]c[i]:=a[i]-b[i]
类似，高精度减法的参考程序：
program exam2;
const
max=200;
var
a,b,c:array[1..max] of 0..9;
n,n1,n2:string;
lena,lenb,lenc,i,x:integer;
begin
write('Input minuend:'); readln(n1);
write('Input subtrahend:'); readln(n2);
{处理被减数和减数}
if (length(n1)begin
n:=n1;n1:=n2;n2:=n;
write('-') {n1end;
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');
i:=1;
while (i<=lena) or(i<=lenb) do begin
x := a[i] - b[i] + 10 + x; {不考虑大小问题，先往高位借10}
c[i] := x mod 10 ; {保存第i位的值}
x := x div 10 - 1; {将高位借掉的1减去}
i := i + 1
end;
lenc:=i;
while (c[lenc]=0) and (lenc>1) do dec(lenc); {最高位的0不输出}
for i:=lenc downto 1 do write(c[i]);
writeln
end.
例3 高精度乘法。
从键盘读入两个正整数，求它们的积。
分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运算时，必须进行错位相加，如图3, 图4。
分析C数组下标的变化规律，可以写出如下关系式
C i = C’ i +C ”i +…
由此可见，C i跟A[i]*B[j]乘积有关，跟上次的进位有关，还跟原C i的值有关，分析下标规律，有
x:= A[i]*B[j]+ x DIV 10+ C[i+j-1];
C[i+j-1] := x mod 10;
类似，高精度乘法的参考程序：
program exam3;
const
max=200;
var
a,b,c:array[1..max] of 0..9;
n1,n2:string;
lena,lenb,lenc,i,j,x:integer;
begin
write('Input multiplier:'); readln(n1);
write('Input multiplicand:'); readln(n2);
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');
for i:=1 to lena do begin
x:=0;
for j:=1 to lenb do begin {对乘数的每一位进行处理}
x := a[i]*b[j] + x div 10 + c[i+j-1]; {当前乘积+上次乘积进位+原数}
c[i+j-1] := x mod 10;
end;
c[i+j]:= x div 10; {进位}
end;
lenc:=i+j;
while (c[lenc]=0) and (lenc>1) do dec(lenc);
for i:=lenc downto 1 do write(c[i]);
writeln
end.
例４ 高精度除法。
从键盘读入两个正整数，求它们的商（做整除）。
分析：做除法时，每一次上商的值都在０～９，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用0～9次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。
参考程序：
program exam4;
const
max=200;
var
a,c:array[1..max] of 0..9;
x,b:longint;
n1,n2:string;
lena:integer;
code,i,j:integer;
begin
write('Input dividend:'); readln(n1);
write('Input divisor:'); readln(n2);
lena:=length(n1);
for i:=1 to lena do a[i] := ord(n1[i]) - ord('0');
val(n2,b,code);
{按位相除}
x:=0;
for i:=1 to lena do begin
c[i]:=(x*10+a[i]) div b;
x:=(x*10+a[i]) mod b;
end;
{显示商}
j:=1;
while (c[j]=0) and (jfor i:=j to lena do write(c[i]) ;
writeln
end.
实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。例如图5就是采用4位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以解决，程序请读者完成。
第三课 排列与组合
课题：排列与组合
目标：
知识目标：如何利用程序就各种排列和组合
能力目标：排列组合的运用
重点：求出n的全排列和从m中取n个的组合
难点：算法的理解
板书示意：
求全排列的算法
求组合数的算法
授课过程：
例5：有3个人排成一个队列，问有多少种排对的方法，输出每一种方案？
分析：如果我们将3个人进行编号，分别为1、2、3，显然我们列出所有的排列，123，132，213，231，312，321共六种。可用循环枚举各种情况，参考程序：
program exam5;
var
i,j,k:integer;
begin
for I:=1 to 3 do
for j:=1 to 3 do
for k:=1 to 3 do
if (i+j+k=6) and (i*j*k=6) then writeln(i,j,k);
end.
上述情况非常简单，因为只有3个人，但当有N个人时怎么办？显然用循环不能解决问题。下面我们介绍一种求全排列的方法。
设当前排列为P1 P2 ,…,Pn，则下一个排列可按如下算法完成：
1．求满足关系式Pj-1 < Pj的J的最大值，设为I，即
I=max{j | Pj-1 < Pj , j = 2..n}
2．求满足关系式Pi -1 < Pk的k的最大值，设为j，即
J=max{K | Pi-1 < Pk , k = 1..n}
3．Pi -1与Pj互换得 (P) = P1 P2 ,…,Pn
4．(P) = P1 P2 ,…, Pi-1 Pi,…, Pn部分的顺序逆转，得P1 P2 ,…, Pi-1 Pn Pn-1,…, Pi便是下一个排列。
例：设P1 P2 P3 P4 =3421
1．I= max{j | Pj-1 < Pj , j = 2..n} = 2
2．J=max{K | Pi-1 < Pk , k =1..n} = 2
3．P1与P2交换得到4321
4．4321的321部分逆转得到4123即是3421的下一个排列。
程序设计如下：
program exam5;
const
maxn = 100;
var i,j,m,t : integer;
p : array[1..maxn] of integer;
count :integer; {排列数目统计变量}
begin
write('m:');readln(m);
for i:=1 to m do begin p[i]:=i; write(i) end;
writeln;
count:=1;
repeat
{求满足关系式Pj-1 < Pj的J的最大值，设为I}
i:=m;
while (i>1) and (p[i-1]>=p[i]) do dec(i);
if i=1 then break;
{求满足关系式Pi -1 < Pk的k的最大值，设为j}
j:=m;
while (j>0) and (p[i-1]>=p[j]) do dec(j);
if j=0 then break;
{Pi -1与Pj互换得 (P) = P1 P2 ,…,Pm}
t:=p[i-1];p[i-1]:=p[j];p[j]:=t;
{Pi,…, Pm的顺序逆转}
for j:=1 to (m-i+1) div 2 do begin
t:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=t
end;
{打印当前解}
for i:=1 to m do write(p[i]);
inc(count);
writeln;
until false;
writeln(count)
End.
例6：求N个人选取M个人出来做游戏，共有多少种取法？例如：N=4，M=2时，有12，13，14，23，24，34共六种。
分析：因为组合数跟顺序的选择无关。因此对同一个组合的不同排列，只需取其最小的一个（即按从小到大排序）。因此，可以设计如下算法：
1．最后一位数最大可达N，倒数第二位数最大可达N-1，…，依此类推，倒数第K位数最大可达N-K+1。
若R个元素组合用C1C2 …CR表示，且假定C12．当存在CjI=max{J | CjCi+1 := Ci +1 ，Ci+2 := Ci +1+1 ，…. ，CR := CR-1 +1
参考程序：
program exam6;
const maxn=10;
var i,j,n,m :integer;
c :array[1..maxn]of integer; {c数组记录当前组合}
Begin
Write('n & m:'); readln(n,m);
for i:=1 to m do begin {初始化，建立第一个组合}
c[i]:=i;
write(c[i]);
end;
writeln;
while c[1]j:=m;
while (c[j]>n-m+1) and ( j>0) do dec(j); {求I=max{J | Cjc[j]:=c[j]+1;
for i:=j+1 to m do c[i]:=c[i-1]+1; {建立下一个组合}
for i:=1 to m do write(c[i]);writeln {输出}
end;
End.
第四课 枚举法
课题：枚举法
目标：
知识目标：枚举算法的本质和应用
能力目标：枚举算法的应用！
重点：利用枚举算法解决实际问题
难点：枚举算法的次数确定
板书示意：
简单枚举（例7、例8、例9）
利用枚举解决逻辑判断问题（例10、例11）
枚举解决竞赛问题（例12、例13、例14）
授课过程：
所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：
对命题建立正确的数学模型；
根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；
利用循环语句、条件判断语句逐步求解或证明；
枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。
例7：求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。
分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下：
for A := 1 to 3 do
for B := 1 to 3 do
for C := 1 to 3 do
if A + B = C then
Writeln(A, ‘+’, B, ‘=’, C);
上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。
从枚举法的定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在采用枚举法求解的问题时，必须满足两个条件：
预先确定解的个数n；
对每个解变量A1，A2，……，An的取值，其变化范围需预先确定
A1∈{X11，……，X1p}
……
Ai∈{Xi1，……，Xiq}
……
An∈{Xn1，……，Xnk}
例7中的解变量有3个：A，B，C。其中
A解变量值的可能取值范围A∈{1，2，3}
B解变量值的可能取值范围B∈{1，2，3}
C解变量值的可能取值范围C∈{1，2，3}
则问题的可能解有27个
（A，B，C）∈{（1，1，1），（1，1，2），（1，1，3），
（1，2，1），（1，2，2），（1，2，3），
………………………………
（3，3，1），（3，3，2），（3，3，3）}
在上述可能解集合中，满足题目给定的检验条件的解元素，即为问题的解。
如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用搜索等算法求解。由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问题，回溯算法要比枚举法时间复杂度稍高。
例8 给定一个二元一次方程aX+bY=c。从键盘输入a,b,c的数值，求X在[0，100]，Y在[0，100]范围内的所有整数解。
分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看这些点是否满足方程即可。参考程序：
program exam8;
var
a,b,c:integer;
x,y:integer;
begin
write('Input a,b,c:');readln(a,b,c);
for x:=0 to 100 do
for y:=0 to 100 do
if a*x+b*y=c then writeln(x,' ',y);
end.
从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。
例9 巧妙填数
1 9 2
3 8 4
5 7 6
将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。如图6:
图6
分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。
但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：
program exam9;
var
i,j,k,s:integer;
function sum(s:integer):integer;
begin
sum:=s div 100 + s div 10 mod 10 + s mod 10
end;
function mul(s:integer):longint;
begin
mul:=(s div 100) * (s div 10 mod 10) * (s mod 10)
end;
begin
for i:=1 to 3 do
for j:=1 to 9 do
if j<>i then for k:=1 to 9 do
if (k<>j) and (k<>i) then begin
s := i*100 + j*10 +k; {求第一行数}
if 3*s<1000 then
if (sum(s)+sum(2*s)+sum(3*s)=45) and
(mul(s)*mul(2*s)*mul(3*s)=362880) then {满足条件，并数字都由1~9组成}
begin
writeln(s);
writeln(2*s);
writeln(3*s);
writeln;
end;
end;
end.
例10 在某次数学竞赛中, A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名？
条件1: 你如果认为A, B, C, D, E 就是这些人的第一至第五名的名次排列, 便大错。因为:
没猜对任何一个优胜者的名次。
也没猜对任何一对名次相邻的学生。
条件2: 你如果按D, A , E , C , B 来排列五人名次的话, 其结果是:
说对了其中两个人的名次。
还猜中了两对名次相邻的学生的名次顺序。
分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。
根据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一种可能性，只有4！=24种情况了。
参考程序：
Program Exam10;
Var
A,B,C,D,E :Integer;
Cr :Array[1..5] Of Char;
Begin
For A:=1 To 5 Do
For B:=1 To 5 Do
For C:=1 To 5 Do
For D:=1 To 5 Do
For E:=1 To 5 Do Begin
{ABCDE没猜对一个人的名次}
If (A=1) Or (B=2) Or (C=3) Or (D=4) Or (E=5) Then Continue;
If [A,B,C,D,E]<>[1,2,3,4,5] Then Continue;{他们名次互不重复}
{DAECB猜对了两个人的名次}
If Ord(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2 Then Continue;
{ABCDE没猜对一对相邻名次}
If (B=A+1) Or (C=B+1) Or (D=C+1) Or (E=D+1) Then Continue;
{DAECB猜对了两对相邻人名次}
If Ord(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2 Then Continue;
Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';
Cr[D]:='D';Cr[E]:='E';
Writeln(Cr[1],' ',Cr[2],' ',Cr[3],' ',Cr[4],' ',Cr[5]);
End;
End.
例11：来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况是, 没有人既会日语又会法语;A会日语,但D不会,A和D能互相交谈,B不会英语,但A和C交谈时却要B当翻译,B,C,D三个想互相交谈,但找不到共同的语言,只有一种语言3人都会,编程确定A,B,C,D四位留学生各会哪两种语言。
分析：将中、法、日、英四种语言分别定义为CHN、FRH、JPN、ENG,则四种语言中取两种共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),( ENG,FRH),( ENG,JPN),(FRH,JPN)六种组合，分别定义为1、2、3、4、5、6。据已知，没有人既会日语又会法语;因此，组合6不会出现；A 会日语，所以A只可能等于3、5；D不会日语, 所以D只可能等于1、2、4；B不会英语，所以B只可能等于2、3；见下表。如果我们对A、B、C、D分别进行枚举，根据判定条件，即可找到答案。
(CHN,ENG) (CHN,FRH) (CHN,JPN) ( ENG,FRH) ( ENG,JPN)
A × × ×
B × × ×
C
D × ×
程序如下：
program EXAM11;
type
Language = (CHN,ENG,FRH,JPN);
TNoSet= set of Language;
const
No: array [1 .. 5] of TNoSet=
([CHN,ENG], [CHN,FRH], [CHN,JPN], [ENG,FRH], [ENG,JPN]);
var
A, B, C, D: 1 .. 5;
Can1, Can2, Can3, Can4: Boolean;
function Might(Lang: Language): Boolean;
var
Bool: Boolean;
begin
Bool:=false;
if No[A] * No[A] * No[C] = [Lang] then Bool := True;
if No[A] * No[B] * No[D] = [Lang] then Bool := True;
if No[A] * No[C] * No[D] = [Lang] then Bool := True;
if No[B] * No[C] * No[D] = [Lang] then Bool := True;
Might := Bool
end;
procedure Print(A, B, C, D: Integer);
procedure Show(P: Integer; Ch: Char);
var
I: Integer;
Lang: Language;
begin
Write(ch,':');
for Lang := CHN to JPN do
if Lang in No[P] then
case Lang of
CHN: Write('CHN':5);
FRH: Write('FRH':5);
JPN: Write('JPN':5);
ENG: Write('ENG':5);
end;
Writeln;
end;
begin
Show(A, 'A');
Show(B, 'B');
Show(C, 'C');
Show(D, 'D');
end;
begin
for A := 3 to 5 do
if A <> 4 then for B := 2 to 3 do
for C := 1 to 5 do
for D := 1 to 4 do if D <> 3 then begin
{A和D能互相交谈}
Can1 := No[A] * No[D] <> [];
{A和C交谈时却要B当翻译}
Can2 := (No[A] * No[C] = []) and (No[A] * No[B] <> [])
and (No[B] * No[C] <> []);
{B,C,D三个想互相交谈,但找不到共同的语言}
Can3 := No[B] * No[C] * No[D] = [];
{只有一种语言3人都会}
Can4 := Ord(Might(CHN)) + Ord(Might(ENG))
+ Ord(Might(FRH)) + Ord(Might(JPN)) = 1;
if Can1 and Can2 and Can3 and Can4 then Print(A,B,C,D);
end;
end.
例12 古纸残篇
在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了, 只留下曾经写过字的痕迹, 依稀还可以看出它是一个乘法算式, 如图7所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来。难道说, 这个算式与素数有什么关系吗？有人对此作了深入的研究, 果然发现这个算式中的每一个数字都是素数, 而且这样的算式是唯一的。请你也研究一番, 并把这个算式写出来。
分析：实际上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被乘数的每一位。然后再判断是不是满足条件即可。计算量是45=1024，对于计算机来说，计算量非常小。
参考程序：
Program Exam12;
Const
Su : Array[1..4] Of Longint=(2,3,5,7);
Var
A1,A2,A3,B1,B2,X,Y,S :Longint;
Function Kx(S:Longint):Boolean;{判断一个数
是不是都是由素数组成}
Begin
Kx:=True;
While S<>0 Do Begin
If Not((S Mod 10) In [2,3,5,7]) Then Begin
Kx:=False;
Exit;
End;
S:=S Div 10;
End;
End;
Begin
For A1:=1 To 4 Do
For A2:=1 To 4 Do
For A3:=1 To 4 Do
For B1:=1 To 4 Do
For B2:=1 To 4 Do Begin
X:=Su[A1]*100+Su[A2]*10+Su[A3];{X为被乘数}
If X*Su[B1]<1000 Then Continue;
If X*Su[B2]<1000 Then Continue;
If X*(Su[B1]*10+Su[B2])<10000 Then Continue;
{它们分别是两个四位数，一个五位数}
If (Kx(X*Su[B1])=False) Or
(Kx(X*Su[B2])=False) Or
(Kx(X*(Su[B1]*10+Su[B2]))=False) Then Continue;
{满足其他数都是由质数构成}
Writeln(' ',Su[A1],Su[A2],Su[A3]);
Writeln('* ',Su[B1],Su[B2]);
Writeln('-----------');
Writeln(' ',X*Su[B2]);
Writeln(' ',X*Su[B1]);
Writeln('-----------');
Writeln(' ',X*(Su[B1]*10+Su[B2]));
End;
End.
例13：时钟问题（IOI94-4）
在图8所示的3*3矩阵中有9个时钟，我们的目标是旋转时钟指针，使所有时钟的指针都指向12点。允许旋转时钟指针的方法有9种，每一种移动用一个数字号（1，2，…，9）表示。图2-11示出9个数字号与相应的受控制的时钟，这些时钟在图中以灰色标出，其指针将顺时针旋转90度。
输入数据：
由输入文件INPUT.TXT读9个数码，这些数码给出了9个时钟时针的初始位置。数码与时刻的对应关系为：
0——12点
1——3点
2——6点
3——9点
图2-11中的例子对应下列输入数据：
330
222
212
输出数据：
将一个最短的移动序列（数字序列）写入输出文件OUTPUT.TXT中，该序列要使所有的时钟指针指向12点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的OUTPUT.TXT的内容为：
5849
输入输出示例：
INPUT.TXT OUTPUT.TXT
330222212 5489
具体的移动方案如图10所示。
分析：
首先，我们分析一下表示时钟时针初始位置的数码j（0≦j≦3）与时刻的对应关系：
0——12点
1——3点
2——6点
3——9点
每移动一次，时针将顺时针旋转90度。由此我们可以得出：
对于任意一个时钟i（1≦i≦9）来说，从初始位置j出发至少需要Ci=（4-j） mod 4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。
移动方案选取与顺序无关。样例中，最佳移动序列为5849，同样4589序列也可达到目标。因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。
设 pi表示第i种旋转方法的使用次数（0≦pi≦3，1≦i≦9）。
则可能的解的集合为{P1，P2，……，P9}，该集合共含49个状态。从图2.11中，我们可以分析出9个时钟分别被哪些方法所控制，见下表：
时钟号 控制时钟方案 检验条件
1 1、2、4 C1=(P1+P2+P4) mod 4
2 1、2、3、5 C2=(P1+P2+P3+P5) mod 4
3 2、3、6 C3=(P2+P3+P6) mod 4
4 1、4、5、7 C4=(P1+P4+P5+P7) mod 4
5 1、3、5、7、9 C5=(P1+P3+P5+P7+P9) mod 4
6 3、5、6、9 C6=(P3+P5+P6+P9) mod 4
7 4、7、8 C7=(P4+P7+P8) mod 4
8 5、7、8、9 C8=(P5+P7+P8+P9) mod 4
9 6、8、9 C9=(P6+P8+P9) mod 4
因此我们可以设计如下枚举算法：
for p1:=0 to 3 do
for p2:=0 to 3 do
... ... ...
for p9:=0 to 3 do
if c1满足时钟1 and c2满足时钟2 and ... and c9满足时钟9 then
打印解路径；
显然，上述枚举算法枚举了所有49=262144个状态，运算量和运行时间颇大。我们可以采取缩小可能解范围的局部枚举法，仅枚举第1、2、3种旋转方法可能取的43个状态，根据这三种旋转方法的当前状态值，由下述公式
P4=order(C1-P1-P2);
P5=order(C2-P1-P2-P3);
P6=order(C3-P2-P3);
P7=order(C4-P1-P4-P5);
P8=order(C8-P5-PP9);
P9=order(C6-P3-P5-P6);
其中
得出其余P4……P9的相应状态值。然后将P1，P2，…，P9代入下述三个检验条件
C5=(P1+P3+P5+P7+P9) mod 4
C7=(P4+P7+P8) mod 4
C9=(P6+P8+P9) mod 4
一一枚举，以求得确切解。
由此可见，上述局部枚举的方法（枚举状态数为43个）比较全部枚举的方法（枚举状态数为49个）来说，由于大幅度削减了枚举量，减少运算次数，因此其时效显著改善，是一种优化了的算法。
程序如下：
program IOI94_4;
const
Inp = 'input.txt';
Outp = 'output.txt';
var
Clock, Map: array [1 .. 3, 1 .. 3] of Integer;
{Clock：第((I+2)mod 3)*3+J个时钟从初始时间到12点的最少移动次数}
{Map:最短移动序列中，数字（（I+2）mod 3）*3+J的次数}
procedure Init;
var
I, J: Integer;
begin
Assign(Input, Inp); Reset(Input);
for I := 1 to 3 do
{读入9个时钟指针的初始位置，求出每个时钟从初始到12点的最少移动次数}
for J := 1 to 3 do begin
Read(Clock[I, J]);
Clock[I, J] := (4 - Clock[I, J]) mod 4;
end;
Close(Input);
end;
function Order(K: Integer): Integer;
var
c: Integer;
begin
c:=k;
while c<0 do inc(c,4);
while c>4 then dec(c,4);
Order := k;
end;
procedure Main; {计算和输出最短移动序列}
var
I, J, K: Integer;
begin
{枚举最短移动序列中数字1、2、3的个数可能取的43种状态}
Assign(Output, Outp); Rewrite(Output);
for Map[1, 1] := 0 to 3 do
for Map[1, 2] := 0 to 3 do
for Map[1, 3] := 0 to 3 do begin
Map[2,1]:=Order(Clock[1,1]-Map[1,1]-Map[1,2]);
Map[2,3]:=Order(Clock[1,3]-Map[1,2]-Map[1,3]);
Map[2,2]:=Order(Clock[1,2]-Map[1,1]-Map[1,2]-Map[1, 3]);
Map[3,1]:=Order(Clock[2,1]-Map[1,1]-Map[2,1]-Map[2, 2]);
Map[3,3]:=Order(Clock[2,3]-Map[1,3]-Map[2,2]-Map[2, 3]);
Map[3,2]:=Order(Clock[3,2]-Map[3,1]-Map[3,3]-Map[2, 2]);
{根据数字1、2、3个数的当前值，得出数字4~9的个数}
if ((Map[2,1]+Map[3,1]+Map[3,2])mod 4=Clock[3,1]) and
((Map[2,3]+Map[3,2]+Map[3,3])mod 4=Clock[3, 3])and
((Map[2,2]+Map[1,1]+Map[1,3]+Map[3,1]+Map[3, 3])
mod 4 = Clock[2, 2])
then begin {若数字4~9的个数满足检验条件，则输出方案}
for I := 1 to 3 do
for J := 1 to 3 do
for K := 1 to Map[I, J] do
Write((I - 1) * 3 + J);
Exit; {找到一个解后退出}
end;
end;
Writeln('No Answer !');
Close(Output);
end;
begin
Init;
Main;
end.
在上例中，由于事先能够排除那些明显不属于解集的元素，使得算法效率非常高。而减少重复运算、力求提前计算所需数据、使用恰当的数据结构进行算法优化等方法也是优化枚举算法的常用手段。
例14：最佳游览线路 （NOI94）
某旅游区的街道成网格状（图2.13）。其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。
阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的街道值得游览的程度，分值时从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。
例如图11是被打过分的某旅游区的街道图：
阿龙可以从任一个路口开始游览，在任一个路口结束游览。请你写一个程序，帮助阿龙找一条最佳的游览线路，使得这条线路的所有分值总和最大。
输入数据：
输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街（1≦M≦100），N表示有多少条林阴道（1≦M≦20001）。接下来的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。
输出数据：
输出文件是OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳游览线路的总分值。
输入输出示例：
INPUT.TXT OUTPUT.TXT
3 6-50 –47 36 –30 –2317 –19 –34 –13 –8-42 –3 –43 34 –45 84
分析：
设Lij为第I条旅游街上自西向东第J段的分值（1 ≦ I ≦ M，1 ≦ J ≦ N – 1）。例如样例中L12=17，L23=-34，L34=34。
我们将网格状的旅游区街道以林荫道为界分为N – 1个段，每一段由M条旅游街的对应段成，即第J段成为{L1J，L2J，……，LMJ}（1≦ J ≦ N – 1）。由于游览方向规定横向自西向东，纵向即可沿林阴道由南向北，亦可由北向南，而横行的街段有分值，纵行无分值，因此最佳游览路现必须具备如下三个特征：
来自若干个连续的段，每一个段中取一个分值；
每一个分值是所在段中最大的；
起点段和终点段任意，但途经段的分值和最大。
设Li为第I个段中的分值最大的段。即Li=Max{L1I，L2I，……，LMI}（1≦I≦N – 1）。例如对于样例数据：
L1=Max（-50，17，-42）=17；
L2=Max（-47，-19，-3）=-3；
L3=Max（36，-34，-43）=36；
L4=Max（-30，-13，34）=34；
L5=Max（-23，-8，-45）=-8；
有了以上的基础，我们便可以通过图示描述解题过程，见图12。
我们把将段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条游览路线。显然，如果确定西端为起点、东段为终点，则这条游览路线的总分值最大。
问题是某些段的最大分值可能是负值，而最优游览路线的起点和终点任意，在这种情况下，上述游览路线就不一定最佳了。因此，我们只能枚举这条游览路线的所有可能的子路线，从中找出一条子路线II+1……J（1 ≦ I设Best为最佳游览路线的总分值，初始时为0；
Sum为当前游览路线的总分值。
我们可以得到如下算法：
Best := 0; Sum := 0;
for I := 1 to N – 2 do
for J := I + 1 to N – 1 do begin
Sum := LI + …… + LJ;
if Sum > Best then
Best := Sum;
end
显然，这个算法的时间复杂度为O（N2）。而N在1~20001之间，时间复杂度比较高。于是，我们必须对这个算法进行优化。
仍然从顶点1开始枚举最优路线。若当前子路线延伸至顶点I时发现总分值Sum≦0，则应放弃当前子路线。因为无论LI+1为何值，当前子路线延伸至顶点I+1后的总分值不会大于LI+1。因此应该从顶点I+1开始重新考虑新的一条子路线。通过这种优化，可以使得算法的时间复杂度降到了O（N）。
优化后的算法描述如下:
Best := 0; Sum := 0;
for I := 1 to N – 1 do begin
Sum := Sum + LI;
if Sum > Best then
Best := Sum;
if Sum < 0 then
Sum := 0;
end
程序描述如下：
{$R-,S-,Q-}
{$M 65520,0,655360}
program Noi94;
const
MaxN = 20001; {林阴道数的上限}
Inp = 'input.txt';
Outp = 'output.txt';
var
M, N: Word; {旅游街数和林阴道数}
Best: Longint; {最佳游览路线的总分值}
Score: array [1..MaxN] of ShortInt; {描述每个段的最大分值}
procedure Init;
var
I, J, K: Integer;
Buffer: array [1 .. 40960] of Char; {文件缓冲区}
begin
Assign(Input, Inp);
Reset(Input);
SetTextBuf(Input, Buffer); {开辟文件缓冲区}
Readln(M, N); {读入旅游街数和林阴道数}
FillChar(Score,Sizeof(Score),$80); {初始化各段的最大分值}
for I := 1 to M do {计算1~N –1段的最大分值 }
for J := 1 to N - 1 do begin
Read(K);
if K > Score[J] then Score[J] := K;
end;
Close(Input);
end;
procedure Out;
begin
Assign(Output, Outp);
Rewrite(Output);
Writeln(Best);
Close(Output);
end;
procedure Main;
var
I: Integer;
Sum: Longint; {当前游览路线的总分值}
begin
{最佳游览路线的总分值和当前游览路线的总分值初始化}
Best := 0;
Sum := 0;
for I := 1 to N - 1 do begin {顺序枚举游览路线的总分值}
Inc(Sum, Score[I]); {统计当前游览路线的总分值}
if Sum > Best then Best := Sum; {若当前最佳，则记下}
if Sum < 0 then Sum := 0; {若总分值<0，则考虑一条新路线}
end;
end;
begin
Init; {输入数据}
Main; {主过程}
Out; {输出}
end.
第五课 递归与回溯法
课题：递归与回溯
目标：
知识目标：递归概念与利用递归进行回溯
能力目标：回溯算法的应用
重点：回溯算法
难点：回溯算法的理解
板书示意：
递归的理解
利用递归回溯解决实际问题（例14、例15、例16、例17、例18）
利用回溯算法解决排列问题（例19）
授课过程：
什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。
例如，我们可以这样定义N!，N!=N*(N-1)!，因此求N!转化为求 (N-1)!。这就是一个递归的描述。
因此，可以编写如下递归程序：
program Factorial;
var
N: Integer;
T: Longint;
function Fac(N: Integer): Longint;
begin
if N = 0 then Fac := 1 else Fac := N * Fac(N - 1)
end;
begin
Write('N = '); Readln(N);
T := Fac(N);
Writeln('N! = ',T);
end.
图13展示了N=3的执行过程。由上述程序可以看出，递归是一个反复执行直到递归终止的过程。
设一个未知函数f，用其自身构成的已知函数g来定义：
为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2) ，…，上述这种用自身的简单情况来定义自己的方式称为递归定义。
递归有如下特点：
①它直接或间接的调用了自己。
②一定要有递归终止的条件，这个条件通常称为边界条件。
与递推一样，每一个递推都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递归边界值f(0)=a。然后返回调用函数。返回的过程中，中间结果相继出栈恢复，f(1)=g(1,a)f(2)=g(2,f(1))……直至求出f(n)=g(n,f(n-1))。
由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。
递归算法适用的一般场合为：
① 数据的定义形式按递归定义。
如裴波那契数列的定义：
对应的递归程序为
function fib(n: Integer): Integer;
begin
if n = 0 then
fib := 1 {递归边界}
else if n = 1 then
fib := 2 {递归边界}
else
fib := fib(n – 2) + fib(n – 1); {递归}
end;
这类递归问题可转化为递推算法，递归边界为递推的边界条件。例如上例转化为递推算法即为
function fib(n: Integer): Integer;
begin
f[0] := 1; f[1] := 2; {递推边界}
for I := 2 to n do
f[I] := f[I – 1] + f[I – 2];
fib := f(n);
end;
② 数据之间的关系（即数据结构）按递归定义。如树的遍历，图的搜索等。
③ 问题解法按递归算法实现。例如回溯法等。
对于②和③，可以用堆栈结构将其转换为非递归算法，以提高算法的效率以及减少内存空间的浪费。
下面以经典的N皇后问题为例，看看递归法是怎样实现的，以及比较递归算法和非递归算法效率上的差别。
例15：N皇后问题
在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。
分析：
由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。
下面是放置第I个皇后的的递归算法：
Procedure Try(I:integer)；
{搜索第I行皇后的位置}
var
j:integer;
begin
if I=n+1 then 输出方案；
for j:=1 to n do
if 皇后能放在第I行第J列的位置 then begin
放置第I个皇后；
对放置皇后的位置进行标记；
Try（I+1）
对放置皇后的位置释放标记；
End;
End;
N皇后问题的递归算法的程序如下：
program N_Queens;
const
MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数}
procedure Out; {输出方案}
var
I: Integer;
begin
Inc(Total); Write(Total: 3, ‘:’);
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
procedure Try(I: Integer);
{搜索第I个皇后的可行位置}
var
J: Integer;
begin
if I = N + 1 then Out; {N个皇后都放置完毕，则输出解}
for J := 1 to N do
if A[J] and B[J + I] and C[J – I] then begin
X[I] := J;
A[J] := False;
B[J + I] := False;
C[J – I] := False;
Try(I + 1); {搜索下一皇后的位置}
A[J] := True;
B[J + I] := True;
C[J – I] := True;
end;
end;
begin
Write(‘Queens Numbers = ‘);
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, Sizeof(C), True);
Try(1);
Writeln(‘Total = ‘, Total);
end.
N皇后问题的非递归算法的程序：
program N_Queens;
const MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数
procedure Out; {输出方案}
var
I: Integer;
begin
Inc(Total);
Write(Total: 3, ‘:’);
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
procedure Main;
var
K: Integer;
begin
X[1] := 0; K := 1;
while K > 0 do begin
if X[K] <> 0 then begin
A[X[K]] := True;
B[X[K] + K] := True;
C[X[K] – K] := True;
end;
Inc(X[K]);
while(X[K]<=N)and not(A[X[K]]and B[X[K]+K]and C[X[K]–K])do
Inc(X[K]); {寻找一个可以放置的位置}
if X[K] <= N then
if K = N then Out
else begin
A[X[K]] := False;
B[X[K] + K] := False;
C[X[K] – K] := False;
Inc(K);
X[K] := 0; {继续放置下一个皇后}
end
else Dec(K); {回溯}
end;
end;
begin
Write(‘Queens Number = ‘);
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, SizeofI, True);
Main;
Writeln(‘Total = ‘, Total);
end.
使用递归可以使蕴含复杂关系的问题，结构变得简洁精炼。看看下面的例题。
例16:新汉诺（hanoi）塔问题
设有n各大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称之为初始状态。问题要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。移动时有如下要求：
一次只移动一个盘；
不允许把大盘移到小盘上边；
输入：输入文件第1行是状态中圆盘总数；第2~4行是分别是初始状态中A、B、C柱上的圆盘个数和从上到下每个圆盘的编号；第5~7行是分别是目标状态A、B、C柱上的圆盘个数和从上到下每个圆盘的编号。
输出：每行写一步的移动方案，格式为：
Move I圆盘 form P柱 to Q柱。
最后输出最少步数。
输入样例（如图）：
6
3 1 2 3
2 4 5
1 6
0
6 1 2 3 4 5 6
0
样例所描述的状态如图15所示。
=
输出样例：
分析：
要从初始状态移动到目标状态，就是把每个圆盘分别移动到自己的目标状态。而问题的关键一步就是：首先考虑把编号最大的圆盘移动到自己的目标状态，而不是最小的，因为编号最大的圆盘移到目标位置之后就可以不再移动了，而在编号最大的圆盘未移到目标位置之前，编号小的圆盘可能还要移动，编号最大的圆盘一旦固定，对以后的移动将不会造成影响。
根据上面的分析可设计如下过程
Move(K, W);
表示把编号K的圆盘从当前所在柱移动到W柱的过程。
下面对样例进行分析。
将6号盘移动到B柱，在此之前一定将经历如图16所示的状态
要移动6号盘首先要把1~5号盘全部移开，也就是说，既不能移动到6号盘的初始立柱上，也不能移动到6号盘的目标立柱上。显然这里要将它们移动到A柱。然后再将6号盘移到位。此时状态如图17所示。
同时我们注意到：把1~5盘移动到目标的过程和将6号盘移动到B柱的过程，从形式上是一样的，只是盘的编号不同而已。显然这是个递归过程，可以采用递归法实现。
算法设计如下:
procedure Move(K, W)；
{编号K的圆盘从当前所在柱移动到W柱}
begin
if K号盘已经在W立柱上 then Exit； {递归边界}
for I := K - 1 downto 1 do
Move(I, 过渡立柱); {将编号小于K的盘都移到过渡立柱上去}
输出当前移动方案;
将K号盘移到W立柱上;
Inc(Step); {累计步数}
end;
程序设计如下：
program New_Hanoi;
const
Inp = ‘hanoi.in’;
Outp = ‘hanoi.out’;
MaxN = 64; {最大圆盘数}
Stake: array [1 .. 3] of Char =(‘A’, ‘B’, ‘C’);
type
Tnode = array [1 .. MaxN] of Byte; {记录圆盘所处的立柱编号}
var
N: Integer; {圆盘数}
Now, {当前状态}
Goal: Tnode; {目标状态}
Step: Longint; {步数}
procedure Init; {读入数据}
var
I, J, L, X: Integer;
begin
Assign(Input, Inp);
Reset(Input);
Readln(N); {读入圆盘数}
for I := 1 to 3 do begin {读入初始状态}
Read(L);
for J := 1 to L do begin
Read(X); Now[X] := I;
end;
Readln;
end;
for I := 1 to 3 do begin {读入目标状态}
Read(L);
for J := 1 to L do begin
Read(X); Goal[X] := I;
end;
Readln;
end;
Close(Input);
end;
procedure Main;
var
I: Integer;
procedure Move(K: Integer; W: Byte);
var
I, J: Word;
begin
if Now[K] = W then Exit; {若达到目标，则退出}
J := 6 – Now[K] – W; {计算过渡立柱编号}
for I := K – 1 downto 1 do {将圆盘移动到过渡立柱}
Move(I, J);
Write(‘Move‘,K,‘ From ‘,Stake[Now[K]],‘ to ‘,Stake[W]);
Writeln(‘.’);
Now[K] := W; {将K号盘移动到目标位置}
Inc(Step); {累计步数}
end;
begin
Assign(Output, Outp);
Rewrite(Output);
for I := N downto 1 do {从大到小对每一个圆盘进行处理}
Move(I, Goal[I]);
Writeln(Step); {输出总步数}
Close(Output);
end;
Begin
Init;
Main;
End.
例17背包问题：
已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大
分析：本题可以用递归求解：设当前有N个物品，容量为M；因为这些物品要么选，要么不选，我们假设选的第一个物品编号为I（1~I-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可。
另外，为了优化程序，我们定义一个函数如下：
F[I]表示选第I~N个物品能得到的总效益。不难推出：
F[N]=Pn
F[I]=F[I+1]+Pi （I=1…N-1）
假设当前已选到第I号物品，如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小，则没有必要继续搜索下去。
参考程序：
Program exam17;
Var W,P :Array [1..50] Of Integer;
F :Array [1..50] Of Integer;
Ou,Out :Array [1..50] Of Boolean;
{Ou，Out数组记录选择物品的具体方案}
M :Integer;
N,U :Byte;
Ans,Now :Integer; {Ans记录最优解，Now记录当前效益值}
Procedure Init; {初始化}
Var I :Byte;
Begin
Fillchar(Out,Sizeof(Out),False);
Ou:=Out;
Assign(Input,'Input.txt');
Reset(Input);
Readln(M,N);
For I:=1 To N Do
Readln(W[I],P[I]);
Close(Input); {读入数据}
F[N+1]:=0;
For I:=N Downto 1 Do
F[I]:=F[I+1]+P[I]; {计算函数F的值}
Ans:=0;
Now:=0;
End;
Procedure Search(I:Integer; J:Byte); {递归求解}
Var K :Byte;
Begin
If Now+F[J]<=Ans Then Exit; {如果没有必要搜索下去，则返回到上一级}
If Now>Ans Then Begin {修改最优解}
Ans:=Now;
Out:=Ou;
End;
For K:=J To N Do {选取物品}
If W[K]<=I Then Begin
Now:=Now+P[K];
Ou[K]:=True;
Search(I-W[K],K+1);
Now:=Now-P[K];
Ou[K]:=False;
End;
End;
Begin
Init;
Search(M,1);
Assign(Output,'Output.txt'); {输出}
Rewrite(Output);
Writeln(Ans);
For U:=1 To N Do
If Out[U] Then Write(U,' ');
Writeln;
Close(Output);
End.
例18寻找国都名
给出一个矩阵及一些国都名：
o k d u b l i n dublin
a l p g o c e v tokyo
r a s m u s m b london
o s l o n d o n rome
y i b l g l r c bonn
k r z u r i c h paris
o a i b x m u z oslo
t p q g l a m v lima
要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。
输入：在文本文件input.txt中的第一行有一个整数M和N，表示该字符矩阵的长和宽。接下来就是M*N的字符矩阵。字符矩阵后有一个整数K，表示国家都名的个数，接下来的K行，每一行都是一个国都名。
输出：在文本文件output.txt中共有K行，第I行写入第I个国都名的起始位置及方向。起始位置用坐标表示，方向定义见图18。如没有找到国都名，输出‘No found’。
分析：将字符矩阵读入到二维数组，然后对每一个国都名进行搜索，首先需要在矩阵中找到国都名的第一个字符，然后沿八个方向进行搜索。直到找到国都名为止。若在矩阵中没有找到，则输出相应的信息。
在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了。
参考程序如下：
program exam18;
Const
Fx : Array[1..8,1..2] Of Shortint {定义八个方向}
=((0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1));
max = 100; {最大字符矩阵}
Finp = 'Input.Txt'; {输入文件名}
Fout = 'Output.Txt'; {输出文件名}
Var
A :Array[0..max+1,0..max+1] of Char;
{为了节约边界条件的判断，故增加边界范围}
B :Array[1..max,1..max] Of Boolean;
{标志数组，标志已经搜索过的路径}
S,
W :String;
N,M,I,J,K :Integer;
printed :Boolean;
Procedure Init;
Var
I,J :Integer;
Begin
Assign(Input,Finp); Reset(Input);
{采用重定向的手段，将输入文件与标准输入联系起来，
这样对标准输入（键盘）的操作，相当对输入文件的操作}
Assign(Output,Fout);Rewrite(Output);
{采用重定向的手段，将输出文件与标准输出联系起来，
这样对标准输出（屏幕）的操作，相当对输出文件的操作}
Readln(M,N);
For I:=1 To M Do Begin
For J:=1 To N Do Read(A[I,J]);
Readln;
End;
End;
Procedure Out;
Begin
write('(',J,',',k,')'); {输出起始位置的坐标}
Writeln('':5,W); {输出路径}
printed:=True {置已经打印的标志}
End;
Procedure Work(T,X,Y:Integer);
{搜索路径，T为国都名的字符位置，X，Y为当前搜索的坐标}
Var I : Integer;
Begin
If T=Length(S)+1 Then begin {搜索完，打印输出}
Out;
exit
end;
For I:=1 To 8 Do {八个方向进行搜索}
Begin
X:=X+Fx[I,1]; Y:=Y+Fx[I,2]; {坐标变化}
If (A[X,Y]=S[T])And(B[X,Y]) Then
Begin
W:=W+Chr(I+48); {记录路径}
B[X,Y]:=False; {设置已经搜索}
Work(T+1,X,Y); {继续搜索下一个}
Delete(W,Length(W),1);{恢复原路径}
B[X,Y]:=True; {恢复标志}
End;
X:=X-Fx[I,1]; Y:=Y-Fx[I,2]; {返回后，坐标恢复}
End;
End;
Begin
Init;
Readln(N);
For I:=1 To N Do {对所有的国都名进行处理}
Begin
Readln(S); {读入第I个国都名}
printed:=False;
Fillchar(B,Sizeof(B),True);{未搜索之前清标志数组}
For J:=1 To N Do begin {对字符矩阵进行搜索}
For K:=1 To N Do Begin
If printed Then Break; {已经打印了，跳出内循环}
If A[J,K]=S[1] Then Work(2,J,K);{从第一个字符开始搜}
End;
If printed Then Break; {已经打印了，跳出外循环}
end;
If Not printed Then Writeln('No found');
End;
Close(Input);
Close(Output);
End.
例19采用递归方法，求N个元素中取出M个的排列，。
（1）每个元素只能取一次。
（2）每个元素可以取任意多次（即可重复的排列）。
分析：此题用简单的递归搜索。设x[I]排列中的第I个元素，依次搜索每一个x[I]即可
program exam19;
const finp ='input.txt';
fout ='output.txt';
maxn =10;
var n,m :integer;
x :array[1..maxn]of integer; { x数组记录当前排列}
used:array[1..maxn]of boolean; {used[I]=True时表明第I个元素在当前排列中，反之亦然}
procedure init; {初始化输入}
var i :integer;
begin
write(‘input n, m:’); readln(n,m);
fillchar(used,sizeof(used),false)
end;
procedure pailie(i:integer); {搜索}
var j :integer;
begin
if i>m then begin
for j:=1 to m do write(x[j]:5);writeln; {输出一组解}
end else
for j:=1 to n do
if not used[j] then begin
used[j]:=true; {修改used[I]}
x[i]:=j; {记录x[i]}
pailie(i+1); {继续搜索排列的下一个}
used[j]:=false {还原used[I]}
end
end;
Begin
init;
pailie(1);
End.
（2）只需要将pailie过程中used标志数组 去掉即可，这样，已经取过的数据可以继续取。
修改如下：
procedure pailie(i:integer); {搜索x[I]}
var j :integer;
begin
if i>m then begin
for j:=1 to m do write(x[j]:5);writeln;{找到一组解，输出}
end else
for j:=1 to n do begin {枚举x[I]}
x[i]:=j; {记录x[I]}
pailie(i+1) {继续搜索x[I+1]}
end
end;
第六课 递推法
课题：递推法
目标：
知识目标：递推概念与利用递推解决实际问题
能力目标：递推方程
重点：递推方程
难点：递推方程写出
板书示意：
递推的理解（例20）
倒推法（例21）
顺推法（例22、例23）
授课过程：
递推就是逐步推导的过程。我们先看一个简单的问题。
例20：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。
分析：我们可以根据裴波那契数列的定义：从第2项开始，逐项推算，直到第N项。因此可以设计出如下算法：
F[0] := 1; F[1] := 2;
FOR I := 2 TO N DO
F[I] := F[I – 1] + F[I – 2];
从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。
对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。
递推分倒推法和顺推法两种形式。算法流程如下：
一、倒推法
所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标，根据递推关系，采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法。因为这类问题的运算过程是一一映射的，故可分析其递推公式。看看下面的例题。
例21：贮油点
一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？
编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：
No. Distance(k.m.) Oil(litre)
1 × × × ×
2 × × × ×
… … … … …
分析：
设Way[I]——第I个贮油点到终点（I=0）的距离；
oil[I]——第I个贮油点的贮油量；
我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。图19表示倒推时的返回点。
从贮油点I向贮油点I+1倒推的方法是：卡车在贮油点I和贮油点I+1间往返若干次。卡车每次返回I+1点时应该正好耗尽500公升汽油，而每次从I+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下，使I点贮足I*500公升汽油的要求（0≦I≦n-1）。具体来说，第一个贮油点I=1应距终点I=0处500km，且在该点贮藏500公升汽油，这样才能保证卡车能由I=1处到达终点I=0处，这就是说
Way[I]=500；oil[I]=500；
为了在I=1处贮藏500公升汽油，卡车至少从I=2处开两趟满载油的车至I=1处，所以I=2处至少贮有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上从I=1返回至I=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即d12=500/3km，Way[2]=Way[1]+d12=Way[I]+500/3
此时的状况如图20所示。
为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3处的二趟返程空车，合计5次。路途耗油亦应500公升，即d23=500/5，
Way[3]=Way[2]+d23=Way[2]+500/5；
此时的状况如图21所示。
依次类推，为了在I=k处贮藏k*500公升汽油，卡车至少从I=k+1处开k趟满载车至I=k处，即oil[k+1]=(k+1)*500=oil[k]+500，加上从I=k返回I=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即dk,k+1=500/(2k-1)，
Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)；
此时的状况如图22所示。
最后，I=n至始点的距离为1000-Way[n],oil[n]=500*n。为了在I=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至I=n，加上从I=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为（1000-Way[n]）*(2n+1)，即始点藏油为oil[n]+(1000-Way[n])*(2n+1)。
程序设计如下：
program Oil_lib;
var
K: Integer; {贮油点位置序号}
D, {累计终点至当前贮油点的距离}
D1: Real; {I=n至终点的距离}
Oil, Way: array [1 .. 10] of Real;
i: Integer;
begin
Writeln(‘No.’, ‘Distance’:30, ‘Oil’:80);
K := 1;
D := 500; {从I=1处开始向终点倒推}
Way[1] := 500;
Oil[1] := 500;
repeat
K := K + 1;
D := D + 500 / (2 * K – 1);
Way[K] := D;
Oil[K] := Oil[K – 1] + 500;
until D >= 1000;
Way[K] := 1000; {置始点到终点的距离值}
D1 := 1000 – Way[K – 1]; {求I=n处至至点的距离}
Oil[K] := D1 * (2 * k + 1) + Oil[K – 1]; {求始点贮油量}
{由始点开始，逐一打印至当前贮油点的距离和贮油量}
for i := 0 to K do
Writeln(i, 1000 – Way[K – i]:30, Oil[K – i]:80);
end.
二、顺推法
顺推法是从边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值……，依次类推，直至从问题初始陈述向前推进到这个问题的解为止。
看看下面的问题。
例22昆虫繁殖
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？x>=1,y>=1,z>=x
输入：x,y,z的数值
输出：成虫对数
事例：
输入：x=1 y=2 z=8
输出：37
分析：首先我们来看样例：每隔1个月产2对卵，求过8月（即第8+1=9月）的成虫个数
月份 1 2 3 4 5 6 7 8 9 …
新增卵 0 2 2 2 6 10 14 26 46 …
成虫 1 1 1 3 5 7 13 23 37 …
设数组A[i]表示第I月新增的成虫个数。
由于新成虫每过x个月产y对卵，则可对每个A[I]作如下操作:
A[i+k*x+2]:=A[i+k*x+2]+A[i]*y （1<=k, I+k*x+2<=z+1）
因为A [i]的求得只与A[1]~A[i-1]有关，即可用递推求法。
则总共的成虫个数为：
程序如下：
program exam22;
var x,y,z,i :integer;
ans :longint;
a :array[1..60]of longint;
procedure add(i:integer);
var j :integer;
begin
j:=i+2+x; {新生成虫要过x 个月才开始产卵，即第I+2+x个月才出现第一群新成虫}
repeat
a[j]:=a[j]+a[i]*y; {递推}
j:=j+x
until j>z+1
end;
begin
readln(x,y,z);
a[1]:=1; {初始化}
for i:=1 to z do add(i); {对每个A[I]进行递推}
ans:=0;
for i:=1 to z+1 do ans:=ans+a[i]; {累加总和}
writeln(ans);
end.
例23：实数数列（NOI94第3题）
一个实数数列共有N项，已知
ai=(ai-1-ai+1)/2+d，(1键盘输入N，d，a1，an，m，输出am。
输入数据均不需判错。
分析：
根据公式ai=(ai-1-ai+1)/2+d 变形得，ai+1=ai-1-2ai+2d，因此该数列的通项公式为：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，这样就可以根据公式递推求出am
∵ ai=ai-2-2ai-1+2d ……①
=ai-2-2（ai-3-2ai-2+2d）+2d
=-2ai-3+5（ai-4-2ai-3+2d）-2d
=5ai-4-12ai-3+8d
……
一直迭代下去，直到最后，可以建立ai和a1与a2的关系式。
设ai=Pia2+Qid+Ria1，我们来寻求Pi,Qi,Ri的变化规律。
∵ ai=ai-2-2ai-1+2d
∴ ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d
=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1
∴ Pi=Pi-2-2Pi-1 ……②
Qi=Qi-2-2Qi-1+2 ……③
Ri=Ri-2-2Ri-1 ……④
显然，P1=0 Q1=0 R1=1 （i=1）
P2=1 Q2=0 R2=0 （i=2）
将初值P1、Q1、R1和P2、Q2、R2代入②③④可以求出Pn、Qn、Rn
∵ an=Pna2+Qnd+Rna1
∴ a2=(an-Qnd+Rna1)/Pn
然后根据公式①递推求出am，问题解决。
但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过30时，求出的am就明显偏离正确值。显然，这种算法虽简单但不可靠。
为了减少误差，我们可设计如下算法：
∵ ai=Pia2+Qid+Ria1
=Pi-1a3+Qi-1d+Ri-1a2
=Pi-2a4+Qi-2d+Ri-2a3
……
=Pi-2+kak+Qi-2+kd+Ri-2+kak-1
∴ an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1
ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 ……⑤
根据公式⑤，可以顺推a2、a3、…、aM。虽然仍然存在实数误差，但由于Pn-k+2递减，因此最后得出的am要比直接利用公式①精确得多。
程序如下：
program NOI94_3;
const
MaxN = 60;
var
N, M, i: Integer;
D: Real;
A: array [1 .. MaxN] of Real;
F: array [1 .. MaxN, 1 .. 3] of Real;
{F[i,1]：对应Pi；F[i,2]：对应Qi；F[i,3]：对应Ri}
procedure Init;
begin
Write(‘N, M, D =’);
Readln(N, M, D); {输入项数、输出项序号和常数}
Write(‘A1, A’, N, ‘ =’);
Readln(A[1], A[N]); {输入a1和an}
end;
procedure Solve;
{根据公式PiPi-2-2*Pi-1,QiQi-2-2*Qi-1,RiRi-2-2*Ri-1求Pi、Qi、Ri }
begin
F[1, 1] := 0; F[1, 2] := 0; F[1, 3]:= 1;
F[2, 1] := 1; F[2, 2] := 0; F[2, 3] := 0;
for i := 3 to N do
begin
F[i, 1] := F[i – 2, 1] – 2 * F[i – 1, 1];
F[i, 2] := F[i – 2, 2] – 2 * F[i – 1, 2] + 2;
F[i, 3] := F[i – 2, 3] – 2 * F[i – 1, 3];
end;
end;
procedure Main;
begin
Solve;
{递推A2…Am}
for i := 2 to M do
A[i]:=(A[N]–F[N–i+2,2]*D–F[N–i+2,3]*A[i–1])/F[N–i+2,1];
Writeln(‘a’, m, ‘ =’, A[M]:20 :10);
end;
begin
Init;
Main;
end.
第七课 贪心法
课题：贪心法
目标：
知识目标：贪心的原理递与贪心的实现
能力目标：贪心的原理
重点：贪心算法的应用
难点：贪心的理解
板书示意：
贪心的引入（例24）
贪心的应用（例25、例26、例27、例28）
授课过程：
若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。
下面我们看一些简单例题。
例24：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。
分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:
读入N, M,矩阵数据；
Total := 0;
For I := 1 to N do begin {对N行进行选择}
选择第I行最大的数,记为K；
Total := Total + K；
End；
输出最大总和Total；
从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。
特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。
例25：部分背包问题
给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。
分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。
因此我们非常容易设计出如下算法：
问题初始化； {读入数据}
按Vi从大到小将商品排序；
I := 1;
repeat
if M = 0 then Break; {如果卡车满载则跳出循环}
M := M - Wi;
if M >= 0 then 将第I种商品全部装入卡车
else
将(M + Wi)重量的物品I装入卡车;
I := I + 1; {选择下一种商品}
until (M <= 0) OR (I >= N)
在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。
Program Exam25;
Const Finp='Input.Txt';
Fout='Output.Txt';
Var N,M :Longint;
S :Real;
P,W :Array[1..100] Of Integer;
Procedure Init; {输出}
Var I :Integer;
Begin
Assign(Input,Finp); Reset(Input);
Readln(M,N);
For I:=1 To N Do Readln(W[I],P[I]);
Close(Input);
End;
Procedure Sort(L,R:Integer); {按收益值从大到小排序}
Var I,J,Y :Integer;
X :Real;
Begin
I:=L; J:=R;
X:=P[(L+R) Div 2]/W[(L+R) Div 2];
Repeat
While (I=X) Do Inc(I);
While (P[J]/W[J]<=X)And(J>L) Do Dec(J);
If I<=J Then
Begin
Y:=P[I]; P[I]:=P[J]; P[J]:=Y;
Y:=W[I]; W[I]:=W[J]; W[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If IIf LEnd;
Procedure Work;
Var I :Integer;
Begin
Sort(1,N);
For I:=1 To N Do
If M>=W[I] Then {如果全部可取，则全取}
Begin
S:=S+P[I]; M:=M-W[I];
End
Else {否则取一部分}
Begin
S:=S+M*(P[I]/W[I]); Break;
End;
End;
Procedure Out; {输出}
Begin
Assign(Output,Fout); Rewrite(Output);
Writeln(S:0:0);
Close(Output);
End;
Begin {主程序}
Init;
Work;
Out;
End.
因此，利用贪心策略解题，需要解决两个问题：
首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：
可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。
其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。
下面来看看0-1背包问题。
给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。
分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。
即确定一组X1，X2，…，Xn， Xi∈{0,1}
f(x)=max(∑Xi*Vi) 其中，∑(Xi*Wi)≦W
从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（Vi/Wi）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些Vi/Wi最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子：
设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。
情况A：按照上述思路，三种动物的Vi/Wi分别为2,2,2.14。显然，我们首先选择动物C，得到价值150，然后任意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。
情况B：不按上述约束条件，直接选择A和B。可以得到价值80+100=180，卡车装载的重量为40+50=90。没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。
问题出现在什么地方呢？我们看看图2-18
从图23中明显可以看出，情况A，卡车的空载率比情况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。
因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。
例26排队打水问题
有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？
分析：由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：
将输入的时间按从小到大排序；
将排序后的时间按顺序依次放入每个水龙头的队列中；
统计，输出答案。
参考程序：
Program Exam26;
Const Finp='Input.Txt';
Fout='Output.Txt';
Var A :Array[1..100] Of Integer;
S :Array[1..100] Of Longint;
N,M :Integer;
Min :Longint;
Procedure Init; {读入数据}
Var I :Integer;
Begin
Assign(Input,Finp); Reset(Input);
Readln(N,M);
For I:=1 To N Do Read(A[I]);
Close(Input);
End;
Procedure Sort(L,R:Integer); {将时间从小到大排序}
Var I,J,X,Y :Integer;
Begin
I:=L; J:=R; X:=A[(L+R) Div 2];
Repeat
While (A[I]<=X)And(IWhile (A[J]>=X)And(J>L) Do Dec(J);
If I<=J Then
Begin
Y:=A[I]; A[I]:=A[J]; A[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If LIf R>I Then Sort(I,R);
End;
Procedure Work;
Var I,J,K :Integer;
Begin
Fillchar(S,Sizeof(S),0);
J:=0; Min:=0;
For I:=1 To N Do {用贪心法求解}
Begin
Inc(J);
If J=M+1 Then J:=1;
S[J]:=S[J]+A[I];
Min:=Min+S[J];
End;
Assign(Output,Fout); Rewrite(Output); {输出解答}
Writeln(Min);
Close(Output);
End;
Begin {主程序}
Init;
Sort(1,N);
Work;
End.
例27：旅行家的预算（NOI99分区联赛第3题）
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……，N）。
计算结果四舍五入至小数点后两位。
如果无法到达目的地，则输出“No Solution”。
样例：
Input
D1=275.6 C=11.9 D2=27.4 P=2.8 N=2
油站号I 离出发点的距离Di 每升汽油价格Pi
1 102.0 2.9
2 220.0 2.2
Output
26.95（该数据表示最小费用）
分析：需要考虑如下问题：
出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？
汽车行程到第几站开始加油，加多少油？
可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：
对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。
对于第一种情况，则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况，则需将油箱加满。
贪心算法证明如下：
设定如下变量：
Value[i]：第i个加油站的油价；
Over[i]：在第i站时的剩油；
Way[i]：起点到油站i的距离；
X[I]：X记录问题的最优解，X[I]记录油站I的实际加油量。
首先，X[1]≠0，Over[1]=0。
假设第I站加的X[I]一直开到第K站。则有，X[I]..x[k-1]都为0，而X[K]≠0。
若Value[I]>Value[k]，则按贪心方案，第I站应加油为
T=（Way[k]-Way[I]）/M-Over[I]。
若T若T>X[I], 则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用Value[I]*W，如果W加仑汽油在油站K加，则须费用Value[K]*W，显然Value[K]*W若Value[I]T=C-Over[I] （即加满油）。
若T若T>X[I]，则表示在第I站的不加满油，而将一部分油留待第K站加，而Value[I]综合上述分析，可以得出如下算法：
I := 1 {汽车出发设定为第1个加油站}
L := C*D2； {油箱装满油能行驶的距离}
repeat
在L距离以内，向后找第一个油价比I站便宜的加油站J；
if J存在 then
if I站剩余油能到达J then
计算到达J站的剩油
else
在I站购买油，使汽车恰好能到达J站
else
在I站加满油；
I := J； {汽车到达J站}
until 汽车到达终点；
程序如下：
program NOI99L_3;
const
Inp = ‘input.txt’;
Outp = ‘output.txt’;
MaxN = 10001; {最大油站数}
Zero = 1e-16; {误差值}
type
Rectype = record {油站的数据结构}
Value: Real; {油价}
Way: Real; {距起点的距离}
Over: Real; {汽车到达该站时的剩油}
end;
RecPtr = ︿Rectype; {油站指针}
var
Oil: array [1 .. MaxN] of RecPtr; {记录所有油站}
D1, {起点到终点之间的距离}
C, {汽车油箱的容量}
D2, {每升汽油能行驶的距离}
N: Integer; {油站数}
Cost: Real; {最小油费}
MaxWay, {满油时汽车最大的行驶距离}
function init: Boolean; {初始化，并判无解}
var
I: Integer;
begin
Read (D1, C, D2);
New(Oil[1]); {处理初始值和起始油站}
Oil[1]︿.Way := 0;
Read(Oil[1]︿.Value,n);
MaxWay := D2 * C;
for I := 2 to n do begin {读入后N-1个油站信息}
New(Oil[I]);
Readln(Oil[I]︿.Way, Oil[I]︿.Value);
Oil[I]︿.over:=0;
end;
Inc(n); {将终点也看成一个加油站}
New(Oil[n]);
Oil[n]︿.Way := D1;
Oil[n]︿.Value := 0;
Oil[n]︿.over:=0;
for I := 2 to n+1 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);;
{在I加油站购买Miles/D2加仑汽油}
begin
Cost:= Cost + Miles / D2 * Oil[I]︿.Value;
{将买汽油所需的费用加到Cost变量中}
end;
procedure Solve;
var
I, J: Integer;
S: Real;
begin
I := 1; {汽车在起点}
repeat
S := 0.0;
{在MaxWay范围以内，找第一个油价比I站便宜的加油站J}
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 {如果找到J站或可以直达终点}
{如果剩油足够到达J站，则无需购油，并计算到达J站时汽车的剩油}
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
{在I站购买恰好能到达J站的油量}
Buy(I,Oil[J]︿.Way – Oil[I]︿.Way – Oil[I]︿.Over);
Oil[J]︿.Over := 0.0;
end
else begin {附近无比I站便宜的加油站J}
Buy(I, MaxWay – Oil[I]︿.Over); {在I站加满油}
J := I + 1; {行驶到下一站}
Oil[J]︿.Over:= MaxWay – (Oil[J]︿.Way – Oil[I]︿.Way);
end;
I := J; {汽车直达J站}
until I = N; {汽车到达终点}
end;
begin {主程序}
Cost := 0;
Assign(Input, Inp);
Reset(Input);
Assign(Output, Outp);
Rewrite(Output);
if init then begin {如果有解}
Solve; {求解}
Writeln(Cost:0 :2); {输出最少费用}
end else
Writeln(‘No Solution’); {输出无解}
Close(Input);
Close(Output);
end.
例28：两机器加工问题
有n个部件需在A，B机器上加工，每个工件都必须经过先A后B两道工序。
已知：部件i在A、B机器上的加工时间分别为ai，bi。
问：如何安排n个工件的加工顺序，才能使得总加工时间最短？
输入示例：
N = 5
工件I 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
输出示例：
34 （最少时间）
1 5 4 2 3 （最优加工顺序）
分析：
本题求一个加工顺序使得加工总时间最短，要使时间最短，则就是让机器的空闲时间最短。一旦A机器开始加工，则A机器将会不停的进行作业，关键是B机器在加工过程中，有可能要等待A机器。很明显第一个部件在A机器上加工时，B机器必须等待，最后一个部件在B机器上加工，A机器也在等待B机器的完工。
可以大胆猜想，要使总的空闲的最少，就要把在A机器上加工时间最短的部件最先加工，这样使得B机器能以最快的速度开始加工；把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：
设Mi=min{ai, bi}
将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的已经作业后面，若Mi=bi，则将它排在从尾开始的作业前面。
例如：N=5
（a1，a2，a3，a4，a5）=（3，5，8，7，10）
（b1，b2，b3，b4，b5）=（6，2，1，4，9）
则（m1，m2，m3，m4，m5）=（3，2，1，4，9）
排序之后为（m3，m2，m1，m4，m5）
处理m3：∵m3=b3 ∴m3排在后面；加入m3之后的加工顺序为（ ， ， ， ，3）；
处理m2：∵m2=b2 ∴m2排在后面；加入m2之后的加工顺序为（ ， ， ，2，3）；
处理m1：∵m3=a1 ∴m1排在前面；加入m1之后的加工顺序为（1， ， ，2，3）；
处理m4：∵m4=b4 ∴m4排在后面；加入m4之后的加工顺序为（1， ，4，2，3）；
处理m5：∵m5=b5 ∴m5排在后面；加入m5之后的加工顺序为（1，5，4，2，3）；
则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。
问题是这种贪心策略是否正确呢？还需证明。
证明过程如下：
设S={J1，J2，……，Jn}，为待加工部件的作业排序，若A机器开始加工S中的部件时，B机器还在加工其它部件，t时刻后再可利用，在这样的条件下，加工S中任务所需的最短时间T（S，t）= min{ai+T(S-{Ji},bi+max{t-ai,0})} 其中，Ji∈S。
从图24可以看出，（a）为作业I等待机器B的情况，（b）为机器B等待作业I在机器A上完成的情形。
假设最佳的方案中，先加工作业Ji，然后加工作业Jj，则有：
T(S,t)=ai+T(S-{Ji},bi+Max{t-ai,0})
=ai+aj+T(S-{Ji,Jj},bj+max{bi+max{t-ai,0}-aj,0})
=ai+aj+T(S-{Ji,Jj},Tij)
Tij=bj+max{bi+max{t-ai,0}-aj,0}
=bj+bi-aj+max{max{t-ai,0},aj-bi}
=bi+bj-aj+max{t-ai,aj-bi,0}
=bi+bj-ai-aj+max{t,ai,ai+aj-bi}
若max{t,ai,ai+aj-bi}=t
若max{t,ai,ai+aj-bi}=ai
若max{t,ai,ai+aj-bi}=ai+aj-bi
若将作业Ji和作业Jj的加工顺序，则有：
T’(S,t)=ai+aj+T(S-(Ji,Jj),Tji)，其中
Tji=bi+bj-ai-aj+max{t,aj,ai+aj-bj}
按假设，因为T<=T’,所以有:
max{t,ai+aj-bi,ai}<=max{t,ai+aj-bj,aj} ……………… ①
于是有：
ai+aj+max{-bi,-aj}<=ai+aj+max{-bj,-ai}
即
Min{bj,ai}<=min{bi,aj} ……………… ②
②式便是Johnson公式。也就是说②式成立的条件下，任务Ji安排在任务Jj之前加工可以得到最优解。也就是说在A机器上加工时间短的任务应优先，而在B机器上加工时间短的任务应排在后面。因此，论证了开始设计的贪心算法是正确的。
算法流程如下：
for I := 1 to N do {求M数组}
if A[I] < B[I] then
M[I] := A[I]
else
M[I] := B[I]；
将M从小到大排序；
S := 1; T := N; {首位指针初始化}
for I := 1 to N do
if 对于第I小的工序J，若A[J] < B[J] then begin
Order[S] := J; {将工序J插在加工序列的前面}
S := S + 1;
end else begin
Order[T] := J; {将工序J插在加工序列的后面}
T := T - 1;
end;
程序如下：
program Machine;
const
Inp = 'input.txt';
Outp = 'output.txt';
MaxN = 100; {最多部件数}
var
N, Min: Integer;
A, B, M,
O, {O用来记录从小到大排序后部件的编号}
Order: array [1 .. MaxN] of Integer; {Order用来记录加工顺序}
procedure Init; {读入数据}
var
I: Integer;
begin
Assign(Input, Inp); Reset(Input);
Readln(N);
for I := 1 to N do
Read(A[I]);
Readln;
for I := 1 to N do
Read(B[I]);
Close(Input);
end;
procedure Main;
var
I, J, Z, S, T, T1, T2: Integer;
begin
FillChar(M, Sizeof(M), 0); {求M数组的值}
for I := 1 to N do
if A[I] < B[I] then M[I] := A[I] else M[I] := B[I];
for I := 1 to N do O[I] := I;
for I := 1 to N - 1 do {从小到大排序}
for J := I + 1 to N do
if M[O[I]] > M[O[J]] then begin
Z := O[I]; O[I] :=O[J]; O[J] := Z;
end;
FillChar(Order, Sizeof(Order), 0);
S := 1; T := N;
for I := 1 to N do
if M[O[I]] = A[O[I]] then begin
{若A[O[I]]Order[S] := O[I];
S := S + 1;
end else begin
{若B[O[I]]≧A[O[I]]，则插在加工序列的后面}
Order[T] := O[I];
T := T - 1;
end;
{计算最少加工时间}
T1 := 0; T2 := 0;
for I := 1 to N do begin
T1 := T1 + A[Order[I]];
if T2 < T1 then T2 := T1;
T2 := T2 + B[Order[I]];
end;
Min := T2;
end;
procedure Out; {打印输出}
var I: Integer;
begin
Assign(Output, Outp); Rewrite(Output);
Writeln(Min); {输出最少时间}
for I := 1 to N do {输出最佳加工序列}
Write(Order[I], ' ');
Writeln;
Close(Output);
end;
Begin
Init; {输入}
Main; {主过程}
Out; {输出}
End.
第八课 分治法
课题：分治法
目标：
知识目标：分治的原理与分治
TOC \o "1-1" \h \z \u 第一课 算法简介 1
HYPERLINK \l "_Toc66721565" 第二课 多精度数值处理 1
第三课 排列与组合 6
HYPERLINK \l "_Toc66721567" 第四课 枚举法 9
第五课 递归与回溯法 25
HYPERLINK \l "_Toc66721569" 第六课 递推法 42
第七课 贪心法 50
HYPERLINK \l "_Toc66721571" 第八课 分治法 64
第九课 模拟法 70
HYPERLINK \l "_Toc66721573" 习题 79
第一课 算法简介
算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征：
有穷性：一个算法必须能在执行有限步之后结束；
确切性：算法的每一步骤必须确切定义；
输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件；
输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的；
可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。
为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。
第二课 多精度数值处理
课题：多精度数值的处理
目标：
知识目标：多精度值的加、减、乘、除
能力目标：多精度值的处理，优化！
重点：多精度的加、减、乘
难点：进位与借位处理
板书示意：
输入两个正整数，求它们的和
输入两个正整数，求它们的差
输入两个正整数，求它们的积
输入两个正整数，求它们的商
授课过程：
所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。
例1 从键盘读入两个正整数，求它们的和。
分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。
这样，我们方便写出两个整数相加的算法。
如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上例有
A[1]=6, A[2]=5, A[3]=8, B[1]=5,B[2]=5, B[3]=2, C[4]=1,C[3]=1, C[2]=1,C[1]=1,两数相加如图2所示。由上图可以看出：
C[i]:= A[i]+B[i];
if C[i]>10 then begin C[i]:= C[i] mod 10; C[i+1]:= C[i+1]+1 end;
因此，算法描述如下：
procedure add(a,b;var c);
{ a,b,c都为数组，a存储被加数，b存储加数，c存储结果 }
var i,x:integer;
begin
i:=1
while (i<=a数组长度>0) or(i<=b数组的长度) do begin
x := a[i] + b[i] + x div 10; {第i位相加并加上次的进位}
c[i] := x mod 10; {存储第i位的值}
i := i + 1 {位置指针变量}
end
end;
通常，读入的两个整数用可用字符串来存储，程序设计如下：
program exam1;
const
max=200;
var
a,b,c:array[1..max] of 0..9;
n:string;
lena,lenb,lenc,i,x:integer;
begin
write('Input augend:'); readln(n);
lena:=length(n); {加数放入a数组}
for i:=1 to lena do a[lena-i+1]:=ord(n[i])-ord('0');
write('Input addend:'); readln(n);
lenb:=length(n); {被加数放入b数组}
for i:=1 to lenb do b[lenb-i+1]:=ord(n[i])-ord('0');
i:=1;
while (i<=lena) or(i<=lenb) do begin
x := a[i] + b[i] + x div 10; {两数相加，然后加前次进位}
c[i] := x mod 10; {保存第i位的值}
i := i + 1
end;
if x>=10 then {处理最高进位}
begin lenc:=i;c[i]:=1 end
else lenc:=i-1;
for i:=lenc downto 1 do write(c[i]); {输出结果}
writeln
end.
例2 高精度减法。
从键盘读入两个正整数，求它们的差。
分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。
因此，可以写出如下关系式
if a[i]
类似，高精度减法的参考程序：
program exam2;
const
max=200;
var
a,b,c:array[1..max] of 0..9;
n,n1,n2:string;
lena,lenb,lenc,i,x:integer;
begin
write('Input minuend:'); readln(n1);
write('Input subtrahend:'); readln(n2);
{处理被减数和减数}
if (length(n1)
n:=n1;n1:=n2;n2:=n;
write('-') {n1
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');
i:=1;
while (i<=lena) or(i<=lenb) do begin
x := a[i] - b[i] + 10 + x; {不考虑大小问题，先往高位借10}
c[i] := x mod 10 ; {保存第i位的值}
x := x div 10 - 1; {将高位借掉的1减去}
i := i + 1
end;
lenc:=i;
while (c[lenc]=0) and (lenc>1) do dec(lenc); {最高位的0不输出}
for i:=lenc downto 1 do write(c[i]);
writeln
end.
例3 高精度乘法。
从键盘读入两个正整数，求它们的积。
分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运算时，必须进行错位相加，如图3, 图4。
分析C数组下标的变化规律，可以写出如下关系式
C i = C’ i +C ”i +…
由此可见，C i跟A[i]*B[j]乘积有关，跟上次的进位有关，还跟原C i的值有关，分析下标规律，有
x:= A[i]*B[j]+ x DIV 10+ C[i+j-1];
C[i+j-1] := x mod 10;
类似，高精度乘法的参考程序：
program exam3;
const
max=200;
var
a,b,c:array[1..max] of 0..9;
n1,n2:string;
lena,lenb,lenc,i,j,x:integer;
begin
write('Input multiplier:'); readln(n1);
write('Input multiplicand:'); readln(n2);
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');
for i:=1 to lena do begin
x:=0;
for j:=1 to lenb do begin {对乘数的每一位进行处理}
x := a[i]*b[j] + x div 10 + c[i+j-1]; {当前乘积+上次乘积进位+原数}
c[i+j-1] := x mod 10;
end;
c[i+j]:= x div 10; {进位}
end;
lenc:=i+j;
while (c[lenc]=0) and (lenc>1) do dec(lenc);
for i:=lenc downto 1 do write(c[i]);
writeln
end.
例４ 高精度除法。
从键盘读入两个正整数，求它们的商（做整除）。
分析：做除法时，每一次上商的值都在０～９，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用0～9次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。
参考程序：
program exam4;
const
max=200;
var
a,c:array[1..max] of 0..9;
x,b:longint;
n1,n2:string;
lena:integer;
code,i,j:integer;
begin
write('Input dividend:'); readln(n1);
write('Input divisor:'); readln(n2);
lena:=length(n1);
for i:=1 to lena do a[i] := ord(n1[i]) - ord('0');
val(n2,b,code);
{按位相除}
x:=0;
for i:=1 to lena do begin
c[i]:=(x*10+a[i]) div b;
x:=(x*10+a[i]) mod b;
end;
{显示商}
j:=1;
while (c[j]=0) and (j
writeln
end.
实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。例如图5就是采用4位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以解决，程序请读者完成。
第三课 排列与组合
课题：排列与组合
目标：
知识目标：如何利用程序就各种排列和组合
能力目标：排列组合的运用
重点：求出n的全排列和从m中取n个的组合
难点：算法的理解
板书示意：
求全排列的算法
求组合数的算法
授课过程：
例5：有3个人排成一个队列，问有多少种排对的方法，输出每一种方案？
分析：如果我们将3个人进行编号，分别为1、2、3，显然我们列出所有的排列，123，132，213，231，312，321共六种。可用循环枚举各种情况，参考程序：
program exam5;
var
i,j,k:integer;
begin
for I:=1 to 3 do
for j:=1 to 3 do
for k:=1 to 3 do
if (i+j+k=6) and (i*j*k=6) then writeln(i,j,k);
end.
上述情况非常简单，因为只有3个人，但当有N个人时怎么办？显然用循环不能解决问题。下面我们介绍一种求全排列的方法。
设当前排列为P1 P2 ,…,Pn，则下一个排列可按如下算法完成：
1．求满足关系式Pj-1 < Pj的J的最大值，设为I，即
I=max{j | Pj-1 < Pj , j = 2..n}
2．求满足关系式Pi -1 < Pk的k的最大值，设为j，即
J=max{K | Pi-1 < Pk , k = 1..n}
3．Pi -1与Pj互换得 (P) = P1 P2 ,…,Pn
4．(P) = P1 P2 ,…, Pi-1 Pi,…, Pn部分的顺序逆转，得P1 P2 ,…, Pi-1 Pn Pn-1,…, Pi便是下一个排列。
例：设P1 P2 P3 P4 =3421
1．I= max{j | Pj-1 < Pj , j = 2..n} = 2
2．J=max{K | Pi-1 < Pk , k =1..n} = 2
3．P1与P2交换得到4321
4．4321的321部分逆转得到4123即是3421的下一个排列。
程序设计如下：
program exam5;
const
maxn = 100;
var i,j,m,t : integer;
p : array[1..maxn] of integer;
count :integer; {排列数目统计变量}
begin
write('m:');readln(m);
for i:=1 to m do begin p[i]:=i; write(i) end;
writeln;
count:=1;
repeat
{求满足关系式Pj-1 < Pj的J的最大值，设为I}
i:=m;
while (i>1) and (p[i-1]>=p[i]) do dec(i);
if i=1 then break;
{求满足关系式Pi -1 < Pk的k的最大值，设为j}
j:=m;
while (j>0) and (p[i-1]>=p[j]) do dec(j);
if j=0 then break;
{Pi -1与Pj互换得 (P) = P1 P2 ,…,Pm}
t:=p[i-1];p[i-1]:=p[j];p[j]:=t;
{Pi,…, Pm的顺序逆转}
for j:=1 to (m-i+1) div 2 do begin
t:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=t
end;
{打印当前解}
for i:=1 to m do write(p[i]);
inc(count);
writeln;
until false;
writeln(count)
End.
例6：求N个人选取M个人出来做游戏，共有多少种取法？例如：N=4，M=2时，有12，13，14，23，24，34共六种。
分析：因为组合数跟顺序的选择无关。因此对同一个组合的不同排列，只需取其最小的一个（即按从小到大排序）。因此，可以设计如下算法：
1．最后一位数最大可达N，倒数第二位数最大可达N-1，…，依此类推，倒数第K位数最大可达N-K+1。
若R个元素组合用C1C2 …CR表示，且假定C1
参考程序：
program exam6;
const maxn=10;
var i,j,n,m :integer;
c :array[1..maxn]of integer; {c数组记录当前组合}
Begin
Write('n & m:'); readln(n,m);
for i:=1 to m do begin {初始化，建立第一个组合}
c[i]:=i;
write(c[i]);
end;
writeln;
while c[1]
while (c[j]>n-m+1) and ( j>0) do dec(j); {求I=max{J | Cj
for i:=j+1 to m do c[i]:=c[i-1]+1; {建立下一个组合}
for i:=1 to m do write(c[i]);writeln {输出}
end;
End.
第四课 枚举法
课题：枚举法
目标：
知识目标：枚举算法的本质和应用
能力目标：枚举算法的应用！
重点：利用枚举算法解决实际问题
难点：枚举算法的次数确定
板书示意：
简单枚举（例7、例8、例9）
利用枚举解决逻辑判断问题（例10、例11）
枚举解决竞赛问题（例12、例13、例14）
授课过程：
所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：
对命题建立正确的数学模型；
根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；
利用循环语句、条件判断语句逐步求解或证明；
枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。
例7：求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。
分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下：
for A := 1 to 3 do
for B := 1 to 3 do
for C := 1 to 3 do
if A + B = C then
Writeln(A, ‘+’, B, ‘=’, C);
上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。
从枚举法的定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在采用枚举法求解的问题时，必须满足两个条件：
预先确定解的个数n；
对每个解变量A1，A2，……，An的取值，其变化范围需预先确定
A1∈{X11，……，X1p}
……
Ai∈{Xi1，……，Xiq}
……
An∈{Xn1，……，Xnk}
例7中的解变量有3个：A，B，C。其中
A解变量值的可能取值范围A∈{1，2，3}
B解变量值的可能取值范围B∈{1，2，3}
C解变量值的可能取值范围C∈{1，2，3}
则问题的可能解有27个
（A，B，C）∈{（1，1，1），（1，1，2），（1，1，3），
（1，2，1），（1，2，2），（1，2，3），
………………………………
（3，3，1），（3，3，2），（3，3，3）}
在上述可能解集合中，满足题目给定的检验条件的解元素，即为问题的解。
如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用搜索等算法求解。由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问题，回溯算法要比枚举法时间复杂度稍高。
例8 给定一个二元一次方程aX+bY=c。从键盘输入a,b,c的数值，求X在[0，100]，Y在[0，100]范围内的所有整数解。
分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看这些点是否满足方程即可。参考程序：
program exam8;
var
a,b,c:integer;
x,y:integer;
begin
write('Input a,b,c:');readln(a,b,c);
for x:=0 to 100 do
for y:=0 to 100 do
if a*x+b*y=c then writeln(x,' ',y);
end.
从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。
例9 巧妙填数
1 9 2
3 8 4
5 7 6
将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。如图6:
图6
分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。
但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：
program exam9;
var
i,j,k,s:integer;
function sum(s:integer):integer;
begin
sum:=s div 100 + s div 10 mod 10 + s mod 10
end;
function mul(s:integer):longint;
begin
mul:=(s div 100) * (s div 10 mod 10) * (s mod 10)
end;
begin
for i:=1 to 3 do
for j:=1 to 9 do
if j<>i then for k:=1 to 9 do
if (k<>j) and (k<>i) then begin
s := i*100 + j*10 +k; {求第一行数}
if 3*s<1000 then
if (sum(s)+sum(2*s)+sum(3*s)=45) and
(mul(s)*mul(2*s)*mul(3*s)=362880) then {满足条件，并数字都由1~9组成}
begin
writeln(s);
writeln(2*s);
writeln(3*s);
writeln;
end;
end;
end.
例10 在某次数学竞赛中, A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名？
条件1: 你如果认为A, B, C, D, E 就是这些人的第一至第五名的名次排列, 便大错。因为:
没猜对任何一个优胜者的名次。
也没猜对任何一对名次相邻的学生。
条件2: 你如果按D, A , E , C , B 来排列五人名次的话, 其结果是:
说对了其中两个人的名次。
还猜中了两对名次相邻的学生的名次顺序。
分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。
根据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一种可能性，只有4！=24种情况了。
参考程序：
Program Exam10;
Var
A,B,C,D,E :Integer;
Cr :Array[1..5] Of Char;
Begin
For A:=1 To 5 Do
For B:=1 To 5 Do
For C:=1 To 5 Do
For D:=1 To 5 Do
For E:=1 To 5 Do Begin
{ABCDE没猜对一个人的名次}
If (A=1) Or (B=2) Or (C=3) Or (D=4) Or (E=5) Then Continue;
If [A,B,C,D,E]<>[1,2,3,4,5] Then Continue;{他们名次互不重复}
{DAECB猜对了两个人的名次}
If Ord(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2 Then Continue;
{ABCDE没猜对一对相邻名次}
If (B=A+1) Or (C=B+1) Or (D=C+1) Or (E=D+1) Then Continue;
{DAECB猜对了两对相邻人名次}
If Ord(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2 Then Continue;
Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';
Cr[D]:='D';Cr[E]:='E';
Writeln(Cr[1],' ',Cr[2],' ',Cr[3],' ',Cr[4],' ',Cr[5]);
End;
End.
例11：来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况是, 没有人既会日语又会法语;A会日语,但D不会,A和D能互相交谈,B不会英语,但A和C交谈时却要B当翻译,B,C,D三个想互相交谈,但找不到共同的语言,只有一种语言3人都会,编程确定A,B,C,D四位留学生各会哪两种语言。
分析：将中、法、日、英四种语言分别定义为CHN、FRH、JPN、ENG,则四种语言中取两种共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),( ENG,FRH),( ENG,JPN),(FRH,JPN)六种组合，分别定义为1、2、3、4、5、6。据已知，没有人既会日语又会法语;因此，组合6不会出现；A 会日语，所以A只可能等于3、5；D不会日语, 所以D只可能等于1、2、4；B不会英语，所以B只可能等于2、3；见下表。如果我们对A、B、C、D分别进行枚举，根据判定条件，即可找到答案。
(CHN,ENG) (CHN,FRH) (CHN,JPN) ( ENG,FRH) ( ENG,JPN)
A × × ×
B × × ×
C
D × ×
程序如下：
program EXAM11;
type
Language = (CHN,ENG,FRH,JPN);
TNoSet= set of Language;
const
No: array [1 .. 5] of TNoSet=
([CHN,ENG], [CHN,FRH], [CHN,JPN], [ENG,FRH], [ENG,JPN]);
var
A, B, C, D: 1 .. 5;
Can1, Can2, Can3, Can4: Boolean;
function Might(Lang: Language): Boolean;
var
Bool: Boolean;
begin
Bool:=false;
if No[A] * No[A] * No[C] = [Lang] then Bool := True;
if No[A] * No[B] * No[D] = [Lang] then Bool := True;
if No[A] * No[C] * No[D] = [Lang] then Bool := True;
if No[B] * No[C] * No[D] = [Lang] then Bool := True;
Might := Bool
end;
procedure Print(A, B, C, D: Integer);
procedure Show(P: Integer; Ch: Char);
var
I: Integer;
Lang: Language;
begin
Write(ch,':');
for Lang := CHN to JPN do
if Lang in No[P] then
case Lang of
CHN: Write('CHN':5);
FRH: Write('FRH':5);
JPN: Write('JPN':5);
ENG: Write('ENG':5);
end;
Writeln;
end;
begin
Show(A, 'A');
Show(B, 'B');
Show(C, 'C');
Show(D, 'D');
end;
begin
for A := 3 to 5 do
if A <> 4 then for B := 2 to 3 do
for C := 1 to 5 do
for D := 1 to 4 do if D <> 3 then begin
{A和D能互相交谈}
Can1 := No[A] * No[D] <> [];
{A和C交谈时却要B当翻译}
Can2 := (No[A] * No[C] = []) and (No[A] * No[B] <> [])
and (No[B] * No[C] <> []);
{B,C,D三个想互相交谈,但找不到共同的语言}
Can3 := No[B] * No[C] * No[D] = [];
{只有一种语言3人都会}
Can4 := Ord(Might(CHN)) + Ord(Might(ENG))
+ Ord(Might(FRH)) + Ord(Might(JPN)) = 1;
if Can1 and Can2 and Can3 and Can4 then Print(A,B,C,D);
end;
end.
例12 古纸残篇
在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了, 只留下曾经写过字的痕迹, 依稀还可以看出它是一个乘法算式, 如图7所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来。难道说, 这个算式与素数有什么关系吗？有人对此作了深入的研究, 果然发现这个算式中的每一个数字都是素数, 而且这样的算式是唯一的。请你也研究一番, 并把这个算式写出来。
分析：实际上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被乘数的每一位。然后再判断是不是满足条件即可。计算量是45=1024，对于计算机来说，计算量非常小。
参考程序：
Program Exam12;
Const
Su : Array[1..4] Of Longint=(2,3,5,7);
Var
A1,A2,A3,B1,B2,X,Y,S :Longint;
Function Kx(S:Longint):Boolean;{判断一个数
是不是都是由素数组成}
Begin
Kx:=True;
While S<>0 Do Begin
If Not((S Mod 10) In [2,3,5,7]) Then Begin
Kx:=False;
Exit;
End;
S:=S Div 10;
End;
End;
Begin
For A1:=1 To 4 Do
For A2:=1 To 4 Do
For A3:=1 To 4 Do
For B1:=1 To 4 Do
For B2:=1 To 4 Do Begin
X:=Su[A1]*100+Su[A2]*10+Su[A3];{X为被乘数}
If X*Su[B1]<1000 Then Continue;
If X*Su[B2]<1000 Then Continue;
If X*(Su[B1]*10+Su[B2])<10000 Then Continue;
{它们分别是两个四位数，一个五位数}
If (Kx(X*Su[B1])=False) Or
(Kx(X*Su[B2])=False) Or
(Kx(X*(Su[B1]*10+Su[B2]))=False) Then Continue;
{满足其他数都是由质数构成}
Writeln(' ',Su[A1],Su[A2],Su[A3]);
Writeln('* ',Su[B1],Su[B2]);
Writeln('-----------');
Writeln(' ',X*Su[B2]);
Writeln(' ',X*Su[B1]);
Writeln('-----------');
Writeln(' ',X*(Su[B1]*10+Su[B2]));
End;
End.
例13：时钟问题（IOI94-4）
在图8所示的3*3矩阵中有9个时钟，我们的目标是旋转时钟指针，使所有时钟的指针都指向12点。允许旋转时钟指针的方法有9种，每一种移动用一个数字号（1，2，…，9）表示。图2-11示出9个数字号与相应的受控制的时钟，这些时钟在图中以灰色标出，其指针将顺时针旋转90度。
输入数据：
由输入文件INPUT.TXT读9个数码，这些数码给出了9个时钟时针的初始位置。数码与时刻的对应关系为：
0——12点
1——3点
2——6点
3——9点
图2-11中的例子对应下列输入数据：
330
222
212
输出数据：
将一个最短的移动序列（数字序列）写入输出文件OUTPUT.TXT中，该序列要使所有的时钟指针指向12点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的OUTPUT.TXT的内容为：
5849
输入输出示例：
INPUT.TXT OUTPUT.TXT
330222212 5489
具体的移动方案如图10所示。
分析：
首先，我们分析一下表示时钟时针初始位置的数码j（0≦j≦3）与时刻的对应关系：
0——12点
1——3点
2——6点
3——9点
每移动一次，时针将顺时针旋转90度。由此我们可以得出：
对于任意一个时钟i（1≦i≦9）来说，从初始位置j出发至少需要Ci=（4-j） mod 4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。
移动方案选取与顺序无关。样例中，最佳移动序列为5849，同样4589序列也可达到目标。因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。
设 pi表示第i种旋转方法的使用次数（0≦pi≦3，1≦i≦9）。
则可能的解的集合为{P1，P2，……，P9}，该集合共含49个状态。从图2.11中，我们可以分析出9个时钟分别被哪些方法所控制，见下表：
时钟号 控制时钟方案 检验条件
1 1、2、4 C1=(P1+P2+P4) mod 4
2 1、2、3、5 C2=(P1+P2+P3+P5) mod 4
3 2、3、6 C3=(P2+P3+P6) mod 4
4 1、4、5、7 C4=(P1+P4+P5+P7) mod 4
5 1、3、5、7、9 C5=(P1+P3+P5+P7+P9) mod 4
6 3、5、6、9 C6=(P3+P5+P6+P9) mod 4
7 4、7、8 C7=(P4+P7+P8) mod 4
8 5、7、8、9 C8=(P5+P7+P8+P9) mod 4
9 6、8、9 C9=(P6+P8+P9) mod 4
因此我们可以设计如下枚举算法：
for p1:=0 to 3 do
for p2:=0 to 3 do
... ... ...
for p9:=0 to 3 do
if c1满足时钟1 and c2满足时钟2 and ... and c9满足时钟9 then
打印解路径；
显然，上述枚举算法枚举了所有49=262144个状态，运算量和运行时间颇大。我们可以采取缩小可能解范围的局部枚举法，仅枚举第1、2、3种旋转方法可能取的43个状态，根据这三种旋转方法的当前状态值，由下述公式
P4=order(C1-P1-P2);
P5=order(C2-P1-P2-P3);
P6=order(C3-P2-P3);
P7=order(C4-P1-P4-P5);
P8=order(C8-P5-PP9);
P9=order(C6-P3-P5-P6);
其中
得出其余P4……P9的相应状态值。然后将P1，P2，…，P9代入下述三个检验条件
C5=(P1+P3+P5+P7+P9) mod 4
C7=(P4+P7+P8) mod 4
C9=(P6+P8+P9) mod 4
一一枚举，以求得确切解。
由此可见，上述局部枚举的方法（枚举状态数为43个）比较全部枚举的方法（枚举状态数为49个）来说，由于大幅度削减了枚举量，减少运算次数，因此其时效显著改善，是一种优化了的算法。
程序如下：
program IOI94_4;
const
Inp = 'input.txt';
Outp = 'output.txt';
var
Clock, Map: array [1 .. 3, 1 .. 3] of Integer;
{Clock：第((I+2)mod 3)*3+J个时钟从初始时间到12点的最少移动次数}
{Map:最短移动序列中，数字（（I+2）mod 3）*3+J的次数}
procedure Init;
var
I, J: Integer;
begin
Assign(Input, Inp); Reset(Input);
for I := 1 to 3 do
{读入9个时钟指针的初始位置，求出每个时钟从初始到12点的最少移动次数}
for J := 1 to 3 do begin
Read(Clock[I, J]);
Clock[I, J] := (4 - Clock[I, J]) mod 4;
end;
Close(Input);
end;
function Order(K: Integer): Integer;
var
c: Integer;
begin
c:=k;
while c<0 do inc(c,4);
while c>4 then dec(c,4);
Order := k;
end;
procedure Main; {计算和输出最短移动序列}
var
I, J, K: Integer;
begin
{枚举最短移动序列中数字1、2、3的个数可能取的43种状态}
Assign(Output, Outp); Rewrite(Output);
for Map[1, 1] := 0 to 3 do
for Map[1, 2] := 0 to 3 do
for Map[1, 3] := 0 to 3 do begin
Map[2,1]:=Order(Clock[1,1]-Map[1,1]-Map[1,2]);
Map[2,3]:=Order(Clock[1,3]-Map[1,2]-Map[1,3]);
Map[2,2]:=Order(Clock[1,2]-Map[1,1]-Map[1,2]-Map[1, 3]);
Map[3,1]:=Order(Clock[2,1]-Map[1,1]-Map[2,1]-Map[2, 2]);
Map[3,3]:=Order(Clock[2,3]-Map[1,3]-Map[2,2]-Map[2, 3]);
Map[3,2]:=Order(Clock[3,2]-Map[3,1]-Map[3,3]-Map[2, 2]);
{根据数字1、2、3个数的当前值，得出数字4~9的个数}
if ((Map[2,1]+Map[3,1]+Map[3,2])mod 4=Clock[3,1]) and
((Map[2,3]+Map[3,2]+Map[3,3])mod 4=Clock[3, 3])and
((Map[2,2]+Map[1,1]+Map[1,3]+Map[3,1]+Map[3, 3])
mod 4 = Clock[2, 2])
then begin {若数字4~9的个数满足检验条件，则输出方案}
for I := 1 to 3 do
for J := 1 to 3 do
for K := 1 to Map[I, J] do
Write((I - 1) * 3 + J);
Exit; {找到一个解后退出}
end;
end;
Writeln('No Answer !');
Close(Output);
end;
begin
Init;
Main;
end.
在上例中，由于事先能够排除那些明显不属于解集的元素，使得算法效率非常高。而减少重复运算、力求提前计算所需数据、使用恰当的数据结构进行算法优化等方法也是优化枚举算法的常用手段。
例14：最佳游览线路 （NOI94）
某旅游区的街道成网格状（图2.13）。其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。
阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的街道值得游览的程度，分值时从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。
例如图11是被打过分的某旅游区的街道图：
阿龙可以从任一个路口开始游览，在任一个路口结束游览。请你写一个程序，帮助阿龙找一条最佳的游览线路，使得这条线路的所有分值总和最大。
输入数据：
输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街（1≦M≦100），N表示有多少条林阴道（1≦M≦20001）。接下来的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。
输出数据：
输出文件是OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳游览线路的总分值。
输入输出示例：
INPUT.TXT OUTPUT.TXT
3 6-50 –47 36 –30 –2317 –19 –34 –13 –8-42 –3 –43 34 –45 84
分析：
设Lij为第I条旅游街上自西向东第J段的分值（1 ≦ I ≦ M，1 ≦ J ≦ N – 1）。例如样例中L12=17，L23=-34，L34=34。
我们将网格状的旅游区街道以林荫道为界分为N – 1个段，每一段由M条旅游街的对应段成，即第J段成为{L1J，L2J，……，LMJ}（1≦ J ≦ N – 1）。由于游览方向规定横向自西向东，纵向即可沿林阴道由南向北，亦可由北向南，而横行的街段有分值，纵行无分值，因此最佳游览路现必须具备如下三个特征：
来自若干个连续的段，每一个段中取一个分值；
每一个分值是所在段中最大的；
起点段和终点段任意，但途经段的分值和最大。
设Li为第I个段中的分值最大的段。即Li=Max{L1I，L2I，……，LMI}（1≦I≦N – 1）。例如对于样例数据：
L1=Max（-50，17，-42）=17；
L2=Max（-47，-19，-3）=-3；
L3=Max（36，-34，-43）=36；
L4=Max（-30，-13，34）=34；
L5=Max（-23，-8，-45）=-8；
有了以上的基础，我们便可以通过图示描述解题过程，见图12。
我们把将段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条游览路线。显然，如果确定西端为起点、东段为终点，则这条游览路线的总分值最大。
问题是某些段的最大分值可能是负值，而最优游览路线的起点和终点任意，在这种情况下，上述游览路线就不一定最佳了。因此，我们只能枚举这条游览路线的所有可能的子路线，从中找出一条子路线II+1……J（1 ≦ I
Sum为当前游览路线的总分值。
我们可以得到如下算法：
Best := 0; Sum := 0;
for I := 1 to N – 2 do
for J := I + 1 to N – 1 do begin
Sum := LI + …… + LJ;
if Sum > Best then
Best := Sum;
end
显然，这个算法的时间复杂度为O（N2）。而N在1~20001之间，时间复杂度比较高。于是，我们必须对这个算法进行优化。
仍然从顶点1开始枚举最优路线。若当前子路线延伸至顶点I时发现总分值Sum≦0，则应放弃当前子路线。因为无论LI+1为何值，当前子路线延伸至顶点I+1后的总分值不会大于LI+1。因此应该从顶点I+1开始重新考虑新的一条子路线。通过这种优化，可以使得算法的时间复杂度降到了O（N）。
优化后的算法描述如下:
Best := 0; Sum := 0;
for I := 1 to N – 1 do begin
Sum := Sum + LI;
if Sum > Best then
Best := Sum;
if Sum < 0 then
Sum := 0;
end
程序描述如下：
{$R-,S-,Q-}
{$M 65520,0,655360}
program Noi94;
const
MaxN = 20001; {林阴道数的上限}
Inp = 'input.txt';
Outp = 'output.txt';
var
M, N: Word; {旅游街数和林阴道数}
Best: Longint; {最佳游览路线的总分值}
Score: array [1..MaxN] of ShortInt; {描述每个段的最大分值}
procedure Init;
var
I, J, K: Integer;
Buffer: array [1 .. 40960] of Char; {文件缓冲区}
begin
Assign(Input, Inp);
Reset(Input);
SetTextBuf(Input, Buffer); {开辟文件缓冲区}
Readln(M, N); {读入旅游街数和林阴道数}
FillChar(Score,Sizeof(Score),$80); {初始化各段的最大分值}
for I := 1 to M do {计算1~N –1段的最大分值 }
for J := 1 to N - 1 do begin
Read(K);
if K > Score[J] then Score[J] := K;
end;
Close(Input);
end;
procedure Out;
begin
Assign(Output, Outp);
Rewrite(Output);
Writeln(Best);
Close(Output);
end;
procedure Main;
var
I: Integer;
Sum: Longint; {当前游览路线的总分值}
begin
{最佳游览路线的总分值和当前游览路线的总分值初始化}
Best := 0;
Sum := 0;
for I := 1 to N - 1 do begin {顺序枚举游览路线的总分值}
Inc(Sum, Score[I]); {统计当前游览路线的总分值}
if Sum > Best then Best := Sum; {若当前最佳，则记下}
if Sum < 0 then Sum := 0; {若总分值<0，则考虑一条新路线}
end;
end;
begin
Init; {输入数据}
Main; {主过程}
Out; {输出}
end.
第五课 递归与回溯法
课题：递归与回溯
目标：
知识目标：递归概念与利用递归进行回溯
能力目标：回溯算法的应用
重点：回溯算法
难点：回溯算法的理解
板书示意：
递归的理解
利用递归回溯解决实际问题（例14、例15、例16、例17、例18）
利用回溯算法解决排列问题（例19）
授课过程：
什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。
例如，我们可以这样定义N!，N!=N*(N-1)!，因此求N!转化为求 (N-1)!。这就是一个递归的描述。
因此，可以编写如下递归程序：
program Factorial;
var
N: Integer;
T: Longint;
function Fac(N: Integer): Longint;
begin
if N = 0 then Fac := 1 else Fac := N * Fac(N - 1)
end;
begin
Write('N = '); Readln(N);
T := Fac(N);
Writeln('N! = ',T);
end.
图13展示了N=3的执行过程。由上述程序可以看出，递归是一个反复执行直到递归终止的过程。
设一个未知函数f，用其自身构成的已知函数g来定义：
为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2) ，…，上述这种用自身的简单情况来定义自己的方式称为递归定义。
递归有如下特点：
①它直接或间接的调用了自己。
②一定要有递归终止的条件，这个条件通常称为边界条件。
与递推一样，每一个递推都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递归边界值f(0)=a。然后返回调用函数。返回的过程中，中间结果相继出栈恢复，f(1)=g(1,a)f(2)=g(2,f(1))……直至求出f(n)=g(n,f(n-1))。
由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。
递归算法适用的一般场合为：
① 数据的定义形式按递归定义。
如裴波那契数列的定义：
对应的递归程序为
function fib(n: Integer): Integer;
begin
if n = 0 then
fib := 1 {递归边界}
else if n = 1 then
fib := 2 {递归边界}
else
fib := fib(n – 2) + fib(n – 1); {递归}
end;
这类递归问题可转化为递推算法，递归边界为递推的边界条件。例如上例转化为递推算法即为
function fib(n: Integer): Integer;
begin
f[0] := 1; f[1] := 2; {递推边界}
for I := 2 to n do
f[I] := f[I – 1] + f[I – 2];
fib := f(n);
end;
② 数据之间的关系（即数据结构）按递归定义。如树的遍历，图的搜索等。
③ 问题解法按递归算法实现。例如回溯法等。
对于②和③，可以用堆栈结构将其转换为非递归算法，以提高算法的效率以及减少内存空间的浪费。
下面以经典的N皇后问题为例，看看递归法是怎样实现的，以及比较递归算法和非递归算法效率上的差别。
例15：N皇后问题
在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。
分析：
由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。
下面是放置第I个皇后的的递归算法：
Procedure Try(I:integer)；
{搜索第I行皇后的位置}
var
j:integer;
begin
if I=n+1 then 输出方案；
for j:=1 to n do
if 皇后能放在第I行第J列的位置 then begin
放置第I个皇后；
对放置皇后的位置进行标记；
Try（I+1）
对放置皇后的位置释放标记；
End;
End;
N皇后问题的递归算法的程序如下：
program N_Queens;
const
MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数}
procedure Out; {输出方案}
var
I: Integer;
begin
Inc(Total); Write(Total: 3, ‘:’);
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
procedure Try(I: Integer);
{搜索第I个皇后的可行位置}
var
J: Integer;
begin
if I = N + 1 then Out; {N个皇后都放置完毕，则输出解}
for J := 1 to N do
if A[J] and B[J + I] and C[J – I] then begin
X[I] := J;
A[J] := False;
B[J + I] := False;
C[J – I] := False;
Try(I + 1); {搜索下一皇后的位置}
A[J] := True;
B[J + I] := True;
C[J – I] := True;
end;
end;
begin
Write(‘Queens Numbers = ‘);
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, Sizeof(C), True);
Try(1);
Writeln(‘Total = ‘, Total);
end.
N皇后问题的非递归算法的程序：
program N_Queens;
const MaxN = 100; {最多皇后数}
var
A:array [1..MaxN] of Boolean; {竖线被控制标记}
B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记}
C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜线被控制标记}
X: array [1 .. MaxN] of Integer; {记录皇后的解}
Total: Longint; {解的总数}
N: Integer; {皇后个数
procedure Out; {输出方案}
var
I: Integer;
begin
Inc(Total);
Write(Total: 3, ‘:’);
for I := 1 to N do Write(X[I]: 3);
Writeln;
end;
procedure Main;
var
K: Integer;
begin
X[1] := 0; K := 1;
while K > 0 do begin
if X[K] <> 0 then begin
A[X[K]] := True;
B[X[K] + K] := True;
C[X[K] – K] := True;
end;
Inc(X[K]);
while(X[K]<=N)and not(A[X[K]]and B[X[K]+K]and C[X[K]–K])do
Inc(X[K]); {寻找一个可以放置的位置}
if X[K] <= N then
if K = N then Out
else begin
A[X[K]] := False;
B[X[K] + K] := False;
C[X[K] – K] := False;
Inc(K);
X[K] := 0; {继续放置下一个皇后}
end
else Dec(K); {回溯}
end;
end;
begin
Write(‘Queens Number = ‘);
Readln(N);
FillChar(A, Sizeof(A), True);
FillChar(B, Sizeof(B), True);
FillChar(C, SizeofI, True);
Main;
Writeln(‘Total = ‘, Total);
end.
使用递归可以使蕴含复杂关系的问题，结构变得简洁精炼。看看下面的例题。
例16:新汉诺（hanoi）塔问题
设有n各大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称之为初始状态。问题要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。移动时有如下要求：
一次只移动一个盘；
不允许把大盘移到小盘上边；
输入：输入文件第1行是状态中圆盘总数；第2~4行是分别是初始状态中A、B、C柱上的圆盘个数和从上到下每个圆盘的编号；第5~7行是分别是目标状态A、B、C柱上的圆盘个数和从上到下每个圆盘的编号。
输出：每行写一步的移动方案，格式为：
Move I圆盘 form P柱 to Q柱。
最后输出最少步数。
输入样例（如图）：
6
3 1 2 3
2 4 5
1 6
0
6 1 2 3 4 5 6
0
样例所描述的状态如图15所示。
=
输出样例：
分析：
要从初始状态移动到目标状态，就是把每个圆盘分别移动到自己的目标状态。而问题的关键一步就是：首先考虑把编号最大的圆盘移动到自己的目标状态，而不是最小的，因为编号最大的圆盘移到目标位置之后就可以不再移动了，而在编号最大的圆盘未移到目标位置之前，编号小的圆盘可能还要移动，编号最大的圆盘一旦固定，对以后的移动将不会造成影响。
根据上面的分析可设计如下过程
Move(K, W);
表示把编号K的圆盘从当前所在柱移动到W柱的过程。
下面对样例进行分析。
将6号盘移动到B柱，在此之前一定将经历如图16所示的状态
要移动6号盘首先要把1~5号盘全部移开，也就是说，既不能移动到6号盘的初始立柱上，也不能移动到6号盘的目标立柱上。显然这里要将它们移动到A柱。然后再将6号盘移到位。此时状态如图17所示。
同时我们注意到：把1~5盘移动到目标的过程和将6号盘移动到B柱的过程，从形式上是一样的，只是盘的编号不同而已。显然这是个递归过程，可以采用递归法实现。
算法设计如下:
procedure Move(K, W)；
{编号K的圆盘从当前所在柱移动到W柱}
begin
if K号盘已经在W立柱上 then Exit； {递归边界}
for I := K - 1 downto 1 do
Move(I, 过渡立柱); {将编号小于K的盘都移到过渡立柱上去}
输出当前移动方案;
将K号盘移到W立柱上;
Inc(Step); {累计步数}
end;
程序设计如下：
program New_Hanoi;
const
Inp = ‘hanoi.in’;
Outp = ‘hanoi.out’;
MaxN = 64; {最大圆盘数}
Stake: array [1 .. 3] of Char =(‘A’, ‘B’, ‘C’);
type
Tnode = array [1 .. MaxN] of Byte; {记录圆盘所处的立柱编号}
var
N: Integer; {圆盘数}
Now, {当前状态}
Goal: Tnode; {目标状态}
Step: Longint; {步数}
procedure Init; {读入数据}
var
I, J, L, X: Integer;
begin
Assign(Input, Inp);
Reset(Input);
Readln(N); {读入圆盘数}
for I := 1 to 3 do begin {读入初始状态}
Read(L);
for J := 1 to L do begin
Read(X); Now[X] := I;
end;
Readln;
end;
for I := 1 to 3 do begin {读入目标状态}
Read(L);
for J := 1 to L do begin
Read(X); Goal[X] := I;
end;
Readln;
end;
Close(Input);
end;
procedure Main;
var
I: Integer;
procedure Move(K: Integer; W: Byte);
var
I, J: Word;
begin
if Now[K] = W then Exit; {若达到目标，则退出}
J := 6 – Now[K] – W; {计算过渡立柱编号}
for I := K – 1 downto 1 do {将圆盘移动到过渡立柱}
Move(I, J);
Write(‘Move‘,K,‘ From ‘,Stake[Now[K]],‘ to ‘,Stake[W]);
Writeln(‘.’);
Now[K] := W; {将K号盘移动到目标位置}
Inc(Step); {累计步数}
end;
begin
Assign(Output, Outp);
Rewrite(Output);
for I := N downto 1 do {从大到小对每一个圆盘进行处理}
Move(I, Goal[I]);
Writeln(Step); {输出总步数}
Close(Output);
end;
Begin
Init;
Main;
End.
例17背包问题：
已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大
分析：本题可以用递归求解：设当前有N个物品，容量为M；因为这些物品要么选，要么不选，我们假设选的第一个物品编号为I（1~I-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可。
另外，为了优化程序，我们定义一个函数如下：
F[I]表示选第I~N个物品能得到的总效益。不难推出：
F[N]=Pn
F[I]=F[I+1]+Pi （I=1…N-1）
假设当前已选到第I号物品，如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小，则没有必要继续搜索下去。
参考程序：
Program exam17;
Var W,P :Array [1..50] Of Integer;
F :Array [1..50] Of Integer;
Ou,Out :Array [1..50] Of Boolean;
{Ou，Out数组记录选择物品的具体方案}
M :Integer;
N,U :Byte;
Ans,Now :Integer; {Ans记录最优解，Now记录当前效益值}
Procedure Init; {初始化}
Var I :Byte;
Begin
Fillchar(Out,Sizeof(Out),False);
Ou:=Out;
Assign(Input,'Input.txt');
Reset(Input);
Readln(M,N);
For I:=1 To N Do
Readln(W[I],P[I]);
Close(Input); {读入数据}
F[N+1]:=0;
For I:=N Downto 1 Do
F[I]:=F[I+1]+P[I]; {计算函数F的值}
Ans:=0;
Now:=0;
End;
Procedure Search(I:Integer; J:Byte); {递归求解}
Var K :Byte;
Begin
If Now+F[J]<=Ans Then Exit; {如果没有必要搜索下去，则返回到上一级}
If Now>Ans Then Begin {修改最优解}
Ans:=Now;
Out:=Ou;
End;
For K:=J To N Do {选取物品}
If W[K]<=I Then Begin
Now:=Now+P[K];
Ou[K]:=True;
Search(I-W[K],K+1);
Now:=Now-P[K];
Ou[K]:=False;
End;
End;
Begin
Init;
Search(M,1);
Assign(Output,'Output.txt'); {输出}
Rewrite(Output);
Writeln(Ans);
For U:=1 To N Do
If Out[U] Then Write(U,' ');
Writeln;
Close(Output);
End.
例18寻找国都名
给出一个矩阵及一些国都名：
o k d u b l i n dublin
a l p g o c e v tokyo
r a s m u s m b london
o s l o n d o n rome
y i b l g l r c bonn
k r z u r i c h paris
o a i b x m u z oslo
t p q g l a m v lima
要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。
输入：在文本文件input.txt中的第一行有一个整数M和N，表示该字符矩阵的长和宽。接下来就是M*N的字符矩阵。字符矩阵后有一个整数K，表示国家都名的个数，接下来的K行，每一行都是一个国都名。
输出：在文本文件output.txt中共有K行，第I行写入第I个国都名的起始位置及方向。起始位置用坐标表示，方向定义见图18。如没有找到国都名，输出‘No found’。
分析：将字符矩阵读入到二维数组，然后对每一个国都名进行搜索，首先需要在矩阵中找到国都名的第一个字符，然后沿八个方向进行搜索。直到找到国都名为止。若在矩阵中没有找到，则输出相应的信息。
在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了。
参考程序如下：
program exam18;
Const
Fx : Array[1..8,1..2] Of Shortint {定义八个方向}
=((0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1));
max = 100; {最大字符矩阵}
Finp = 'Input.Txt'; {输入文件名}
Fout = 'Output.Txt'; {输出文件名}
Var
A :Array[0..max+1,0..max+1] of Char;
{为了节约边界条件的判断，故增加边界范围}
B :Array[1..max,1..max] Of Boolean;
{标志数组，标志已经搜索过的路径}
S,
W :String;
N,M,I,J,K :Integer;
printed :Boolean;
Procedure Init;
Var
I,J :Integer;
Begin
Assign(Input,Finp); Reset(Input);
{采用重定向的手段，将输入文件与标准输入联系起来，
这样对标准输入（键盘）的操作，相当对输入文件的操作}
Assign(Output,Fout);Rewrite(Output);
{采用重定向的手段，将输出文件与标准输出联系起来，
这样对标准输出（屏幕）的操作，相当对输出文件的操作}
Readln(M,N);
For I:=1 To M Do Begin
For J:=1 To N Do Read(A[I,J]);
Readln;
End;
End;
Procedure Out;
Begin
write('(',J,',',k,')'); {输出起始位置的坐标}
Writeln('':5,W); {输出路径}
printed:=True {置已经打印的标志}
End;
Procedure Work(T,X,Y:Integer);
{搜索路径，T为国都名的字符位置，X，Y为当前搜索的坐标}
Var I : Integer;
Begin
If T=Length(S)+1 Then begin {搜索完，打印输出}
Out;
exit
end;
For I:=1 To 8 Do {八个方向进行搜索}
Begin
X:=X+Fx[I,1]; Y:=Y+Fx[I,2]; {坐标变化}
If (A[X,Y]=S[T])And(B[X,Y]) Then
Begin
W:=W+Chr(I+48); {记录路径}
B[X,Y]:=False; {设置已经搜索}
Work(T+1,X,Y); {继续搜索下一个}
Delete(W,Length(W),1);{恢复原路径}
B[X,Y]:=True; {恢复标志}
End;
X:=X-Fx[I,1]; Y:=Y-Fx[I,2]; {返回后，坐标恢复}
End;
End;
Begin
Init;
Readln(N);
For I:=1 To N Do {对所有的国都名进行处理}
Begin
Readln(S); {读入第I个国都名}
printed:=False;
Fillchar(B,Sizeof(B),True);{未搜索之前清标志数组}
For J:=1 To N Do begin {对字符矩阵进行搜索}
For K:=1 To N Do Begin
If printed Then Break; {已经打印了，跳出内循环}
If A[J,K]=S[1] Then Work(2,J,K);{从第一个字符开始搜}
End;
If printed Then Break; {已经打印了，跳出外循环}
end;
If Not printed Then Writeln('No found');
End;
Close(Input);
Close(Output);
End.
例19采用递归方法，求N个元素中取出M个的排列，。
（1）每个元素只能取一次。
（2）每个元素可以取任意多次（即可重复的排列）。
分析：此题用简单的递归搜索。设x[I]排列中的第I个元素，依次搜索每一个x[I]即可
program exam19;
const finp ='input.txt';
fout ='output.txt';
maxn =10;
var n,m :integer;
x :array[1..maxn]of integer; { x数组记录当前排列}
used:array[1..maxn]of boolean; {used[I]=True时表明第I个元素在当前排列中，反之亦然}
procedure init; {初始化输入}
var i :integer;
begin
write(‘input n, m:’); readln(n,m);
fillchar(used,sizeof(used),false)
end;
procedure pailie(i:integer); {搜索}
var j :integer;
begin
if i>m then begin
for j:=1 to m do write(x[j]:5);writeln; {输出一组解}
end else
for j:=1 to n do
if not used[j] then begin
used[j]:=true; {修改used[I]}
x[i]:=j; {记录x[i]}
pailie(i+1); {继续搜索排列的下一个}
used[j]:=false {还原used[I]}
end
end;
Begin
init;
pailie(1);
End.
（2）只需要将pailie过程中used标志数组 去掉即可，这样，已经取过的数据可以继续取。
修改如下：
procedure pailie(i:integer); {搜索x[I]}
var j :integer;
begin
if i>m then begin
for j:=1 to m do write(x[j]:5);writeln;{找到一组解，输出}
end else
for j:=1 to n do begin {枚举x[I]}
x[i]:=j; {记录x[I]}
pailie(i+1) {继续搜索x[I+1]}
end
end;
第六课 递推法
课题：递推法
目标：
知识目标：递推概念与利用递推解决实际问题
能力目标：递推方程
重点：递推方程
难点：递推方程写出
板书示意：
递推的理解（例20）
倒推法（例21）
顺推法（例22、例23）
授课过程：
递推就是逐步推导的过程。我们先看一个简单的问题。
例20：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。
分析：我们可以根据裴波那契数列的定义：从第2项开始，逐项推算，直到第N项。因此可以设计出如下算法：
F[0] := 1; F[1] := 2;
FOR I := 2 TO N DO
F[I] := F[I – 1] + F[I – 2];
从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。
对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。
递推分倒推法和顺推法两种形式。算法流程如下：
一、倒推法
所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标，根据递推关系，采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法。因为这类问题的运算过程是一一映射的，故可分析其递推公式。看看下面的例题。
例21：贮油点
一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？
编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：
No. Distance(k.m.) Oil(litre)
1 × × × ×
2 × × × ×
… … … … …
分析：
设Way[I]——第I个贮油点到终点（I=0）的距离；
oil[I]——第I个贮油点的贮油量；
我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。图19表示倒推时的返回点。
从贮油点I向贮油点I+1倒推的方法是：卡车在贮油点I和贮油点I+1间往返若干次。卡车每次返回I+1点时应该正好耗尽500公升汽油，而每次从I+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下，使I点贮足I*500公升汽油的要求（0≦I≦n-1）。具体来说，第一个贮油点I=1应距终点I=0处500km，且在该点贮藏500公升汽油，这样才能保证卡车能由I=1处到达终点I=0处，这就是说
Way[I]=500；oil[I]=500；
为了在I=1处贮藏500公升汽油，卡车至少从I=2处开两趟满载油的车至I=1处，所以I=2处至少贮有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上从I=1返回至I=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即d12=500/3km，Way[2]=Way[1]+d12=Way[I]+500/3
此时的状况如图20所示。
为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3处的二趟返程空车，合计5次。路途耗油亦应500公升，即d23=500/5，
Way[3]=Way[2]+d23=Way[2]+500/5；
此时的状况如图21所示。
依次类推，为了在I=k处贮藏k*500公升汽油，卡车至少从I=k+1处开k趟满载车至I=k处，即oil[k+1]=(k+1)*500=oil[k]+500，加上从I=k返回I=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即dk,k+1=500/(2k-1)，
Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)；
此时的状况如图22所示。
最后，I=n至始点的距离为1000-Way[n],oil[n]=500*n。为了在I=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至I=n，加上从I=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为（1000-Way[n]）*(2n+1)，即始点藏油为oil[n]+(1000-Way[n])*(2n+1)。
程序设计如下：
program Oil_lib;
var
K: Integer; {贮油点位置序号}
D, {累计终点至当前贮油点的距离}
D1: Real; {I=n至终点的距离}
Oil, Way: array [1 .. 10] of Real;
i: Integer;
begin
Writeln(‘No.’, ‘Distance’:30, ‘Oil’:80);
K := 1;
D := 500; {从I=1处开始向终点倒推}
Way[1] := 500;
Oil[1] := 500;
repeat
K := K + 1;
D := D + 500 / (2 * K – 1);
Way[K] := D;
Oil[K] := Oil[K – 1] + 500;
until D >= 1000;
Way[K] := 1000; {置始点到终点的距离值}
D1 := 1000 – Way[K – 1]; {求I=n处至至点的距离}
Oil[K] := D1 * (2 * k + 1) + Oil[K – 1]; {求始点贮油量}
{由始点开始，逐一打印至当前贮油点的距离和贮油量}
for i := 0 to K do
Writeln(i, 1000 – Way[K – i]:30, Oil[K – i]:80);
end.
二、顺推法
顺推法是从边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值……，依次类推，直至从问题初始陈述向前推进到这个问题的解为止。
看看下面的问题。
例22昆虫繁殖
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？x>=1,y>=1,z>=x
输入：x,y,z的数值
输出：成虫对数
事例：
输入：x=1 y=2 z=8
输出：37
分析：首先我们来看样例：每隔1个月产2对卵，求过8月（即第8+1=9月）的成虫个数
月份 1 2 3 4 5 6 7 8 9 …
新增卵 0 2 2 2 6 10 14 26 46 …
成虫 1 1 1 3 5 7 13 23 37 …
设数组A[i]表示第I月新增的成虫个数。
由于新成虫每过x个月产y对卵，则可对每个A[I]作如下操作:
A[i+k*x+2]:=A[i+k*x+2]+A[i]*y （1<=k, I+k*x+2<=z+1）
因为A [i]的求得只与A[1]~A[i-1]有关，即可用递推求法。
则总共的成虫个数为：
程序如下：
program exam22;
var x,y,z,i :integer;
ans :longint;
a :array[1..60]of longint;
procedure add(i:integer);
var j :integer;
begin
j:=i+2+x; {新生成虫要过x 个月才开始产卵，即第I+2+x个月才出现第一群新成虫}
repeat
a[j]:=a[j]+a[i]*y; {递推}
j:=j+x
until j>z+1
end;
begin
readln(x,y,z);
a[1]:=1; {初始化}
for i:=1 to z do add(i); {对每个A[I]进行递推}
ans:=0;
for i:=1 to z+1 do ans:=ans+a[i]; {累加总和}
writeln(ans);
end.
例23：实数数列（NOI94第3题）
一个实数数列共有N项，已知
ai=(ai-1-ai+1)/2+d，(1
输入数据均不需判错。
分析：
根据公式ai=(ai-1-ai+1)/2+d 变形得，ai+1=ai-1-2ai+2d，因此该数列的通项公式为：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，这样就可以根据公式递推求出am
∵ ai=ai-2-2ai-1+2d ……①
=ai-2-2（ai-3-2ai-2+2d）+2d
=-2ai-3+5（ai-4-2ai-3+2d）-2d
=5ai-4-12ai-3+8d
……
一直迭代下去，直到最后，可以建立ai和a1与a2的关系式。
设ai=Pia2+Qid+Ria1，我们来寻求Pi,Qi,Ri的变化规律。
∵ ai=ai-2-2ai-1+2d
∴ ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d
=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1
∴ Pi=Pi-2-2Pi-1 ……②
Qi=Qi-2-2Qi-1+2 ……③
Ri=Ri-2-2Ri-1 ……④
显然，P1=0 Q1=0 R1=1 （i=1）
P2=1 Q2=0 R2=0 （i=2）
将初值P1、Q1、R1和P2、Q2、R2代入②③④可以求出Pn、Qn、Rn
∵ an=Pna2+Qnd+Rna1
∴ a2=(an-Qnd+Rna1)/Pn
然后根据公式①递推求出am，问题解决。
但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过30时，求出的am就明显偏离正确值。显然，这种算法虽简单但不可靠。
为了减少误差，我们可设计如下算法：
∵ ai=Pia2+Qid+Ria1
=Pi-1a3+Qi-1d+Ri-1a2
=Pi-2a4+Qi-2d+Ri-2a3
……
=Pi-2+kak+Qi-2+kd+Ri-2+kak-1
∴ an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1
ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 ……⑤
根据公式⑤，可以顺推a2、a3、…、aM。虽然仍然存在实数误差，但由于Pn-k+2递减，因此最后得出的am要比直接利用公式①精确得多。
程序如下：
program NOI94_3;
const
MaxN = 60;
var
N, M, i: Integer;
D: Real;
A: array [1 .. MaxN] of Real;
F: array [1 .. MaxN, 1 .. 3] of Real;
{F[i,1]：对应Pi；F[i,2]：对应Qi；F[i,3]：对应Ri}
procedure Init;
begin
Write(‘N, M, D =’);
Readln(N, M, D); {输入项数、输出项序号和常数}
Write(‘A1, A’, N, ‘ =’);
Readln(A[1], A[N]); {输入a1和an}
end;
procedure Solve;
{根据公式PiPi-2-2*Pi-1,QiQi-2-2*Qi-1,RiRi-2-2*Ri-1求Pi、Qi、Ri }
begin
F[1, 1] := 0; F[1, 2] := 0; F[1, 3]:= 1;
F[2, 1] := 1; F[2, 2] := 0; F[2, 3] := 0;
for i := 3 to N do
begin
F[i, 1] := F[i – 2, 1] – 2 * F[i – 1, 1];
F[i, 2] := F[i – 2, 2] – 2 * F[i – 1, 2] + 2;
F[i, 3] := F[i – 2, 3] – 2 * F[i – 1, 3];
end;
end;
procedure Main;
begin
Solve;
{递推A2…Am}
for i := 2 to M do
A[i]:=(A[N]–F[N–i+2,2]*D–F[N–i+2,3]*A[i–1])/F[N–i+2,1];
Writeln(‘a’, m, ‘ =’, A[M]:20 :10);
end;
begin
Init;
Main;
end.
第七课 贪心法
课题：贪心法
目标：
知识目标：贪心的原理递与贪心的实现
能力目标：贪心的原理
重点：贪心算法的应用
难点：贪心的理解
板书示意：
贪心的引入（例24）
贪心的应用（例25、例26、例27、例28）
授课过程：
若在求解一个问题时，能根据每次所得到的局部最优解，推导出全局最优或最优目标。那么，我们可以根据这个策略，每次得到局部最优解答，逐步而推导出问题，这种策略称为贪心法。
下面我们看一些简单例题。
例24：在N行M列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共N个数的和最大。
分析：要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。因此，我们设计出如下算法:
读入N, M,矩阵数据；
Total := 0;
For I := 1 to N do begin {对N行进行选择}
选择第I行最大的数,记为K；
Total := Total + K；
End；
输出最大总和Total；
从上例中我们可以看出，和递推法相仿，贪心法也是从问题的某一个初始解出发，向给定的目标递推。但不同的是，推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择，即贪心选择（在例中，这种贪心选择表现为选择一行中的最大整数），这样，不断的将问题归纳为若干相似的子问题，最终产生出一个全局最优解。
特别注意的是是，局部贪心的选择是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略，应从理论上予以证明。下面我们看看另一个问题。
例25：部分背包问题
给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。
分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。
因此我们非常容易设计出如下算法：
问题初始化； {读入数据}
按Vi从大到小将商品排序；
I := 1;
repeat
if M = 0 then Break; {如果卡车满载则跳出循环}
M := M - Wi;
if M >= 0 then 将第I种商品全部装入卡车
else
将(M + Wi)重量的物品I装入卡车;
I := I + 1; {选择下一种商品}
until (M <= 0) OR (I >= N)
在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。
Program Exam25;
Const Finp='Input.Txt';
Fout='Output.Txt';
Var N,M :Longint;
S :Real;
P,W :Array[1..100] Of Integer;
Procedure Init; {输出}
Var I :Integer;
Begin
Assign(Input,Finp); Reset(Input);
Readln(M,N);
For I:=1 To N Do Readln(W[I],P[I]);
Close(Input);
End;
Procedure Sort(L,R:Integer); {按收益值从大到小排序}
Var I,J,Y :Integer;
X :Real;
Begin
I:=L; J:=R;
X:=P[(L+R) Div 2]/W[(L+R) Div 2];
Repeat
While (I
While (P[J]/W[J]<=X)And(J>L) Do Dec(J);
If I<=J Then
Begin
Y:=P[I]; P[I]:=P[J]; P[J]:=Y;
Y:=W[I]; W[I]:=W[J]; W[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If I
Procedure Work;
Var I :Integer;
Begin
Sort(1,N);
For I:=1 To N Do
If M>=W[I] Then {如果全部可取，则全取}
Begin
S:=S+P[I]; M:=M-W[I];
End
Else {否则取一部分}
Begin
S:=S+M*(P[I]/W[I]); Break;
End;
End;
Procedure Out; {输出}
Begin
Assign(Output,Fout); Rewrite(Output);
Writeln(S:0:0);
Close(Output);
End;
Begin {主程序}
Init;
Work;
Out;
End.
因此，利用贪心策略解题，需要解决两个问题：
首先，确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：
可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。
其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。
下面来看看0-1背包问题。
给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。
分析：对于N种动物，要么被装，要么不装，也就是说在满足卡车载重的条件下，如何选择动物，使得动物价值最大的问题。
即确定一组X1，X2，…，Xn， Xi∈{0,1}
f(x)=max(∑Xi*Vi) 其中，∑(Xi*Wi)≦W
从直观上来看，我们可以按照上例一样选择那些价值大，而重量轻的动物。也就是可以按价值质量比（Vi/Wi）的大小来进行选择。可以看出，每做一次选择，都是从剩下的动物中选择那些Vi/Wi最大的，这种局部最优的选择是否能满足全局最优呢？我们来看看一个简单的例子：
设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。
情况A：按照上述思路，三种动物的Vi/Wi分别为2,2,2.14。显然，我们首先选择动物C，得到价值150，然后任意选择A或B，由于卡车最大载重为100，因此卡车不能装载其他动物。
情况B：不按上述约束条件，直接选择A和B。可以得到价值80+100=180，卡车装载的重量为40+50=90。没有超过卡车的实际载重，因此也是一种可行解，显然，这种解比上一种解要优化。
问题出现在什么地方呢？我们看看图2-18
从图23中明显可以看出，情况A，卡车的空载率比情况B高。也就是说，上面的分析，只考虑了货物的价值质量比，而没有考虑到卡车的运营效率，因此，局部的最优化，不能导致全局的最优化。
因此，贪心不能简单进行，而需要全面的考虑，最后得到证明。
例26排队打水问题
有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？
分析：由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：
将输入的时间按从小到大排序；
将排序后的时间按顺序依次放入每个水龙头的队列中；
统计，输出答案。
参考程序：
Program Exam26;
Const Finp='Input.Txt';
Fout='Output.Txt';
Var A :Array[1..100] Of Integer;
S :Array[1..100] Of Longint;
N,M :Integer;
Min :Longint;
Procedure Init; {读入数据}
Var I :Integer;
Begin
Assign(Input,Finp); Reset(Input);
Readln(N,M);
For I:=1 To N Do Read(A[I]);
Close(Input);
End;
Procedure Sort(L,R:Integer); {将时间从小到大排序}
Var I,J,X,Y :Integer;
Begin
I:=L; J:=R; X:=A[(L+R) Div 2];
Repeat
While (A[I]<=X)And(I
If I<=J Then
Begin
Y:=A[I]; A[I]:=A[J]; A[J]:=Y;
Inc(I); Dec(J);
End;
Until I>J;
If L
End;
Procedure Work;
Var I,J,K :Integer;
Begin
Fillchar(S,Sizeof(S),0);
J:=0; Min:=0;
For I:=1 To N Do {用贪心法求解}
Begin
Inc(J);
If J=M+1 Then J:=1;
S[J]:=S[J]+A[I];
Min:=Min+S[J];
End;
Assign(Output,Fout); Rewrite(Output); {输出解答}
Writeln(Min);
Close(Output);
End;
Begin {主程序}
Init;
Sort(1,N);
Work;
End.
例27：旅行家的预算（NOI99分区联赛第3题）
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……，N）。
计算结果四舍五入至小数点后两位。
如果无法到达目的地，则输出“No Solution”。
样例：
Input
D1=275.6 C=11.9 D2=27.4 P=2.8 N=2
油站号I 离出发点的距离Di 每升汽油价格Pi
1 102.0 2.9
2 220.0 2.2
Output
26.95（该数据表示最小费用）
分析：需要考虑如下问题：
出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？
汽车行程到第几站开始加油，加多少油？
可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：
对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。
对于第一种情况，则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况，则需将油箱加满。
贪心算法证明如下：
设定如下变量：
Value[i]：第i个加油站的油价；
Over[i]：在第i站时的剩油；
Way[i]：起点到油站i的距离；
X[I]：X记录问题的最优解，X[I]记录油站I的实际加油量。
首先，X[1]≠0，Over[1]=0。
假设第I站加的X[I]一直开到第K站。则有，X[I]..x[k-1]都为0，而X[K]≠0。
若Value[I]>Value[k]，则按贪心方案，第I站应加油为
T=（Way[k]-Way[I]）/M-Over[I]。
若T
若T
I := 1 {汽车出发设定为第1个加油站}
L := C*D2； {油箱装满油能行驶的距离}
repeat
在L距离以内，向后找第一个油价比I站便宜的加油站J；
if J存在 then
if I站剩余油能到达J then
计算到达J站的剩油
else
在I站购买油，使汽车恰好能到达J站
else
在I站加满油；
I := J； {汽车到达J站}
until 汽车到达终点；
程序如下：
program NOI99L_3;
const
Inp = ‘input.txt’;
Outp = ‘output.txt’;
MaxN = 10001; {最大油站数}
Zero = 1e-16; {误差值}
type
Rectype = record {油站的数据结构}
Value: Real; {油价}
Way: Real; {距起点的距离}
Over: Real; {汽车到达该站时的剩油}
end;
RecPtr = ︿Rectype; {油站指针}
var
Oil: array [1 .. MaxN] of RecPtr; {记录所有油站}
D1, {起点到终点之间的距离}
C, {汽车油箱的容量}
D2, {每升汽油能行驶的距离}
N: Integer; {油站数}
Cost: Real; {最小油费}
MaxWay, {满油时汽车最大的行驶距离}
function init: Boolean; {初始化，并判无解}
var
I: Integer;
begin
Read (D1, C, D2);
New(Oil[1]); {处理初始值和起始油站}
Oil[1]︿.Way := 0;
Read(Oil[1]︿.Value,n);
MaxWay := D2 * C;
for I := 2 to n do begin {读入后N-1个油站信息}
New(Oil[I]);
Readln(Oil[I]︿.Way, Oil[I]︿.Value);
Oil[I]︿.over:=0;
end;
Inc(n); {将终点也看成一个加油站}
New(Oil[n]);
Oil[n]︿.Way := D1;
Oil[n]︿.Value := 0;
Oil[n]︿.over:=0;
for I := 2 to n+1 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);;
{在I加油站购买Miles/D2加仑汽油}
begin
Cost:= Cost + Miles / D2 * Oil[I]︿.Value;
{将买汽油所需的费用加到Cost变量中}
end;
procedure Solve;
var
I, J: Integer;
S: Real;
begin
I := 1; {汽车在起点}
repeat
S := 0.0;
{在MaxWay范围以内，找第一个油价比I站便宜的加油站J}
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 {如果找到J站或可以直达终点}
{如果剩油足够到达J站，则无需购油，并计算到达J站时汽车的剩油}
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
{在I站购买恰好能到达J站的油量}
Buy(I,Oil[J]︿.Way – Oil[I]︿.Way – Oil[I]︿.Over);
Oil[J]︿.Over := 0.0;
end
else begin {附近无比I站便宜的加油站J}
Buy(I, MaxWay – Oil[I]︿.Over); {在I站加满油}
J := I + 1; {行驶到下一站}
Oil[J]︿.Over:= MaxWay – (Oil[J]︿.Way – Oil[I]︿.Way);
end;
I := J; {汽车直达J站}
until I = N; {汽车到达终点}
end;
begin {主程序}
Cost := 0;
Assign(Input, Inp);
Reset(Input);
Assign(Output, Outp);
Rewrite(Output);
if init then begin {如果有解}
Solve; {求解}
Writeln(Cost:0 :2); {输出最少费用}
end else
Writeln(‘No Solution’); {输出无解}
Close(Input);
Close(Output);
end.
例28：两机器加工问题
有n个部件需在A，B机器上加工，每个工件都必须经过先A后B两道工序。
已知：部件i在A、B机器上的加工时间分别为ai，bi。
问：如何安排n个工件的加工顺序，才能使得总加工时间最短？
输入示例：
N = 5
工件I 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
输出示例：
34 （最少时间）
1 5 4 2 3 （最优加工顺序）
分析：
本题求一个加工顺序使得加工总时间最短，要使时间最短，则就是让机器的空闲时间最短。一旦A机器开始加工，则A机器将会不停的进行作业，关键是B机器在加工过程中，有可能要等待A机器。很明显第一个部件在A机器上加工时，B机器必须等待，最后一个部件在B机器上加工，A机器也在等待B机器的完工。
可以大胆猜想，要使总的空闲的最少，就要把在A机器上加工时间最短的部件最先加工，这样使得B机器能以最快的速度开始加工；把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：
设Mi=min{ai, bi}
将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的已经作业后面，若Mi=bi，则将它排在从尾开始的作业前面。
例如：N=5
（a1，a2，a3，a4，a5）=（3，5，8，7，10）
（b1，b2，b3，b4，b5）=（6，2，1，4，9）
则（m1，m2，m3，m4，m5）=（3，2，1，4，9）
排序之后为（m3，m2，m1，m4，m5）
处理m3：∵m3=b3 ∴m3排在后面；加入m3之后的加工顺序为（ ， ， ， ，3）；
处理m2：∵m2=b2 ∴m2排在后面；加入m2之后的加工顺序为（ ， ， ，2，3）；
处理m1：∵m3=a1 ∴m1排在前面；加入m1之后的加工顺序为（1， ， ，2，3）；
处理m4：∵m4=b4 ∴m4排在后面；加入m4之后的加工顺序为（1， ，4，2，3）；
处理m5：∵m5=b5 ∴m5排在后面；加入m5之后的加工顺序为（1，5，4，2，3）；
则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。
问题是这种贪心策略是否正确呢？还需证明。
证明过程如下：
设S={J1，J2，……，Jn}，为待加工部件的作业排序，若A机器开始加工S中的部件时，B机器还在加工其它部件，t时刻后再可利用，在这样的条件下，加工S中任务所需的最短时间T（S，t）= min{ai+T(S-{Ji},bi+max{t-ai,0})} 其中，Ji∈S。
从图24可以看出，（a）为作业I等待机器B的情况，（b）为机器B等待作业I在机器A上完成的情形。
假设最佳的方案中，先加工作业Ji，然后加工作业Jj，则有：
T(S,t)=ai+T(S-{Ji},bi+Max{t-ai,0})
=ai+aj+T(S-{Ji,Jj},bj+max{bi+max{t-ai,0}-aj,0})
=ai+aj+T(S-{Ji,Jj},Tij)
Tij=bj+max{bi+max{t-ai,0}-aj,0}
=bj+bi-aj+max{max{t-ai,0},aj-bi}
=bi+bj-aj+max{t-ai,aj-bi,0}
=bi+bj-ai-aj+max{t,ai,ai+aj-bi}
若max{t,ai,ai+aj-bi}=t
若max{t,ai,ai+aj-bi}=ai
若max{t,ai,ai+aj-bi}=ai+aj-bi
若将作业Ji和作业Jj的加工顺序，则有：
T’(S,t)=ai+aj+T(S-(Ji,Jj),Tji)，其中
Tji=bi+bj-ai-aj+max{t,aj,ai+aj-bj}
按假设，因为T<=T’,所以有:
max{t,ai+aj-bi,ai}<=max{t,ai+aj-bj,aj} ……………… ①
于是有：
ai+aj+max{-bi,-aj}<=ai+aj+max{-bj,-ai}
即
Min{bj,ai}<=min{bi,aj} ……………… ②
②式便是Johnson公式。也就是说②式成立的条件下，任务Ji安排在任务Jj之前加工可以得到最优解。也就是说在A机器上加工时间短的任务应优先，而在B机器上加工时间短的任务应排在后面。因此，论证了开始设计的贪心算法是正确的。
算法流程如下：
for I := 1 to N do {求M数组}
if A[I] < B[I] then
M[I] := A[I]
else
M[I] := B[I]；
将M从小到大排序；
S := 1; T := N; {首位指针初始化}
for I := 1 to N do
if 对于第I小的工序J，若A[J] < B[J] then begin
Order[S] := J; {将工序J插在加工序列的前面}
S := S + 1;
end else begin
Order[T] := J; {将工序J插在加工序列的后面}
T := T - 1;
end;
程序如下：
program Machine;
const
Inp = 'input.txt';
Outp = 'output.txt';
MaxN = 100; {最多部件数}
var
N, Min: Integer;
A, B, M,
O, {O用来记录从小到大排序后部件的编号}
Order: array [1 .. MaxN] of Integer; {Order用来记录加工顺序}
procedure Init; {读入数据}
var
I: Integer;
begin
Assign(Input, Inp); Reset(Input);
Readln(N);
for I := 1 to N do
Read(A[I]);
Readln;
for I := 1 to N do
Read(B[I]);
Close(Input);
end;
procedure Main;
var
I, J, Z, S, T, T1, T2: Integer;
begin
FillChar(M, Sizeof(M), 0); {求M数组的值}
for I := 1 to N do
if A[I] < B[I] then M[I] := A[I] else M[I] := B[I];
for I := 1 to N do O[I] := I;
for I := 1 to N - 1 do {从小到大排序}
for J := I + 1 to N do
if M[O[I]] > M[O[J]] then begin
Z := O[I]; O[I] :=O[J]; O[J] := Z;
end;
FillChar(Order, Sizeof(Order), 0);
S := 1; T := N;
for I := 1 to N do
if M[O[I]] = A[O[I]] then begin
{若A[O[I]]
S := S + 1;
end else begin
{若B[O[I]]≧A[O[I]]，则插在加工序列的后面}
Order[T] := O[I];
T := T - 1;
end;
{计算最少加工时间}
T1 := 0; T2 := 0;
for I := 1 to N do begin
T1 := T1 + A[Order[I]];
if T2 < T1 then T2 := T1;
T2 := T2 + B[Order[I]];
end;
Min := T2;
end;
procedure Out; {打印输出}
var I: Integer;
begin
Assign(Output, Outp); Rewrite(Output);
Writeln(Min); {输出最少时间}
for I := 1 to N do {输出最佳加工序列}
Write(Order[I], ' ');
Writeln;
Close(Output);
end;
Begin
Init; {输入}
Main; {主过程}
Out; {输出}
End.
第八课 分治法
课题：分治法
目标：
知识目标：分治的原理与分治
同课章节目录