6回溯算法2

回溯算法2： 回溯算法2： 例5、n皇后问题（名题）。据说国王有n个皇后，为了减少皇后之间的矛盾，聪明的国王将御花园分割为n*n的棋盘格子形，皇后的寓所就在某个棋盘格子上，每个皇后的活动范围是所在格子沿上下左右及对角线的格子上。这样分配这n个皇后，就能使皇后之间活动范围没有交叉和重叠，从而避免了相互接触，减少了不必要的矛盾。试问怎样找出安置皇后寓所的方案，如果方案不唯一，，能否找出全部安置皇后寓所的方案。 问题分析：本问题可以转化为在n*n的格子内放置n个皇后，使得每行、每列以及对角线上都只有一个皇后，既不产生攻击。可以采用回溯的办法沿着行或列的顺次放置皇后，然后判断所方位置是否与已经放置的皇后为之产生冲突，即是否在同一行、列或对角线上已经放置了皇后，如果有放弃该位置，选择下一个位置，如果没有，选择该位置，选择下一个皇后，在下一个行内继续试探放置；如果当前行所有位置都访问完毕没有合适的位置可以放置皇后，回溯返回上一行，重新选择位置。本题选择两个一维数组a[n],b[n]（值为1，或为0表示该行，该烈是否已放置了皇后）。 搜索算法： program p6-5; procedure run(k:integer); var I:integer; function att:Boolean; begin att:=false ; for j:=1 to k-1 do if (abs(k-j)=abs(stack[j-]-I)) or (I=stack[j]) then begin att:=true;break; end; end; begin if k:=n+1 then begin inc (total) ;writeln(‘no’,total); for j:=1 to n do write(stack[j]:5); writeln; exit; end; for I:=1 to n do begin stack[k]:=I; if not att then run(k+1) else stack[k]=0; end; 例6、在n*n的棋盘上（1<=n<=10）填入1、2、3、….、n*n，共有n*n个数，使得任意相邻数的和为素数。 输入：n 输出：若有多个解，则需输出第一行、第一列之和均为最小的排列方案；若无解，则输出‘no’。 例如：n=2，有 n=4时，有 问题分析：本问题可看作将数据1..n*n放入n*n的表格中，且要求相邻两个数的和是素数，可以采用回溯的办法实现。问了避免在主程序中多次判断相邻的两个数的和sum是素数，将sum的所有可能得值先求出放到数组中，判断sum是否在该数组中即可。 源程序： program p6; const max=10; type arr=array[1..2*max*max] of boolean; var I,j,k,m,n,x,y:integer; t:arr;a:array[1..max,1..max] of integer; b:array[1..max,1..max] of boolean; function suc(x,y,k:integer):boolean; begin suc:=true; if x>1 then if not (t[a[x-1,y]+k]) then suc:=false; if y>1 then if not (t[a[x,y-1]+k]) then suc:=false; end; procedure print; var x,y:integer; begin for x:=1 to n do begin for y:=1 to n do write(a[x,y]:4); end; end; procedure try(x,y,dep:integer); var k:integer; begin if dep =n*n then begin print;halt;end; else for k:=1 to n*n do if not(h[k]) and suc(x,y,k) then begin a[x,y]:=k;h[k]:=true; if y=n then try(x+1,y,dep+1) else if x=n then try(x,y+1,dep+1); else if xn then max:=sum,b:=a; if max=n*(2n-1) then begin for r:=1 to n do begin for s:=1 to n do write(b[r,s]:5);writeln;end; halt; end; exit; end; for k:=1 to N*n div 2 do begin if (odd(i) xor odd(j)) then k1:=2k else k1:=2k-1; if not p[k1] then begin a[I,j]:=k1;p[k1]:=true; if I:=1 then begin if( (a[I,j]+a[I,j-1]) in su) and (sum+a[I,j]数学

数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划