说明本文件部分程序来自一些信息学奥赛的参考书

1、说明：本文件部分程序来自一些信息学奥赛的参考书，如早年的信息学高级本等。时间关系，未能一一列出出处，请原作者见谅。部分图尚未画出，争取尽快补上。【execans.2 为深度优先搜索，广度优先搜索类,及技巧性题目题解】【题目1】N皇后问题(八皇后问题的扩展)【题目2】排球队员站位问题【题目3】把自然数分解为若干个自然数之和。【题目4】把自然数分解为若干个自然数之积。【题目5】马的遍历问题。【题目6】加法分式分解【题目7】地图着色问题【题目8】在n*n的正方形中放置长为2,宽为1的长条块,【题目9】找迷宫的最短路径。（广度优先搜索算法）【题目10】火车调度问题【题目11】农夫过河【题目12】七段数

2、码管问题。【题目13】把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续.【题目14】在44的棋盘上放置8个棋,要求每一行,每一列上只能放置2个.【题目15】迷宫问题.求迷宫的路径.(深度优先搜索法)【题目16】一笔画问题【题目17】城市遍历问题.【题目18】棋子移动问题【题目19】求集合元素问题（1,2x+1,3X+1类)=【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。const max=8;var i,j:integer;a:array1.max

3、of 0.max; 放皇后数组b:array2.2*max of boolean;/对角线标志数组c:array-(max-1).max-1 of boolean; 对角线标志数组col:array1.max of boolean; 列标志数组total:integer; 统计总数procedure output; 输出var i:integer;begin write(No.:4,total+1:2,); for i:=1 to max do write(ai:3);write( ); if (total+1) mod 2 =0 then writeln; inc(total);end;fu

4、nction ok(i,dep:integer):boolean; 判断第dep行第i列可放否beginok:=false;if ( bi+dep=true) and ( cdep-i=true) and (adep=0) and (coli=true) then ok:=trueend;procedure try(dep:integer);var i,j:integer;begin for i:=1 to max do 每一行均有max种放法 if ok(i,dep) then begin adep:=i; bi+dep:=false; /对角线已放标志 cdep-i:=false; 对角线

5、已放标志 coli:=false; 列已放标志 if dep=max then output else try(dep+1); 递归下一层 adep:=0; 取走皇后,回溯 bi+dep:=true; 恢复标志数组 cdep-i:=true; coli:=true; end;end;begin for i:=1 to max do begin ai:=0;coli:=true;end; for i:=2 to 2*max do bi:=true; for i:=-(max-1) to max-1 do ci:=true; total:=0; try(1); writeln(total:,tot

6、al);end.【测试数据】n=8 八皇后问题 No. 1 1 58 6 3 7 2 4 No. 2 1 6 83 7 4 2 5 No. 3 1 74 6 8 2 5 3 No. 4 1 7 58 2 4 6 3 No. 5 2 46 8 3 1 7 5 No. 6 2 5 71 3 8 6 4 No. 7 2 57 4 1 8 6 3 No. 8 2 6 17 4 8 3 5 No. 9 2 68 3 1 4 7 5 No.10 2 7 36 8 5 1 4 No.11 2 75 8 1 4 6 3 No.12 2 8 61 3 5 7 4 No.13 3 17 5 8 2 4 6 No.

7、14 3 5 28 1 7 4 6 No.15 3 52 8 6 4 7 1 No.16 3 5 71 4 2 8 6 No.17 3 58 4 1 7 2 6 No.18 3 6 25 8 1 7 4 No.19 3 62 7 1 4 8 5 No.20 3 6 27 5 1 8 4 No.21 3 64 1 8 5 7 2 No.22 3 6 42 8 5 7 1 No.23 3 68 1 4 7 5 2 No.24 3 6 81 5 7 2 4 No.25 3 68 2 4 1 7 5 No.26 3 7 28 5 1 4 6 No.27 3 72 8 6 4 1 5 No.28 3 8

8、 47 1 6 2 5 No.29 4 15 8 2 7 3 6 No.30 4 1 58 6 3 7 2 No.31 4 25 8 6 1 3 7 No.32 4 2 73 6 8 1 5 No.33 4 27 3 6 8 5 1 No.34 4 2 75 1 8 6 3 No.35 4 28 5 7 1 3 6 No.36 4 2 86 1 3 5 7 No.37 4 61 5 2 8 3 7 No.38 4 6 82 7 1 3 5 No.39 4 68 3 1 7 5 2 No.40 4 7 18 5 2 6 3 No.41 4 73 8 2 5 1 6 No.42 4 7 52 6

