5、编码问题(95年全国分区联赛题)：设有一个数组A：array [0..N-1] of integer； 存放的元素为0～N-1(1<N<=10)之间的整数，且A≠A[j]（i≠j）。例如当N=6时，有：A=（4，3，0，5，1，2）。此时，数组A的编码定义如下：
A[0]编码为0；
A编码为：在A[0]，A[1]，…，A[i-1]中比A的值小的个数
（i=1，2，…，N-1）
∴上面数组A的编码为：B=（0，0，0，3，1，2）
要求编程解决以下问题：
(1)给出数组A后，求出其编码；
(2)给出数组A的编码后，求出A中的原数据
程序样例：
例一：
输入：Stat=1 {表示要解决的第（1）问题}
N=8 {输入８个数}
A=1 0 3 2 5 6 7 4
输出：B=0 0 2 2 4 5 6 4
例二：
输入：Stat=2 {表示要解决的第（2）问题}
N=7
B=0 1 0 0 4 5 6
输出：A=2 3 1 0 4 5 6
[解]第1个问题的解法：用穷举搜索法。
B[0]为0
B表示在A[1]，A[2]，……，A[i-1]中比A(i=1,2,……,N)小的个数。
第2个问题的解法：先构建数组P，初始值为0，1，2，３，……，N-1。然后从B[N-1]，B[N-2]，……，B[1]，B[0]逆向从数组P中取数求数组A。以题中例二为例，求解过程如下图：
下标值i B0 B1 B2 B3 B4 B5 B6
p0 p1 p2 p3 p4 p5 p6 数组A
6
0 1 0 0 4 5 6
↑ 0 1 2 3 4 5 6
A[6]=p[B6]=p6=6,划去p6
5 0 1 0 0 4 5 6
↑ 0 1 2 3 4 5
A[5]=p[B5]=p5=5,划去p5
4
0 1 0 0 4 5 6
↑ 0 1 2 3 4
A[4]=p[B4]=p4=4,划去p4
3
0 1 0 0 4 5 6
↑ 0 1 2 3
A[3]=p[B3]=p0=0,划去p0
2
0 1 0 0 4 5 6
↑ 1 2 3
A[2]=p[B2]=p0=1,划去p0
1
0 1 0 0 4 5 6
↑ 2 3
A[1]=p[B1]=p1=3,划去p2
0
0 1 0 0 4 5 6
↑ 2
A[0]=p[B0]=p0=2
从上述求解过程中，我们得到：A=（2，3，1，0，4，5，6）。
[程序]
program code;
var i,j,k,m,n,stat:integer;
A,B,P:array [0..10] of integer;
begin
write('Stat(1,or 2)=');readln(stat);
case stat of
1:begin write('N='); readln(n); write('A=');
for i:=0 to n-1 do read(A); readln; {读入数组A}
for i:=0 to n-2 do
for j:=i+1 to n-1 do
if (A=A[j])or(A>n-1) then {数组A中有否相等}
begin writeln('Input error!');halt; end;
for i:=0 to n-1 do B:=0; {编码数组B初始值为0}
for i:=1 to n-1 do
for j:=0 to i-1 do
if A>A[j] then B:=B+1; {求数组编码}
for i:=0 to n-1 do write(B:5);writeln;
end;
2:begin write('N='); readln(n); write('B=');
for i:=0 to n-1 do read(B); readln; {读编码数组B}
for i:=0 to n-1 do P:=i; {建立取数数列P}
for i:=n-1 downto 0 do {由编码数组B逆向求原数组A}
begin A:=P[B]; {A为数组P中第B号元素}
for j:=B to i-1 do P[j]:=P[j+1];{从P数组中删去P[B]}
end;
write('A=');
for i:=0 to n-1 do write(A:5);writeln; {输出数组A}
end;
end;
end.
第二章 算法应用
一、穷举搜索法
穷举搜索法是穷举所有可能情形，并从中找出符合要求的解。
穷举所有可能情形，最直观的是联系循环的算法。
[例]找出n个自然数(1,2,3,…,n)中r个数的组合。例如，当n=５,r=3时，所有组合为：
５ ４ ３
５ ４ ２
５ ４ １
５ ３ ２
５ ３ １
５ ２ １
４ ３ ２
４ ３ １
４ ２ １
３ ２ １
total=10 {组合的总数}
[解]n个数中r的组合，其中每r 个数中，数不能相同。另外，任何两组组合的数，所包含的数也不应相同。例如，５、４、３与３、４、５。为此，约定前一个数应大于后一个数。
将上述两条不允许为条件，当r=3时，可用三重循环进行搜索。
［程序］
Program zuhe11;
const n=5;
var i,j,k,t:integer;
begin t:=0;
for i:=n downto 1 do
for j:=n downto 1 do
for k:=n downto 1 do
if (i<>j)and(i<>k)and(i>j)and(j>k) then
begin t:=t+1;writeln(i:3,j:3,k:3);end;
writeln('total=',t);
end.
或者
Program zuhe12;
const n=5;r=3;
var i,j,k,t:integer;
begin t:=0;
for i:=n downto r do
for j:=i-1 downto r-1 do
for k:=j-1 downto 1 do
begin t:=t+1;writeln(i:3,j:3,k:3);end;
writeln('total=',t);
end.
这两个程序，前者穷举了所有可能情形，从中选出符合条件的解，而后者比较简洁。但是这两个程序都有一个问题，当r变化时，循环重数改变，这就影响了这一问题的解，即没有一般性。
但是，很多情况下穷举搜索法还是常用的。
二、递归法
递归法也是常用的方法。
［例］仍以前节例题为例，找n个数的r个数的组合。要求：
输入：n,r=5 3
输出：５ ４ ３
５ ４ ２
５ ４ １
５ ３ ２
５ ３ １
５ ２ １
４ ３ ２
４ ３ １
４ ２ １
３ ２ １
total=10 {组合的总数}
［解］分析所提示的10组数。首先固定第一位数（如５），其后是在另４个数中再“组合”２个数。这就将“５个数中３个数的组合”推到了“４个数中２个数的组合”上去了。第一位数可以是n r(如５ 3)，n个数中r个数组合递推到n-1个数中r-1个数有组合，这是一个递归的算法。即：
Procedure comb(n,r:integer);
var i:integer;
begin for i:=n downto r do
begin {固定i的输出位置}
comb(i-1,r-1); {原过程递推到i-1个数的r-1个数组合}
end;
end;
再考虑打印输出格式。
［程序］
Program zuhe2;
var k,n,r:integer;
Produrce comb(n,r:integer);
var i,temp:integer;
begin for i:=n downto r do
if (i<>n)and(k<>r) then {k为过程外定义的}
begin for temp:=1 to (k-r)*3 do write(' '); {确定i的输出位置}
end;
write(i:3);
if i>1 then comb(i-1,r-1); {递推到下一情形}
else writeln;
end;
Begin {main}
write('n,r=');readln(n,r);
if r>n then
begin writeln('Input n,r error!');halt; end;
comb(n,r); {调用递归过程}
End;
三、回溯法
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
［例］再以前例说明，找n个数中r个数的组合。
［解］将自然数排列在数组A中：
A[1] A[2] A[3]
5 4 3
5 4 2
…
3 2 １
排数时从A[1] A[2] A[3]，后一个至少比前一个数小１，并且应满足ri+A[ri]>r。若ri+A[ri]≤r就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为１，也应作一次回溯（若不回，便由上述回溯条件处理）。
［程序］
program zuhe3;
type tp=array[1..100] of integer;
var n,r:integer;
procedure comb2(n,r:integer;a:tp);
var i,ri:integer;
begin ri:=1;a[1]:=n;
repeat
if ri<>r then {没有搜索到底}
if ri+a[ri]>r then ｛是否回溯｝
begin a[ri+1]:=a[ri]-1;
ri:=ri+1;
end
else
begin ri:=ri-1; a[ri]:=a[ri]-1;end; {回溯}
else
begin for j:=1 to r do write(a[j]:3);writeln; {输出组合数}
if a[r]=1 then {是否回溯}
begin ri:=ri-1; a[ri]:=a[ri]-1;end; {回溯}
else a[ri]:=a[ri]-1; {递推到下一个数｝
end;
until a[1]<>r-1;
end;
begin {MAIN}
write('n,r=');readln(n,r);
if r>n then
begin writeln('Input n,r error!');halt; end
comb2(n,r);
end.
第三章 综合题解
综合测试题（一）
1、寻找数：求所有这样的三位数，这些三位数等于它各位数字的立方和。
例如，153＝13 ＋53 ＋33 。
[解]穷尽三位数，用一个循环语句。其数码可用“模取”运算MOD完成。
[程序]
PROGRAM lifang;
uses crt;
var i,a,b,c:integer;
begin
clrscr;
for i:=100 to 999 do
begin c:=i mod 10; ｛取个位数｝
b:=(i div 10) mod 10; ｛取十位数｝
a:=i div 100; ｛取百位数｝
if i=a*a*a+b*b*b+c*c*c then writeln(i:6);
end;
end.
２、最小自然数：求具有下列两个性质的最小自然数n：
(１)n的个位数是６；
(２)若将n的个位数移到其余各位数字之前，所得的新数是n的４倍。
[解]仍用穷举法寻找，当找到一个符合条件者便停止。“找到便停止”的重复，宜采用repeat－until循环。
由于不知道n是几位数，个位数移到前面去应借助一个指定位数的数。设为e。
[程序]
program minnum;
var n,e:integer;
begin e:=1;n:=1;
repeat e:=10*e;
repeat n:=n+1;
until not((n=e)or((10*n+6)*4=(6*e+n)));
until ((10*n+6)*4<>6*e+n);
writeln(10*n+6);
end.
３、找素数：寻找160以内的素数，它的倒序数（如123的倒序数为321）、数码和、数码积不是素数便是１。
[解]倒序数、数码和、数码积都需对原数分解，分解后再查它们是否符合条件。
[程序]
program sushu;
uses crt;
var i,j,n,s,p,f:integer;
function cond(k:integer):boolean;
var j:integer;b:boolean;
begin b:=true; {为1时表示k为素数}
if k<>1 then for j:=2 to k-1 do if k mod j=0 then b:=false;
if k=0 then cond:=false else cond:=b;
end;
begin {MIAN} clrscr;
for i:=2 to 160 do
if cond(i) then
begin j:=i;n:=0;s:=0;p:=1;
while j<>0 do
begin f:=j mod 10;
j:=j div 10;
n:=n*10+f;｛计算倒序数｝
s:=s+f; ｛计算数码和｝
p:=p*f; 计算数码积
end;
if (cond(n))and(cond(s))and(cond(p)) then write(i:5);
end;
writeln; readln
end.
４、完全平方数：寻找具有完全平方数，且不超过７位数码的回文数。所谓回文数是指这样的数，它的各位数码是左右对称的。例如121、676、94249等。
[解]判断一个数是否回文数，可以将其转化成字符判断。也可以分解数，所谓分解就是将数的后半段倒置后再与前半段比较。这里采用分解的方法，其函数为symm。
[程序]
program wcpfs;
uses crt;
var i:longint; s:longint;
function symm(n:longint):boolean;
var i,j,k:longint; m:longint;
begin i:=n;j:=1; {计算n的位数}
repeat j:=j+1;i:=i div 10;until (i<=9)and(i>=0);
k:=j div 2;m:=0;
for i:=1 to k do {分解前后两位数}
begin m:=m*10+(n mod 10);n:=n div 10; end;
if j mod 2=1 then ｛n是奇数位,中间位不要｝n:=n div 10;
symm:=(m=n);
end;
begin {MAIN} clrscr;
for i:=11 to round(sqrt(999999999)) do begin if symm(i*i) then writeln(i*i); end;
end.
５、成等差的素数：寻找６个成等差级数且小于160的素数。
[解]设级数为：n，n-d，n-2d，n-3d，n-4d，n-5d。若这６个数全为素数，则为要求的解。这里d、n均是要寻找的。仍用穷尽法，d最大可为33。判断素数函数为isprime。
[程序]
PROGRAM dcss(input,output);
var n,d:integer;
FUNCTION isprime(m:integer):integer; ｛判断素数函数｝
var b,i:integer;
begin b:=1;
if m<=0 then b:=0
else for i:=2 to trunc(sqrt(m)) do if m mod i=0 then b:=0;
isprime:=b;
end;
begin {main}
for d:=1 to 31 do for n:=160 downto 7 do
if (isprime(n)=1)and(isprime(n-d)=1) then
if (isprime(n-2*d)=1)and(isprime(n-3*d)=1) then
if (isprime(n-4*d)=1)and(isprime(n-5*d)=1) then
writeln(n:6,n-d:6,n-2*d:6,n-3*d:6,n-4*d:6,n-5*d:6);
end.
６、取数列：取｛2m ，3n ｜m>=1，n>=1｝中由小到大排列的前70项数。
[解]这个数的集合事实上存在两个数列：一个是2m ，另一个是3n 。若依次从两数列中取出小的进入新的数列，该新数列便为所求（这里不用数组，而直接打印输出）。
[程序]
program mn23;
const n=70;
var m2,n3:real; k:integer; f:text;
begin
assign(f,'exmn.txt');rewrite(f); {输出结果在文件exmn.txt中}
m2:=2;n3:=3;k:=0;
while k<n do
begin if m2<n3 then begin writeln(f,m2:40:0);m2:=m2*2; end
else begin writeln(f,n3:40:0);n3:=n3*3; end;
k:=k+1;
end;
close(f);
end.
７、发奖章：运动会连续开了n天，一共发了m枚奖章，第一天发１枚并剩下(m-1)枚的1/7，第二天发２枚并剩下的1/7，以后每天按此规律发奖章，在最后一天即第n天发了剩下的n枚奖章。问运动会开了多少天？一共发了几枚奖章？
[解]由于题目涉及m-1的1/7，于是m-1应是7的倍数，即m=7x+1。递推x，寻找m、n。
[程序]
PROGRAM sport;
var m,n,x,b:integer;
begin x:=0;
repeat x:=x+1;m:=7*x+1;n:=1;b:=1;
while (m>n) and (b=1) do
begin m:=m-n;
if (m mod 7=0) then m:=(m div 7)*6 else b:=0;n:=n+1;
end;
until b=0;
writeln('n=',n,' m=',7*x+1);
end.
８、猜名次：五个学生A、B、C、D、E参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为A、B、C、D、E，结果没有猜中任何一个学生的名次，也没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上邻接。例如１与２，或者２与３等）。乙猜的名次顺序为D、A、E、C、B，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？答案为：E、D、A、C、B。乙猜对C、B为最后两名，两对相邻为（D、A）、（C、B））。
[解]设五名选手A、B、C、D、E的编号分别为1、2、3、4、5。用五个变量c1、c2、c3、c4、c5标记第一名至第五名。算法仍用穷尽法。其中处理相邻问题用一个两位数表示，即DA、AE、EC、CB分别用41、15、53、32表示，并按两位数比较判断相邻问题。
[程序]
program mingci;
var c1,c2,c3,c4,c5,s1,s2,t:integer;
begin for c1:=2 to 5 do
for c2:=1 to 5 do
if (c2<>2)or((c2-c1)<>1) then
for c3:=1 to 5 do
if (c3<>3)or((c3-c2)<>1) then
for c4:=1 to 5 do
if (c4<>4)or((c4-c3)<>1) then
for c5:=1 to 4 do
if (c5-c4)<>1 then
begin s2:=0;
if c1=4 then s2:=s2+1;
if c2=1 then s2:=s2+1;
if c3=5 then s2:=s2+1;
if c4=3 then s2:=s2+1;
if c5=2 then s2:=s2+1;
s1:=0;
t:=10*c1+c2;
if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
t:=10*c2+c3;
if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
t:=10*c3+c4;
if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
t:=10*c4+c5;
if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
if (s1=2)and(s2=2) then
writeLn(c1:3,c2:3,c3:3,c4:3,c5:3);
end;
end.
９、填自然数：设有如图所示的3n＋2个球互连，将自然数1－3n＋2分别为这些球编号，使如图相连的球编号之差的绝对正好是数列1，2，……，3n+2中各数。
②─⑥ ②─⑨─⑤ ②─⑿─⑤─⑨
│ │ │ │ │ │ │ │ │
①─⑧─④─⑤ ①─⑾─④─⑧─⑦ ①─⒁─④─⑾─⑦─⑧
│ │ │ │ │ │ │ │ │
③─⑦ (n=2) ③─⑩─⑥ (n=3) ③─⒀─⑥─⑩ (n=4)
[解]填自然数的一种算法是：
(1)先自左向右，第１列中间１个填数，然后第２列上、下２个填数，每次２列；但若n是奇数，最后１次只排第１列中间１个数。
(2)自右向左，先右第１列中间填数；若n是奇数，再右第２列中间填数。然后依次右第１列上、下２个填数，再右第２列中间１个填数，直到左第２列为止。
[程序]
program ziyangshu;
uses crt;
const size=25;
var a:array[0..2,0..size] of integer; i,k,m,n:integer;
begin clrscr;write('Input then n:');readln(n);k:=1;
for i:=0 to n div 2 do
begin a[1,2*i]:=k;k:=k+1;
if ((i=n div 2)and(n mod 2=1)or(i<n div 2)) then
begin a[0,2*i+1]:=k;k:=k+1; a[2,2*i+1]:=k;k:=k+1; end;
end;
if n mod 2=1 then begin a[1,n+1]:=k;k:=k+1;m:=n end
else m:=n+1;
writeln(m);
for i:=0 to n div 2 do
begin a[1,m-2*i]:=k;k:=k+1; writeln(1,' ',m-2*i,' ',k);
a[0,m-2*i-1]:=k;k:=k+1; a[2,m-2*i-1]:=k;k:=k+1;
end;
write(' ':3);
for i:=1 to n do write(a[0,i]:3);writeln;
for i:=0 to n+1 do write(a[1,i]:3);writeln;write(' ':3);
for i:=1 to n do write(a[2,i]:3);writeln;
end.
综合测试题（二）
1、回文问题：递归法判断所输入的一行字符是否回文。这里所说的回文是指输入的一行字符，
以“-”字符为中心，其两边的字符是左右对称的。例如:
输入：ABCDE-EDCBA ↓
输出：It is symmetry. ｛输入一行字符是回文｝
[解]设一行字符为M-W，对于M分解成由ch1表记的一个字符与一子串m；对w分解成一字符子串w和由ch2表记的一个字符，因此M-W这“回文”取决于：(1)m-w是回文；（2)ch1-ch2。即将原问题递推到m-w的解。递归终止条件是M与W（或m与w）长度为０。“回归”时，若m－w是回文且ch1=ch2，则M-W是回文；否则M-W就不是回文。程序使用递归过程pp。
[程序]
PROGRAM MW;
var ch:char;
function pp:boolean;
var ch1,ch2:char; bl:boolean;
begin read(ch1);
if ch1='-' then bl:=true
else begin
if pp then begin read(ch2);bl:=ch1=ch2;end
else bl:=false;
end;
pp:=bl;
end;
begin {MAIN}
write('Input string:');
if pp then begin read(ch);
if ord(ch)=13 then begin writeln;writeln('It is symmetry.');end
else begin writeln;writeln('It is not symmetry.');end;
end
else begin writeln;writeln('It is not symmetry.');end
end.
２、三齿轮问题：三个齿轮啮合。如图在齿轮箱里
三个齿轮互相衔接，某瞬间两对齿相遇，问各转
多少圈后，这两对齿同时重逢。如图示。
（说明：用a，b，c分别表示三个齿轮的齿数。）
[解]这一问题是最小公倍数问题。设三齿轮齿数分别是na、nb、nc，[na，nb，nc]为最小公倍数，相遇各齿轮所转的圈数为最小公倍数除以自己的齿数。
[程序]
{$I-}
program cl;
var na,nb,nc,ma,mb,mc,l3:integer;
function gcd(x,y:integer):integer; { 求最大公约数函数 }
var r:integer;
begin
repeat r:=x mod y;x:=y;y:=r;until r=0;
gcd:=x;
end;
function lcm(x,y:integer):integer; { 求最小公倍数函数 }
begin lcm:=(x*y div gcd(x,y));
end;
function lcm3(a1,a2,a3:integer):integer; { 求三个数的最小公倍数函数 }
begin lcm3:=lcm(lcm(a1,a2),a3); end;
begin {main}
write('na,nb,nc=');readln(na,nb,nc); 读入三齿轮齿数
if (na<1)or(nb<1)or(nc<1) then begin writeln('Input error!');exit;end;
l3:=lcm3(na,nb,nc); {求na,nb,nc的最小公倍数}
ma:=l3 div na; {求各齿轮所转的圈数}
mb:=l3 div nb; mc:=l3 div nc;
writeln('For mesh must rotate about rings:',ma:3,mb:3,mc:3);
end.
３、计算合数：一个整数n（n<=100)可以有多种分划，使其分划的一列整数之和为n。例如：
输入：n=6
输出文件hs.out，格式内容为
6
5 1
4 2
4 1 1
3 3
3 2 1
3 1 1 1
2 2 2
2 2 1 1
2 1 1 1
1 1 1 1 1 1
total=11 {表示分划数有11种}
[解]采用递归算法。从最大合数开始分划，若当前分划数之和仍不大于n，则继续分解。否则回溯再寻找分划。
[程序]
｛$S-｝
program hs;
var i,j,m,k,t:integer;
n:array[0..100] of integer;
f:text;
procedure output_sum;
var j:integer;
begin t:=t+1;j:=0;
while n[j]<>0 do ｛输出所有不为的合数｝
begin write(f,n[j]:3);j:=j+1;end;
writeln(f);
end;
procedure sum(i:integer);
begin
if m-n<=n then {整数分解后的余数不大于已分解的合数}
begin n[i+1]:=m-n;m:=m-n; i:=i+1;n[i+1]:=0; end
else {整数分解后的余数大于已分解的合数}
begin n[i+1]:=n;m:=m-n;i:=i+1;end;
if m<>n then sum(i) {未分解完继续分解}
else output_sum; {输出合数}
if n>1 then {若合数大于1可继续分解,否则回溯寻找大于1的合数}
begin n:=n-1;sum(i);end
else
begin while (n=1)and(i>0) do
begin i:=i-1;m:=m+n;end;
if i<>0 then {找到大于1的合数,则继续分解}
begin n:=n-1;sum(i);end;
end;
end;
begin {MAIN}
assign(f,'hs.out');rewrite(f);
write('Input a number:');readln(n[0]);
t:=0;m:=n[0];k:=n[0]; {第1个合数设为要分解的数}
for i:=1 to k do
n:=0; {除第1个合数外所有合数初值均为0}
output_sum; {输出第1次分解的合数}
while n[0]<>1 do {第1个合数不为1,则继续分解寻找合数}
begin n[0]:=n[0]-1;i:=0;
sum(0); m:=k;
end;
writeln(f,'total=',t); close(f)
end.
４、旅行路线选择：设有n个城市（或景点），今从某市出发遍历各城市，使之旅费最少（即找出一条旅费最少的路径）。
输入部分：各城市间的旅费表由输入文件提供。
输出部分：旅费最少的一条路径及总费用。
例如：
输入文件名：ex14501.dat
输出文件名：1.out
其中，输入文件ex14501.dat的内容如下：
0 17 13 24 10
10 0 20 9 6
17 29 0 21 28
12 10 22 0 19
12 18 31 20 0
输出文件1.out的内容如下：
The route path is:0->2->3->1->4->0 ｛最少旅费城市路径｝
Total of traveling expense: 62 {最少旅费数}
[解]设矩阵元素aij 表示从第i号城市到第j号城市之旅费。并设城市间往返旅费可以不等（即aij ≠aji ）。aii 是没有意义的，由于问题是求最少，因此aii 不应为零，今试为无穷（∞）。各城市间旅费如下表：
∞ 17 13 24 10
10 ∞ 20 9 6
17 29 ∞ 21 28
12 10 22 ∞ 19
12 18 31 20 ∞
问题的算法是在表每行中找最小元素，并用该数减该行非∞元素。再对每列也施同样工作，形成一个新表（保证每行、每列均不少于１个为零），所有减数累加为min（其含义为旅费下界，即旅费不会少于min）。旅行路程因成环路，故可设起点是第０号城市。若选第i号到第j号城市，则表上bij 表示还需旅费，同时由于选了i→j，则i不可能再选向其它城市，则第i行全填∞，同理，由于j已由i过来，则第j城市不可能再由其它城市过来，第j列也全填上∞。对新矩阵再施每行至少有一个０，每列至少有一个０，找出余下城市遍历所需旅费下界mj 。对于不同的j，比较mj +bij 以最小的一个为选定从i到达的城市，并将选择路径记下。如此重复直到选完。下列表表示了分枝选择和每次选择的旅费下界。
初始表： min=61
* 7 0 11 0
4 * 11 0 0
0 12 * 1 11
2 0 9 * 9
0 6 16 5 *
从０号城市出发的４种可能：
0→1 min=9 0→2 min=0
* * * * * * * * * *
4 * 4 0 0 4 * 4 0 0
0 * * 1 11 0 * * 1 11
0 * 0 * 7 0 * 0 * 7
0 * 9 5 * 0 * 9 5 *
0→3 min=9 0→2 min=0
* * * * * * * * * *
4 * 2 * 0 4 * 2 0 *
0 12 * * 11 0 12 * 1 *
0 0 0 * 9 2 0 0 * *
0 6 7 * * 0 6 7 5 *
从中选择应是0→2。再从2出发，有３种选择：
2→1 min=2 2→3 min=0 2→4 min=0
* * * * * * * * * * * * * * *
4 * * 0 0 4 * * * 0 4 * * * *
* * * * * * * * * * 0 * * * *
0 * * * 7 2 0 * * 9 2 0 * * *
0 * * 5 * 0 6 * * * 0 6 * * *
从中应选2→3。再从3出发，2种选择：
3→1 min=0 3→4 min=10
* * * * * * * * * *
4 * * * 0 0 * * * *
* * * * * * * * * *
* * * * * * * * * *
0 * * * * 0 0 * * *
从中选3→1。再从2出发可选：
1→4 min=0
* * * * *
* * * * *
* * * * *
* * * * *
0 * * * *
[程序]
program mm;
uses crt;
const n=5;
max=1000;
type tp=array[0..n,0..n] of integer;
var f1,f2:text; fn1,fn2:string;
i,j,k,min,m1,m,jj,kk,si,sj:integer;
a,b,c,d:tp;
path,s:array[0..n] of integer;
procedure p(var b:tp;var m:integer);
var pi,pj,pk:integer;
px,py:integer;
begin m:=0;
for pi:=0 to n-1 do
begin pk:=max;
for pj:=0 to n-1 do
if b[pi,pj]<pk then pk:=b[pi,pj];
if (pk>0)and(pk<>max) then
begin m:=m+pk;
for pj:=0 to n-1 do
if b[pi,pj]<>max then
b[pi,pj]:=b[pi,pj]-pk;
end;
end;
for pj:=0 to n-1 do
begin pk:=max;
for pi:=0 to n-1 do
if b[pi,pj]<pk then pk:=b[pi,pj];
if (pk>0)and(pk<>max) then
begin m:=m+pk;
for pi:=0 to n-1 do
if b[pi,pj]<>max then
b[pi,pj]:=b[pi,pj]-pk;
end;
end;
end;
begin ｛MAIN｝
clrscr;write('Input filename:');readln(fn1);
write('Output filename:');readln(fn2);
assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2);
writeln(f2,'Traveling expenses table:');
for i:=0 to n-1 do ｛读城市旅费表｝
begin for j:=0 to n-1 do
begin read(f1,a[i,j]);write(f2,a[i,j]:6);end;
writeln(f2);
end;
for i:=0 to n-1 do a[i,i]:=max; ｛aii无意义的,设为max｝
k:=0;path[0]:=0;i:=0;s[0]:=max; ｛从0号城市出发｝
for j:=1 to n-1 do s[j]:=0; ｛s[j]为0时表示未到达j号城市,否则已走过｝
for si:=0 to n-1 do ｛矩阵转置｝
for sj:=0 to n-1 do
b[si,sj]:=a[si,sj];
p(b,min); ｛调用函数,计算旅费下界及最低旅费｝
repeat
m1:=max;
for j:=0 to n-1 do
if (s[j]=0)and(b[i,j]<>max) then 可到达的城市却未遍历
begin
for si:=0 to n-1 do
for sj:=0 to n-1 do
c[si,sj]:=b[si,sj]; ｛矩阵转置｝
for kk:=0 to n-1 do ｛从i城市出发已不可能,从其他城市到j城市也不可能｝
begin c[i,kk]:=max;c[kk,j]:=max; end;
p(c,m); ｛调用函数,计算从i到j城市的旅费下界｝
if m+b[i,j]<m1 then ｛求最小旅费路径｝
begin m1:=m+b[i,j];jj:=j;
for si:=0 to n-1 do
for sj:=0 to n-1 do
d[si,sj]:=c[si,sj]; ｛保存最小旅费表｝
end;
end;
for si:=0 to n-1 do
for sj:=0 to n-1 do
b[si,sj]:=d[si,sj]; ｛将所选择的最小旅费表存入初始表｝
min:=min+m1;i:=jj; ｛jj号城市作为出发点｝
k:=k+1;path[k]:=jj;
s[jj]:=max;sj:=max;
for si:=0 to n-1 do ｛判断所有城市是否都已到达｝
if s[si]<>max then sj:=0;
until sj=max; ｛直至所有城市都已走过为止｝
write(f2,'The route path is:');
for i:=0 to k do write(f2,path,'->');
writeln(f2,'0');
writeln(f2,'Total of traveling expense:',min:5);
close(f1);close(f2);
end.
