文档详情

搜索算法个人总结pascal.doc

发布:2018-01-08约2.01万字共26页下载文档
文本预览下载声明
2011.10.17总结 (1-5题为今天重写一次,其下所表示的提交次数为今天重写的提交次数,其他题提交次数为原来的次数,部分不详,题号前加星号表示未AC) 1·N皇后(位运算版) 这个是看了标程后写的,很有意思很巧妙的做法,也很强大,一次wa,是因为没写inc(sum),。 ①(只输出结果数目) program quen; var k,sum,n:longint; procedure dfs(row,l,r:longint); //row:列 l,r:两条对角线 var pos,p:longint; begin if rowk then begin pos:=k and not(l or r or row); //表示需要放皇后的的位子 while pos0 do //有皇后要放 begin p:=pos and(not pos +1); //取最右边的1 //p表示某个可以放上皇后的地方 pos:=pos-p; //放上皇后 dfs(row+p,(l+p)shl 1,(r+p)shr 1 ); //回溯,注意对角线的处理 end ; end else inc(sum); end; begin readln(n); k:=(1 shl n)-1; //每一位都是1,目标状态 dfs(0,0,0); writeln(sum); end. ②(输出前3种方案,tyvj080) program quen{输出前3种解}; var k,sum,n,i,t:longint; a:array[0..14]of longint; procedure dfs(dep,row,l,r:longint); //dep: 层数 row:列 l,r:两条对角线 var pos,p,i:longint; begin if depn then //决策有效 begin inc(sum); if sum=3 then begin for i:=1 to n do write(a[i], ); //输出决策 writeln; end; end else begin for i:=1 to n do //第i位是否可以放皇后 begin p:=(1 shl (i-1)); //二进制决策 pos:=p and (row or l or r); //pos记录冲突 if(pos=0) //没有冲突 then begin a[dep]:=i; //记录决策 dfs(dep+1,row + p,(l+p)shl 1,(r+p)shr 1); //下一层递归 end; end; end end; begin readln(n); k:=(1 shl n)-1; //每一位都是1,目标状态 for i:=1 to n do begin a[1]:=i; //初始化第一行,有n个状态 t:=1 shl(i-1); dfs(2,t,t shl 1,t shr 1); end; writeln(sum); end. 2. 计算细胞数program tyvj1127; var n,m,re:longint; a:array[1..100,1..100]of longint; procedure init ; begin assign(input,tyvj1127.in); assign(output,tyvj1127.out); reset(input); rewrite(output); end; procedure change(i,j:longint); var k,l:longint; begin a[i,j]
显示全部
相似文档