9、1 3 8 No.43 4 75 3 1 6 8 2 No.44 4 8 13 6 2 7 5 No.45 4 81 5 7 2 6 3 No.46 4 8 53 1 7 2 6 No.47 5 14 6 8 2 7 3 No.48 5 1 84 2 7 3 6 No.49 5 18 6 3 7 2 4 No.50 5 2 46 8 3 1 7 No.51 5 24 7 3 8 6 1 No.52 5 2 61 7 4 8 3 No.53 5 28 1 4 7 3 6 No.54 5 3 16 8 2 4 7 No.55 5 31 7 2 8 6 4 No.56 5 3 84 7 1 6 2

10、No.57 5 71 3 8 6 4 2 No.58 5 7 14 2 8 6 3 No.59 5 72 4 8 1 3 6 No.60 5 7 26 3 1 4 8 No.61 5 72 6 3 1 8 4 No.62 5 7 41 3 8 6 2 No.63 5 84 1 3 6 2 7 No.64 5 8 41 7 2 6 3 No.65 6 15 2 8 3 7 4 No.66 6 2 71 3 5 8 4 No.67 6 27 1 4 8 5 3 No.68 6 3 17 5 8 2 4 No.69 6 31 8 4 2 7 5 No.70 6 3 18 5 2 4 7 No.71

11、6 35 7 1 4 2 8 No.72 6 3 58 1 4 2 7 No.73 6 37 2 4 8 1 5 No.74 6 3 72 8 5 1 4 No.75 6 37 4 1 8 2 5 No.76 6 4 15 8 2 7 3 No.77 6 42 8 5 7 1 3 No.78 6 4 71 3 5 2 8 No.79 6 47 1 8 2 5 3 No.80 6 8 24 1 7 5 3 No.81 7 13 8 6 4 2 5 No.82 7 2 41 8 5 3 6 No.83 7 26 3 1 4 8 5 No.84 7 3 16 8 5 2 4 No.85 7 38 2

12、 5 1 6 4 No.86 7 4 25 8 1 3 6 No.87 7 42 8 6 1 3 5 No.88 7 5 31 6 8 2 4 No.89 8 24 1 7 5 3 6 No.90 8 2 53 1 7 4 6 No.91 8 31 6 2 5 7 4 No.92 8 4 13 6 2 7 5total:92对于N皇后:皇后 N 4 5 6 7 8 9 10 方案数 2 10 4 40 92 352 724 【题目】排球队员站位问题图为排球场的平面图，其中一、二、三、四、五、六为位置编号，二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，一、四号位放主攻手，二、五号位放

13、二传手，三、六号位放副攻手。队员所穿球衣分别为，号，但每个队 四 三 二 员的球衣都与他们的站位号不同。已知号、号队员不在后排，号、号队员不是二传手，号、号队员不在同一排，号、 五 六 一 号队员不是副攻手。编程求每个队员的站位情况。【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。【参考程序】type sset=set of 1.6;var a:array1.6of 1.6; d:array1.6of sset; i:integer;procedure output; 输出begin if not( (a3in 2,3,4)= (a4 in2,3,4) then beg

14、in 3,4号队员不在同一排 write(number:);for i:=1 to 6 do write(i:8);writeln; write(weizhi:);for i:=1 to 6 do write(ai:8);writeln; end;end;procedure try(i:integer;s:sset); 递归过程 i:第i个人,s:哪些位置已安排人了var j,k:integer;begin for j:=1 to 6 do begin每个人都有可能站1-6这6个位置 if (j in di) and not(j in s) then begin j不在di中,则表明第i号人不

15、能站j位. j如在s集合中,表明j位已排人了 ai:=j; 第 i 人可以站 j 位 if i6 then try(i+1,s+j) 未安排妥,则继续排下去 else output; 6个人都安排完,则输出 end; end;end;begin for i:=1 to 6 do di:=1.6-i; 每个人的站位都与球衣的号码不同 d1:=d1-1,5,6; d6:=d6-1,5,6; 1,6号队员不在后排 d2:=d2-2,5; d3:=d3-2,5; 2,3号队员不是二传手 d5:=d5-3,6; d6:=d6-3,6; 5,6号队员不是副攻手 try(1,);end.【题目】把自然数分解

16、为若干个自然数之和。【参考答案】 n total 5 7 6 11 7 1510 42100 190569291【参考程序】var n:byte; num:array0.255 of byte;total:word;procedure output(dep:byte);var j:byte;begin for j:=1 to dep do write(numj:3);writeln; inc(total);end;procedure find(n,dep:byte); N:待分解的数,DEP:深度 var i,j,rest:byte; begin for i:=1 to n do 每一位从N到

17、1去试 if numdep-10) then begin find(rest,dep+1);end else if rest=0 then output(dep);刚好相等则输出 numdep:=0; end; end;begin 主程序 writeln(input n:);readln(n); fillchar(num,sizeof(num),0); total:=0; num0:=0; find(n,1); writeln(sum=,total);end.【题目】把自然数分解为若干个自然数之积。【参考程序】var path :array1.1000 of integer; total,n:

