if b[i] then begin
b[i]:=false; c[k,l]:=i;
try(k-1,1,s-a[i],0,t+abs(p+a[i]-x)); try(k,l+1,s-a[i],p+a[i],t); c[k,l]:=0; b[i]:=true; end; end; end; begin
assign(f,'data.in8'); reset(f);
readln(f,n,m);
for i:=1 to n do read(f,a[i]); close(f);
for i:=1 to n-1 do for j:=i+1 to n do
if a[i]
for i:=1 to n do s:=s+a[i]; y:=s; x:=s/m;
fillchar(b,sizeof(b),true); try(m,1,s,0,0); writeln(y:4:2); end.
三、生日蛋糕
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q= Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数） 输入
有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。 输出
仅一行，是一个正整数S（若无解则S=0）。 样例输入 100 2 样例输出 68
附：圆柱公式 体积V=πR2H 侧面积A’=2πRH 底面积A=πR2
算法分析：
搜索次序：从底层的形状（大小）逐步向上搜；
判合法：是否出界（太大或太小剩余的体积作不出蛋糕来） 展望：剩余体积的最小表面积
程序如下：
var r,h:array[0..21] of integer; n,m,min:integer;
a:array[0..21] of integer; i:integer; f:text;
function tj(k,x,y:integer):longint; var v,i:longint; begin v:=0;
for i:=1 to k-1 do v:=v+(x-i)*(x-i)*(y-i); tj:=v;
end;
procedure try(k,s,v:integer); var x,y:longint; begin
if k<1 then begin
if (v=0)and(s if s+v/(r[k+1]-1)>=min then exit; for x:=r[k+1]-1 downto k do for y:=h[k+1]-1 downto k do if (v-x*x*y>=a[k-1])and(v-x*x*y<=tj(k,x,y)) then begin r[k]:=x; h[k]:=y; if k=m then try(k-1,s+2*x*y+x*x,v-x*x*y) else try(k-1,s+2*x*y,v-x*x*y); end; end; begin assign(f,'cake.005'); reset(f); readln(f,n); readln(f,m); close(f); a[0]:=0; for i:=1 to m do a[i]:=a[i-1]+i*i*i; r[m+1]:=trunc(sqrt((n-a[m])/m)); h[m+1]:=trunc(n/m/m); min:=10000; try(m,0,n); writeln(min); end. 四、求出符合下面条件的5个正整数： （1）5个数之和为23。 （2）从5个数中选取不同的数作加法，可得到1-23中所有的自然数。 算法分析： 以每个数为出发点，搜索它的值。由于5个数是无序的，所以是组合问题。第一个数肯定是1，以后的数按允许重复的组合的方式搜索其值，又由于5个数的总和为23，所以最后 一个数也不用搜，直接算，搜时还需照顾到预留问题。 程序如下： var a:array[1..5] of integer; b:array[0..46] of boolean; procedure try1(k,p:integer); var i:integer; begin b[p]:=true; if k>5 then exit; try1(k+1,p); try1(k+1,p+a[k]); end; procedure try(k,s:integer); var i:integer; begin if k=5 then begin a[k]:=s; fillchar(b,sizeof(b),false); try1(1,0); for i:=1 to 23 do if b[i]=false then exit; writeln(a[1],a[2]:3,a[3]:3,a[4]:3,s:3); exit; end; for i:=a[k-1] to s div (6-k) do begin a[k]:=i; try(k+1,s-i); end; end; begin a[1]:=1; try(2,22); readln; end. 第八次课 宽搜（1） 宽度优先搜索算法的核心是：从初级节点开始，应用算符生成第一层节点，检查目标节点是否是这些后继节点中，若没有，再用产生 式规则将所有的第一层节点逐一扩展，得到第二层节点，并逐一检查第二层中是否包含有目标节点。若没有，再扩展第二层……如此扩展，检查下去，直到发现目标节点为止。 这种搜索次序体现沿层次横向扩展的趋势，叫宽度优先搜索。 宽搜存贮量大，因此需要开大数组来存储。开头、尾两个指针，头指针表示生成时的父结点，尾指针表示当前生成点放的位置。头结点的父结点为0。 想记录父结点，则另开一数组，只记录该结点的父结点。则a[k]的父结点为a[b[k]]； 宽搜的要素： （1） 状态：问题的表示（初始状态、目标状态）； （2） 规则； （3） 判合法； （4） 判重；（如果重复则极影响效率，不判重造成巨大的浪费， 但不影响结果，深搜不判重则影响结果。 （5） 判结果。 1. 8数码问题 （（2，8，3），（1，6，4），（7，0，5））---?（（1，2，3），（8，0，4），（7，6，5）） 程序如下：（宽搜） type node=array[1..3,1..3]of 0..8; const start:node=((2,8,3),(1,6,4),(7,0,5)); goal:node=((1,2,3),(8,0,4),(7,6,5));