回溯算法完善程序练习题

回溯算法完善程序练习题 【题1：围棋子的移动】有N对黑白棋子并排在一起,如：○○○○○○○○●●●●●●●●,(N=8)。移动规则：移动相邻两个棋子至空位，移动是必须跳过若干个棋子。移动N次后变成黑白相间：○●○●○●○●○●○●○●○●. 输入n，输出样子移动方案和移动步数。 分析：n=4开始看，初始时：

○○○○●●●● 第1步：○○○——●●●○●（—表示空位） 48+1 第2步：○○○●○●●——● 84 第3步：○——●○●●○○● 28 第4步：○●○●○●——○● 72 第5步：——○●○●○●○● 17 n=5时，初始时： ○○○○○●●●●● 第1步：○○○○——●●●●○● 第2步：○○○○●●●●——○● 这样，n=5的问题就转化成了n=4的情况。 n=6时，是不是可以转换为5的问题？ „„， 以此类推，对于一个规模为n的问题，可以把它转化成了规模为n-1的子问题。并且最终都将可以使其转换成为n=4的情况，因而n=4是边界重点特别处理的情况。 数据结构如下：数组b[1..maxn]用来作为棋子移动的场所，初始时，c[1]~c[n]存放白子，c[n+1]~c[2n]存放黑子，c[2n+1]，c[2n+2]为空位置。最后结果在c[3]~c[2n+2]中。pt用来指向移动点的位置 const maxn=1000; var b:array[1..maxn]of char; pt,i,n,num:integer; procedure print; var i:integer; begin ___________________; write('step',num:2,':'); for i:=1 to 2*(n+1) do write(b[i]); writeln; end; procedure move(k:integer); var i:integer; begin

pt:=k; print; end; procedure mv(n:integer); begin if _________then begin move(4); move(8); move(2); move(7); move(1); end else begin move(n); move(2*n-1); print； _________________; end; end; begin readln(n); for i:=1 to n do b[i]:='o'; for i:=n+1 to 2*n do b[i]:='*'; b[2*n+1]:='-'; b[2*n+2]:='-'; pt:=2*n+1; num:=__________; print; mv(n); end. 【题2：特殊错位探索】 部分元素在自然位，部分元素错位的排列问题，往往加上一些特定的限制错位条件。 例如，在1—n的全排列中，展示偶数在其自然位而奇数全错位的所有排列。 var n:integer; a:array[1..10] of integer; b:array[1..10] of boolean; ｛记录数字是否可用｝ procedure try(t:integer); var i:integer; begin if (t > n -1) then begin ｛输出解｝ for i:=1 to n do write(a[i]); writeln; exit; end; else for i:=1 to trunk(n/2+0.6) do if _______________ then begin a[t]:=i*2-1; b[i*2-1]:=true; try(t+2); b[i*2-1]:=false; end; end;{try} begin readln(n); fillchar(b,sizeof(b),false); for i:=1 to n div 2 do begin b[i*2]:=true; a[i*2]:=i*2;;end; try(1); end. 程序运行示例 输入：9 321476985 321496587 325416987 325476981 325496187 327416985 327496185 327496581 329416587 329476185 329476581 521436987 521476983 521496387 527416983 527436981 527496183 527496381 529416387 529436187 529476183 529476381 721436985 721496385 721496583 725416983 725436981 725496183 725496381 729416385 729416583 729436185 729436581 921436587 921476385 921476583 925416387 925436187 925476183 925476381 927416385 927416583 927436185 927436581 s=44 考察输出的解，所有偶数都在自然位，所有奇数都错位。 【题3：伯努利装错信封问题】 某人写了n封信，写了这n封信对应的n个信封。把所有的信都装错了信封的情况，共有多少种？ 这是组合数学中有名的错位问题。著名数学家伯努利（Bernoulli）曾最先考虑此题。后来，欧拉对此题产生了兴趣，称此题是“组合理论的一个妙题”，独立地解出了此题。 【分析】为叙述方便，把某一元素在自己相应位置（如“2”在第2个位置）称为在自然位；某一元素不在自己相应位置称为错位。 事实上，所有全排列分为三类： 1） 所有元素都在自然位，实际上只有一个排列。当n=5时，即12345。 2） 所有元素都错位。当n=5时，如24513。 3） 部分元素在自然位，部分元素错位。当n=5时，如21354。 装错信封问题求解实际上是求n个元素全排列中的“每一元素都错位”子集。 当n=2时显然只有一个解：21（“2”不在第2个位置且“1”不在第1个位置）。 当n=3时，有231，312两个解。 一般地，可在实现排列程序设计中加上“限制取位”的条件：x[i]<>i, 每个x[i]互不相等 （3） 运行示例 输入：4 2143 2341 2413 3142 3412 3421 4123 4312 4321 S=9 输入：5 21453 21534 23154 23451 23514 24153 24513 24531 25134 25413 25431 31254 31452 31524 34152 34251 34512 34521 35124 35214 35412 35421 41253 41523 41532 43152 43251 43512 43521 45123 45132 45213 45231 51234 51423 51432 53124 53214 53412 53421 54123 54132 54213 54231 s=44 输入n=6，即得265个6位错位排列，也是上面所提竞赛题的解。 Var x:array[0..100] of integer; A:array[0..100] of boolean; N,s:integer; procedure try(k:integer); var j,i:integer; begin if _______ then begin for i:=1 to n do write(x[i])； write(‘ ‘);________;exit；end else for j:=1 to n do if (a[j]=true)and ______________________ then begin x[k]:=j; a[j]:=false; try(k+1) ______________________ end; end; begin fillchar(a,sizeof(a),true)；s:=0; readln(n); try(1); writeln;write(s) readln; end.

【题4：数字排列】 在一个N*N的棋盘上（1<=n<=10),填入1,2,...,n*n共n*n个数，使得任意两个相临的数之合为素数 例如： n=2 时，有: 1 2 4 3 n=4 1 2 11 12 16 15 8 5 13 4 9 14 6 7 10 3 var i,n:integer; a:array[1..20,1..20]of integer; b:array[1..20]of boolean; function su(s:integer):boolean; ｛判质数｝ procedure try(t:integer); var k,j,i,x,y:integer; begin if _________ then begin for k:=1 to n do begin for j:=1 to n do write(a[k,j]:3); writeln; end; __________; end else for i:=1 to n*n do if (b[i]=true) then begin x:=(t-1) div n+1;_________________________; a[x,y]:=i; if ((x=1) and su(a[1,y]+a[1,y-1])) or ((y=1)and su(a[x,1]+a[x-1,1])) or ((x<>1)and(y<>1) and ____________________________) then begin b[i]:=false; try(t+1); b[i]:=true; end; end; end; begin readln(n); for i:=1 to n*n do ____________; a[1,1]:=1;b[1]:=false;try(2); end.