18、integer;procedure find(k,sum,dep:integer); K:var b,d:Integer;begin if sum=n then 积等于N beginwrite(n,=,path1);for d:=2 to dep-1 do write(*,pathd);writeln;inc(total);exit; end; if sumn then exit; 累积大于N for b:= trunc(n/sum)+1 downto k do每一种可能都去试begin pathdep:=b; find(b,sum*b,dep+1);end;end;beginreadln(n

19、); total:=0;find(2,1,1);writeln(total:,total);readln;end.【题目】马的遍历问题。在的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。【参考程序】 深度优先搜索法const n=5;m=4;fx:array1.8,1.2of -2.2=(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1), (-2,1),(-1,2); 八个方向增量var dep,i:byte; x,y:byte; cont:integer; 统计总数 a:array1.n,1.mof byte

20、; 记录走法数组procedure output; 输出,并统计总数var x,y:byte;begin cont:=cont+1; writeln; writeln(count=,cont); for y:=1 to n do beginfor x:=1 to m do write(ay,x:3); writeln; end; readln; halt;end;procedure find(y,x,dep:byte);var i,xx,yy:integer;begin for i:=1 to 8 do begin xx:=x+fxi,1;yy:=y+fxi,2; 加上方向增量,形成新的坐标i

21、f (xx in 1.m)and(yy in 1.n)and(ayy,xx=0) then 判断新坐标是否出界,是否已走过? begin ayy,xx:=dep; 走向新的坐标 if (dep=n*m) then output else find(yy,xx,dep+1); 从新坐标出发,递归下一层 ayy,xx:=0 回溯,恢复未走标志 end; end;end;begin cont:=0; fillchar(a,sizeof(a),0); dep:=1; writeln(input y,x);readln(y,x); x:=1;y:=1; if (yn) or(xm) then begin

22、 writeln(x,y error!);halt;end; ay,x:=1; find(y,x,2); if cont=0 then writeln(No answer!) else write(The End!); readln;end.【题目】加法分式分解。如：1/2=1/4+1/4.找出所有方案。输入： 为要分解的分数的分母为分解成多少项【参考程序】program fenshifenjie;const nums=5;var t,m,dep:integer; n,maxold,max,j:longint; path:array0.nums of longint; maxok,p:bool

23、ean; sum,sum2:real;procedure print;var i:integer;begin t:=t+1; if maxok=true then begin maxold:=pathm;maxok:=false;end; write (NO.,t); for i:=1 to m do write( ,pathi:4); writeln; if path1=pathm then begin writeln(Ok! total:,t:4);readln;halt;end;end;procedure input;begin writeln (input N:); readln(n)

24、; writeln (input M(M=,nums:1,):); readln(m); if (n=0) or (m4) or (nmaxlongint) then begin writeln(Invalid Input!);readln;halt;end;end;function sum1(ab:integer):real;var a,b,c,d,s1,s2:real; i:integer;begin if ab=1 then sum1:=1/path1 else begin a:=path1; b:=1 ; c:=path2; d:=1; for i:=1 to ab-1 do begi

