1。问题描述:将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为: P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2 问题求解:求出一种分法,使P为最小(若有多种方案仅记一种〉 程序说明: 数组:a[1],a[2],...A[N]存放原数 s[1],s[2],...,s[K]存放每个部分的和 b[1],b[2],...,b[N]穷举用临时空间 d[1],d[2],...,d[N]存放最佳方案 程序: program exp4; Var i,j,n,k : integer; a :array [1..100] of integer; b,d:array [0..100] of integer; s :array[1..30] of integer; begin readln(n,k); for I:=1 to n do read(a[I]); for I:=0 to n do b[I]:=1; cmin:=1000000; while (b[0]=1) do begin for I:=1 to k do ① for I:=1 to n do ② sum:=0; for I:=1 to k-1 do for j:= ③ sum:=sum+(s[I]-s[j])*(s[I]-s[j]); if ④ then begin cmin:=sum; for I:=1 to n do d[I]:=b[I]; end; j:=n; while ⑤ do j:=j-1; b[j]:=b[j]+1; for I:=j+1 to n do ⑥ end; writeln(cmin); for I:=1 to n do write(d[I]:40); writeln; end. 2.问题描述:有n种基本物质(n≤10),分别记为P1,P2,……,Pn,用n种基本物质构造物品,这些物品使用在k个不同地区(k≤20),每个地区对物品提出自己的要求,这些要求用一个n 位的数表示:α1α2……αn,其中: αi =1表示所需物质中必须有第i种基本物质 =-1表示所需物质中必须不能有第i种基本物质r =0无所谓 问题求解:当k个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些物质不被使用。 程序说明:数组b[1],b[2],...,b[nJ表示某种物品 a[1..k,1..n]记录k个地区对物品的要求,其中: a[I,j]=1表示第i个地区对第j种物品是需要的 a[i,j]=0表示第i个地区对第j种物品是无所谓的 a[i,j]=-1表示第i个地区对第j种物品是不需要的 程序: program gxp2; Var i, j ,k, n :integer; p:boolean; b :array [0..20] of 0..1; a :array[1..20,1..10]d integer; begin readln(n,k); for i:=1 to k do begin for j:=1 to n do read(a[i,j]); readln; end; for i:=O to n do b[i]:=0; p:=true; while ① do begin j:=n; while b[j]=1 do j:=j-1; ② for i:=j+1 to n do b[I]:=0; ③ for i:=1 to k do for j :=1to n do if( a[i,j]=1 ) and (b[j]=0) or ④ then p:=true; end; if ⑤ then writeln('找不到!‘) else for i:=1 to n do if (b[i]=1) then writeln('物质',I,’需要') else writeln('物质',i,'不需要'); end.