20分(每空4分)
装球:设有n个盒子(n足够大,可装入任何数量的球),分别编号1,2,……。同时有k个小球(k>0),今将k 个小球装入到盒子中去。
装入规则如下:
(1) 第一个盒子不能为空。
(2) 装入必须严格按递增顺序进行。
例如,当k=8,n=6时,装入方法有1,2,5或1,3,4
(3) 在满足上面的两个条件下,要求有球的盒子尽可能多。
(4) 装完后,相邻盒子中球个数差的绝对值之和最小(未装的盒子不计)。
如上例中:
装入法1,2,5,则差的绝对值之和为2-1+5-2=4
装入法1,3,4,则差的绝对值之和为3-1+4-3=3
[程序要求] 给出k(k表示小球的个数)之后,求出满足上述四个条件的装入方法。
[算法描述] 设计一个数组A用数组元素代表盒子,然后依次装入小球。
[程序清单]
CONST N=20;
VAR I,J,K,L:INTEGER;
A:ARRAY[1..N] OF INTEGER;
BEGIN
READLN(K);
A[0]:=0; ;
J:=1;
WHILE K>A[J-I] DO BEGIN
A[J]:=J; K:=K-J ; J:=J+1
END;
L:=J-1;
WHILE K>0 DO BEGIN
A[L]:=A[L]+1 ;
K:=K-1;
L:=L-1;
END;
FOR I:=1 TO J-1 DO
WRITE(A[I]:4)
END.