25、n s2:=(c*b+a*d); s1:=(a*c); a:=s1; b:=s2; c:=pathi+2; end; sum1:=s2/s1; end;end;procedure back;begin dep:=dep-1; if dep=m-2 then max:=maxold; sum:=sum-1/pathdep; j:=pathdep;end;procedure find;begin repeat dep:=dep+1; j:=pathdep-1-1; p:=false; repeat j:=j+1; if (depm) and (j=1/n then p:=false else be

26、gin p:=true; pathdep:=j; sum:=sum+1/pathdep; end else if jmax then back; if dep=m then begin pathdep:=j; sum2:=sum1(m); if (sum2)1/n then p:=false; if (sum2)=1/n then begin print; max:=j; back; end; if (sum2=max) then back; end; until p until dep=0;end;begin INPUT; maxok:=true; for t:=0 to m do path

27、t:=n; dep:=0; t:=0; sum:=0; max:=maxlongint; find; readln;end.【题目】地图着色问题【参考程序】const lin:array1.12,1.12 of 0.1 区域相邻数组,1表示相邻 =(0,1,1,1,1,1,0,0,0,0,0,0),(1,0,1,0,0,1,1,1,0,0,0,0),(1,1,0,1,0,0,0,1,1,0,0,0),(1,0,1,0,1,0,1,0,1,1,0,0),(1,0,0,1,0,1,0,0,0,1,1,0),(1,1,0,0,1,0,1,0,0,0,1,0),(0,1,0,0,0,1,0,1,0,0

28、,1,1),(0,1,1,0,0,0,1,0,1,0,0,1),(0,0,1,1,0,0,0,1,0,1,0,1),(0,0,0,1,1,0,0,0,1,0,1,1),(0,0,0,0,1,1,1,0,0,1,0,1),(0,0,0,0,0,0,1,1,1,1,1,1);var color:array1.12 of byte; color数组放已填的颜色 total:integer;function ok(dep,i:byte):boolean; 判断选用色i是否可用var k:byte; 条件:相邻的区域颜色不能相同begin for k:=1 to dep do if (lindep,k=

29、1) and (i=colork) then begin ok:=false;exit;end; ok:=true;end;procedure output; 输出var k:byte;begin for k:=1 to 12 do write(colork, );writeln; total:=total+1;end;procedure find(dep:byte); 参数dep:当前正在填的层数var i:byte;begin for i:=1 to 4 do begin 每个区域都可能是1-4种颜色 if ok(dep,i) then begin colordep:=i; if dep=

30、12 then output else find(dep+1); colordep:=0; 恢复初始状态,以便下一次搜索 end; end;end;begin total:=0; 总数初始化 fillchar(color,sizeof(color),0); find(1); writeln(total:=,total);end.【参考程序】const lin数组:代表区域相邻情况 lin:array1.12 of set of 1.12 = (2,3,4,5,6,1,3,6,7,8,1,2,4,8,9,1,3,5,9,10,1,4,6,10,11, 1,2,5,7,11,12,8,11,6,2

31、,12,9,7,2,3,12,8,10,3,4, 12,9,11,4,5,12,7,10,5,6,7,8,9,10,11);color:array1.4 of char=(r,y,b,g);var a:array1.12 of byte; 因有12个区域,故a数组下标为1-12 total:integer;function ok(dep,i:integer):boolean; 判断第dep块区域是否可填第i种色var j:integer; j 为什么设成局部变量?begin ok:=true; for j:=1 to 12 do if (j in lindep) and (aj=i) then

32、 ok:=false;end;procedure output; 输出过程 var j:integer; j 为什么设成局部变量? begin inc(total); 方案总数加1 write(total:4); 输出一种方案 for j:=1 to 12 do write(coloraj:2);writeln;end;procedure find(dep:byte);var i:byte; i 为什么设成局部变量?begin for i:=1 to 4 do 每一区域均可从4种颜色中选一 begin if ok(dep,i) then begin 可填该色 adep:=i; 第dep块区域填

33、第i种颜色 if (dep=12) then output 填完12个区域 else find(dep+1); 未填完 adep:=0; 取消第dep块区域已填的颜色 end; end;end;begin 主程序 fillchar(a,sizeof(a),0); 记得要给变量赋初值! total:=0; find(1); writeln(End.);end.【题目】在n*n的正方形中放置长为2,宽为1的长条块,问放置方案如何【参考程序】const n=4;var k,u,v,result:integer; a:array1.n,1.nof char;procedure printf; 输出 b

34、egin result:=result+1;方案总数加1 writeln(- ,result, -); for v:=1 to n do beginfor u:=1 to n do write(au,v); writeln end; writeln; end;procedure try; 填放长条块 var i,j,x,y:integer; full:boolean; begin full:=true; if ktrunc(n*n/2) then full:=false;测试是否已放满 if full then printf; 放满则可输出 if not full then begin 未满

35、x:=0;y:=1; 以下先搜索未放置的第一个空位置 repeat x:=x+1; if xn then begin x:=1;y:=y+1 end until ax,y= ; 找到后,分两种情况讨论 if ax+1,y= then begin 第一种情况:横向放置长条块 k:=k+1;记录已放的长条数 ax,y:=chr(k+ord(); 放置 ax+1,y:=chr(k+ord(); try;递归找下一个空位置放 k:=k-1; ax,y:= ; 回溯,恢复原状 ax+1,y:= end; if ax,y+1= then begin 第二种情况:竖向放置长条块 k:=k+1; 记录已放的长

36、条数 ax,y:=chr(k+ord(0); 放置 ax,y+1:=chr(k+ord(0); try; 递归找下一个空位置放 k:=k-1; ax,y:= ; 回溯,恢复原状 ax,y+1:= end; end; end;begin 主程序 fillchar(a,sizeof(a), ); 记录放置情况的字符数组,初始值为空格 result:=0; k:=0; k记录已放的块数,如果k=n*n/2,则说明已放满 try; 每找到一个空位置,把长条块分别横放和竖放试验end.【参考程序】const dai:array 1.2,1.2of integer=(0,1),(1,0);type nod

37、e=recordw,f:integer;end;var a:array1.20,1.20of integer;path:array0.200of node;s,m,n,nn,i,j,x,y,dx,dy,dep:integer;p,px:boolean;procedure inputn;begin write(input n);readln(n); n:=4; nn:=n*n;m:=nn div 2;end;procedure print;var i,j:integer;begin inc(s);writeln(no,s); for i:=1 to n do begin for j:=1 to

38、n do write(ai,j:3);writeln; end; writeln;end;function fg(h,v:integer):boolean;var p:boolean;begin p:=false; if (h=n) and (v=n) thenif ah,v=0 then p:=true; fg:=p; end;procedure back; begin dep:=dep-1; if dep=0 then begin p:=true ;px:=true;end else begini:=pathdep.w;j:=pathdep.f;x:=(i-1)div n )+1;y:=i

39、 mod n;if y=0 then y:=n;dx:=x+daij,1;dy:=y+daij,2;ax,y:=0;adx,dy:=0;end;end;begin inputn; s:=0; fillchar(a,sizeof(a),0); x:=0;y:=0;dep:=0; path0.w:=0;path0.f:=0; repeat dep:=dep+1; i:=pathdep-1.w; repeat i:=i+1;x:=(i-1)div n)+1; y:=i mod n;if y=0 then y:=n; px:=false; if fg(x,y) then begin j:=0;p:=f

40、alse; repeat inc(j); dx:=x+daij,1;dy:=y+daij,2; if fg(dx,dy) and (j=2 then back else p:=false; until p; end else if i=nn then back else px:=false; until px; until dep=0; readln; end.【题目】找迷宫的最短路径。（广度优先搜索算法）【参考程序】uses crt;constmigong:array 1.5,1.5 of integer=(0,0,-1,0,0), (0,-1,0,0,-1),(0,0,0,0,0), (0

41、,-1,0,0,0), (-1,0,0,-1,0);迷宫数组fangxiang:array 1.4,1.2 of -1.1=(1,0),(0,1),(-1,0),(0,-1);方向增量数组type node=record lastx:integer; 上一位置坐标 lasty:integer; nowx:integer; 当前位置坐标 nowy:integer; pre:byte; 本结点由哪一步扩展而来 dep:byte; 本结点是走到第几步产生的 end;var lujing:array1.25 of node; 记录走法数组 closed,open,x,y,r:integer;procedure output;var i,j:integer;begin for i:=1 to 5 do begin for j:=1 to 5 do write(migongi,j:4); writeln;end; i:=open; repeat wit