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 {输入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,3,……,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=5,r=3时,所有组合为:
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
total=10 {组合的总数}
[解]n个数中r的组合,其中每r 个数中,数不能相同。另外,任何两组组合的数,所包含的数也不应相同。例如,5、4、3与3、4、5。为此,约定前一个数应大于后一个数。
将上述两条不允许为条件,当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
输出:5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
total=10 {组合的总数}
[解]分析所提示的10组数。首先固定第一位数(如5),其后是在另4个数中再“组合”2个数。这就将“5个数中3个数的组合”推到了“4个数中2个数的组合”上去了。第一位数可以是n r(如5 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 1
排数时从A[1] A[2] A[3],后一个至少比前一个数小1,并且应满足ri+A[ri]>r。若ri+A[ri]≤r就要回溯,该关系就是回溯条件。为直观起见,当输出一组组合数后,若最后一位为1,也应作一次回溯(若不回,便由上述回溯条件处理)。
[程序]
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.
2、最小自然数:求具有下列两个性质的最小自然数n:
(1)n的个位数是6;
(2)若将n的个位数移到其余各位数字之前,所得的新数是n的4倍。
[解]仍用穷举法寻找,当找到一个符合条件者便停止。“找到便停止”的重复,宜采用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.
3、找素数:寻找160以内的素数,它的倒序数(如123的倒序数为321)、数码和、数码积不是素数便是1。
[解]倒序数、数码和、数码积都需对原数分解,分解后再查它们是否符合条件。
[程序]
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.
4、完全平方数:寻找具有完全平方数,且不超过7位数码的回文数。所谓回文数是指这样的数,它的各位数码是左右对称的。例如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.
5、成等差的素数:寻找6个成等差级数且小于160的素数。
[解]设级数为:n,n-d,n-2d,n-3d,n-4d,n-5d。若这6个数全为素数,则为要求的解。这里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.
6、取数列:取{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.
7、发奖章:运动会连续开了n天,一共发了m枚奖章,第一天发1枚并剩下(m-1)枚的1/7,第二天发2枚并剩下的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.
8、猜名次:五个学生A、B、C、D、E参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为A、B、C、D、E,结果没有猜中任何一个学生的名次,也没有猜中任何一对相邻名次(所谓一对相邻名次,是指其中一对选手在名次上邻接。例如1与2,或者2与3等)。乙猜的名次顺序为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.
9、填自然数:设有如图所示的3n+2个球互连,将自然数1-3n+2分别为这些球编号,使如图相连的球编号之差的绝对正好是数列1,2,……,3n+2中各数。
②─⑥ ②─⑨─⑤ ②─⑿─⑤─⑨
│ │ │ │ │ │ │ │ │
①─⑧─④─⑤ ①─⑾─④─⑧─⑦ ①─⒁─④─⑾─⑦─⑧
│ │ │ │ │ │ │ │ │
③─⑦ (n=2) ③─⑩─⑥ (n=3) ③─⒀─⑥─⑩ (n=4)
[解]填自然数的一种算法是:
(1)先自左向右,第1列中间1个填数,然后第2列上、下2个填数,每次2列;但若n是奇数,最后1次只排第1列中间1个数。
(2)自右向左,先右第1列中间填数;若n是奇数,再右第2列中间填数。然后依次右第1列上、下2个填数,再右第2列中间1个填数,直到左第2列为止。
[程序]
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)长度为0。“回归”时,若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.
2、三齿轮问题:三个齿轮啮合。如图在齿轮箱里
三个齿轮互相衔接,某瞬间两对齿相遇,问各转
多少圈后,这两对齿同时重逢。如图示。
(说明:用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.
3、计算合数:一个整数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.
4、旅行路线选择:设有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 ∞
问题的算法是在表每行中找最小元素,并用该数减该行非∞元素。再对每列也施同样工作,形成一个新表(保证每行、每列均不少于1个为零),所有减数累加为min(其含义为旅费下界,即旅费不会少于min)。旅行路程因成环路,故可设起点是第0号城市。若选第i号到第j号城市,则表上bij 表示还需旅费,同时由于选了i→j,则i不可能再选向其它城市,则第i行全填∞,同理,由于j已由i过来,则第j城市不可能再由其它城市过来,第j列也全填上∞。对新矩阵再施每行至少有一个0,每列至少有一个0,找出余下城市遍历所需旅费下界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号城市出发的4种可能:
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出发,有3种选择:
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.