pascal-搜索回溯.doc

杭十五中信息学奥赛算法设计（4）【题目】求集合元素问题（1,2x+1,3X+1类)某集合中的元素有以下特征：(1)数1是A中的元素(2)如果X是A中的元素,则2x+1,3x+1也是A中的元素(3)除了条件(1),(2)以外的所有元素均不是A中的元素参考程序1uses crt,dos;var a:array1.10000of longint; b:array1.10000of boolean; times,n,m,long,i:longint; hour1,minute1,second1,sec1001:word; hour2,minute2,second2,sec1002:word;begin write(N=);readln(n); gettime(hour1,minute1,second1,sec1001); times:=minute1*60+second1; writeln(minute1,:,second1); fillchar(b,sizeof(b),0); a1:=1;m:=2;long:=1; while longak then begin ak+1:=y;j:=j+1; end else for l:=k+1 to j do al:=al+1; j:=j+1; aj:=3*ai+1; inc(i); until k=n; for i:=1 to n do begin write(ai, ); if (i mod 10 =0 ) or (i=n) then writeln end;end.参考程序3uses crt;var a:array1.10000of longint; n,i,one,another,long,s,x,y:longint;begin write(n=);readln(n); a1:=1;long:=1;one:=1;another:=1; while longy then begin s:=y;inc(another);end else begin s:=x;inc(one);inc(another);end; inc(long);along:=s; end; for i:=1 to n do write(ai, );end.参考程序4var n:integer; top,x:longint;function init(x:longint):boolean;begin if x=1 then init:=true else if(x-1)mod 2=0)and(init(x-1)div 2) or(x-1)mod 3=0)and(init(x-1)div 3)then init:=true else init:=false;end;begin write(input n:); readln(n); x:=0; top:=0; while top n do begin x:=x+1; if init(x) then top:=top+1; write(x:8); end; write(output end.); readlnend.问题描述用高精度计算出S=1!+2!+3!+.n!(n=50)其中!表示阶乘,例如:5!=5*4*3*2*1要求：输入正整数N,输出计算结果S四、搜索回溯法搜索回溯法是程序设计中最常用的一种算法，其思想方法是按一定的顺序对每阶段试探所有可能性：即从初始态出发向前搜索，如果成功则继续，否则回退一步，如此反复直至所有可能都试遍。在搜索过程中，须作标志以记住已搜索过的步骤，设栈实现回溯。算法框架 、初始化 、进行第一步搜索(试探) 、判断搜索是否成功，若成功转; 若不成功，则继续 、进行该步下一种情况搜索，若该步所有可能都搜索完则转；否则转 、当前情况步数等作标志(进栈)，并前进一步、判断是否搜索到终点，不是则转；否则继续。 、打印结果， 清除并转 、退后一步（回溯） 、判断是否退回到初始态，不是则转；是则结果程序 一、素数环把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。 算法分析从1开始，每个空位有20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。1、数据初始化；2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；program tt;var a:array 1.20 of integer; k:integer;function pd1(j,i:integer):boolean;begin pd1:=true; for k:=1 to i-1 do if ak=j then begin pd1:=false;exit;end;end;function pd2(x:integer):boolean;begin pd2:=true; for k:=2 to trunc(sqrt(x) do if x mod k=0 then begin pd2:=false; exit;end;end;function pd3(j,i:integer):boolean;begin if i20 then pd3:=pd2(j+ai-1) else pd3:=pd2(j+ai-1) and pd2(j+1);end;procedure print;begin for k:=1 to 20 do write(ak:4); writeln;end;procedure try(i:integer);var j:integer;begin for j:=2 to 20 do begin if pd1(j,i) and pd3(j,i) then begin ai:=j; if i=20 then begin print; halt;end else try(i+1); ai:=0; end; end;end;begin for k:=1 to 20 do ak:=0; a1:=1; try(2);end.二、编写程序走左图所示的迷宫，要求从走到，并印出路径，在走迷宫的过程中，若遇到死胡同，退出时即给堵上。 算法分析:将每一格对应每一步，每走一步计算相应的坐标值，每一步又按1、2、3、4四个方向进行试探，是否有路，若有路则前进，否则换方向继续试探；若四个方向都不行，则回溯，并将此路堵上。三、八皇后问题 在一个的棋盘里放置个皇后，要求每个皇后两两之间不相冲（在每一横列竖列斜列只有一个皇后）。问题分析主要解决以下几个问题： 1、冲突。包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行摆上皇后，则同一行上不能再放皇后，把I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构。（1）解数组A。AI表示第I个皇后放置的列；范围：1.8（2）行冲突标记数组B。BI=0表示第I行空闲；BI=1表示第I行被占领；范围：1.8（3）对角线冲突标记数组C、D。CI-J=0表示第（I-J）条对角线空闲；CI-J=1表示第（I-J）条对角线被占领；范围：-7.7DI+J=0表示第（I+J）条对角线空闲；DI+J=1表示第（I+J）条对角线被占领；范围：2.16算法流程、数据初始化。、从n列开始摆放第n个皇后，先测试当前位置(n,m)是否等于（未被占领）:如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来)，接着进行递归；如果不是，测试下一个位置(n,m+1)，若当n8时，便一一打印出结果。皇后 N45678910方案数21044092352724program queen; 八皇后问题程序const n=8;var a,b:array1.n of integer;数组a存放解：ai表示第i个皇后放在第ai列； c:array 1-n,n-1 of integer; d:array 2.n+n of integer; b为行标志，c、d表示对角线标志 k:integer;procedure print;打印结果var j:integer;begin for j:=1 to n do write(aj:4); writeln;end;procedrue try(i:integer); 递归搜索解var j:integer;每个皇后的可放置位置。注意：一定要在过程中定义；否则当递归时会覆盖掉它的值，不能得到正确结果begin for j:=1 to n do begin if (bj=0) and (ci-j=0) and (di+j=0) then检查位置是否合法 begin ai:=j;置第i个皇后的位置是第j行 bj:=1; ci-j:=1;di+j:=1; 作已摆放标志 if ij时，则进行将h赋值为i，将要处理的数字赋值为加号后的数值，并将x3赋值为x3-x2，作为加号前的数值；当x3j时，而且ie时，则将h赋值为h-1，i赋值为h+1，在当前处理的数字添加号的数位的前一位添上加号，并将x3赋值为x3-x2-ai。3、当he、ie、x3j时，则退出循环并打印结果“no”；当0h=e、0i=e、x3=j时，则退出循环并打印结果“yes”。 参考程序 program aa;var a,b:text; c:string; d,e,g,h,i,x1,x2,x3,xx:integer; f:array 1.100 of integer;procedure bb;begin assign(a,tjh.dat); reset(a); readln(a,c,d); close(a);end;procedure cc;begin for e:=1 to length(c) do fe:=ord(ce)-48; x1:=0; x2:=0; x3:=0; xx:=1; h:=1; i:=1; while x3d do begin for g:=h to i do x1:=x1*10+fg; for g:=i+1 to e do x2:=x2*10+fg; x3:=x1+x2+x3; if x3=d then exit; if (h0) or (i0) then begin xx:=0; exit; end; if x3d then begin h:=h+1; i:=h; x1:=0; x3:=x3-x2; x2:=0; end; end;end;procedure dd;begin assign(b,tjh.out); rewrite(b); if xx=1 then writeln(b,yes) else writeln(b,no); close(b);end;begin bb; cc; dd;end.习题2、骑士游历问题 设有一个NM的棋盘（2N50，2M50），如图所示。在棋盘上任一点有一个中国象棋马，马走的规则：（1）马走日字；（2）马只能向右走；问题：当N，M输入之后，找出一条从左下角到右上角的路径。如：输入N4，M4。输出（1，1）（2，3）（4，4），若不存在路径，则输出NO。3、任何大于1的自然数N都可以拆分成若干个小于N的自然数之和。输入N，计算和输出N的不同拆分方案。 4、有一集合,集合中有N个元素,每个元素都是正整数,它们存放在一维数组中,每个数组元素存放一个数,对给定的整数TOTAL(设集合中的每个元素的值都小于TOTAL),求出所有满足下列条件的子集,子集中各元素之和等于TOTAL。(如设:TOTAL=10,N=7,元素8,4,1,2,5,3,6)5、有一个由数字1，2，3,9组成的数字串(长度不超过200),问如何将M(M=20)个加号(+)插入到这个数字串中,使所形成的算术表达式的值最小.请编一程序解决这个问题.注意:加号不能加在数字串的最前面或最末尾,也不应有两个或两个以上的另号相邻.M保证小于数字串的长度.例如:数字串798446,若需要加入两个加号,则最佳方案为79+84+46,算术表达式的值为133 程序如下： 程序中T数组用来存放子集TOTAL = 10: N = 7FOR I = 1 TO 7: READ A(I): NEXTDATA 8,4,1,2,5,3,7S= 0: I = 0 以上初始化60 : I = I + 1 往前搜索指针I加1 J = J + 1: T(J) = I 元素编号,送入T数组 S = S + A(I) IF S TOTAL THEN 120 IF S = TOTAL THEN 200110 S = S - A(I): J = J - 1 回退120 IF I N THEN 60I = T(J) 重新设置搜索指针 IF I = N AND J = 1 THEN END150 GOTO 110200 FOR K = 1 TO J: PRINT A(T(K); : NEXT K: PRINT : GOTO 110 【题目】棋盘上每行每列各摆颗棋子, 要求每一行,每一列上只能放置2个有多少种摆法程序 10 DIM a(6), b(6) 20 FOR i = 1 TO 6: READ a(i), b(i): NEXT i 30 DATA 1,2,1,3,1,4,2,3,2,4,3,4 40 i = 0 50 i = i + 1: t(i) = 0 60 t(i) = t(i) + 1 70 IF t(i) = 6 THEN 110 80 i = i - 1 90 IF i 2 OR y(b(x) 2 THEN GOTO 200 130 IF i 4 THEN 50 135 m = m + 1 140 FOR j = 1 TO 4: PRINT TAB(a(t(j); *; TAB(b(t(j); *; : NEXT j200 x = t(i): y(a(x) = y(a(x) - 1: y(b(x) = y(b(x) - 1: GOTO 60 【题目】 在44的棋盘上放置8个棋,要求每一行,每一列上只能放置2个.【参考程序1】算法:8个棋子,填8次.深度为8.注意判断是否能放棋子时,两个两个为一行.var a:array1.8 of 0.4; line,bz:array1.4 of 0.2; line数组:每行已放多少个的计数器 bz数组: 每列已放多少个的计数器 total:integer;procedure output; 输出var i:integer;begin inc(total); write(total,: ); for i:=1 to 8 do write(ai); writeln;end;function ok(dep,i:integer):boolean;begin ok:=true; if dep mod 2 =0 then 假如是某一行的第2个,其位置必定要在第1个之后 if (i=adep-1) then ok:=false; if (bzi=2) or(linedep div 2=2) then ok:=false; 某行或某列已放满2个end;procedure find(dep:integer);var i:integer;begin for i:=1 to 4 do begin if ok(dep,i) then begin adep:=i; 放在dep行i列 inc(bzi); 某一列记数器加1 inc(linedep div 2); 某一行记数器加1 if dep=8 then output else find(dep+1); dec(bzi); 回溯 dec(linedep div 2); adep:=0; end; end;end;begin total:=0; fillchar(a,sizeof(a),0); fillchar(bz,sizeof(bz),0); find(1);end.【参考程序2】算法:某一行的放法可能性是(1,2格),(1,3格),(1,4格).共6种放法constfa:array1.6 of array1.2of 1.4=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4);六种可能放法的行坐标var a:array1.8 of 0.4; bz:array1.4 of 0.2; 列放了多少个的记数器 total:integer;procedure output;var i:integer;begin inc(total); write(total,: ); for i:=1 to 8 do write(ai); writeln;end;function ok(dep,i:integer):boolean;begin ok:=true; 判断现在的放法中,相应的两列是否已放够2个 if (bzfai,1=2) or (bzfai,2=2) then ok:=false;end;procedure find(dep:integer);var i:integer;begin for i:=1 to 6 do begin 共有6种可能放法 if ok(dep,i) then begin a(dep-1)*2+1:=fai,1;一次连续放置2个 a(dep-1)*2+2:=fai,2; inc(bzfai,1); 相应的两列,记数器均加1 inc(bzfai,2); if dep=4 then output else find(dep+1); dec(bzfai,1); 回溯 dec(bzfai,2); a(dep-1)*2+1:=0; a(dep-1)*2+2:=0; end; end;end;begin total:=0;fillchar(a,sizeof(a),0); fillchar(bz,sizeof(bz),0); find(1);end.3、字母组合 ：求A-Z任取N个的所有组