数学与程序设计(6)

数学与程序设计 章维铣

maxn=10000; maxm=500; base=10; Type

bignum=array[0..maxm]of integer; Var

s:array[0..1,0..maxn]of bignum; n,m:longint;

Procedure work(var z,x,y:bignum;a,b:longint); var

i,j,k,max:longint; begin

if x[0]>y[0] then max:=x[0] else max:=y[0]; k:=0;

for i:=1 to max do begin

if i<=x[0] then inc(k,x[i]*a); if i<=y[0] then inc(k,y[i]*b); z[i]:=k mod base; k:=k div base; end;

while k>0 do begin

inc(max);

z[max]:=k mod base; k:=k div base; end;

z[0]:=max; end;

Procedure main; var

i,j,k,l:longint; begin

readln(n,m);

fillchar(s,sizeof(s),0); s[0,1,0]:=1;s[0,1,1]:=1; k:=0;

for i:=2 to n do begin

l:=1-k; s[l,0,0]:=0; for j:=1 to m do

work(s[l,j],s[k,j],s[k,j-1],j,2*i-j); k:=l;

第 26 页 共 29 页

数学与程序设计 章维铣

end;

if s[k,m,0]=0 then writeln(0) else begin

for i:=s[k,m,0] downto 1 do write(s[k,m,i]); writeln; end; end; Begin

assign(input,infile);reset(input);

assign(output,oufile);rewrite(output); main;

close(input); close(output); End.

题4 堆塔问题

【问题描述】 设有n个边长为1的正立方体，在一个宽为1的轨道上堆塔，但塔本身不能分离。例如：

n=1时，只有1种方案 □

n=2时 有2种方案

堆塔的规则为底层必须有支撑，下面的堆法是不合法的。

程序要求:输入n(n<=40),求出 ① 总共有多少种不同的方案

② 堆成每层的方案数是多少,例如n=6时,堆成1层的方案数为1,??，堆成6层的方案数为1??

【算法提示】

问题①要求n个边长为1的正立方体总共有多少种不同的堆塔方案，首先考虑将n个边长为1的正立方体排成k(1<=k<=n)列的情况，每列的个数依次为x1,x2,??,xk，则x1+x2+??+xk=n，这里按题目要求x1,x2,??,xk必须为正整数，该方程的解的总数有C(n-1,k-1)，堆

n

塔方案总数为C(n-1,0)+C(n-1,1)+??+C(n-1,n-1)=2。

关于问题②，可以这样考虑，将n个立方体的第一列去掉的话，则成为一个比n小的堆塔问题，这样问题②就可以用递推的方法来解。具体方法是从1到n依次求出堆成各层的方案数，设f(n,k)为堆成k层的方案数，则递推公式为：

f(n,k)??f(n?i,k)??f(n?k,i)

i?1i?1k?1k由于n最大可达到40，所以堆塔的总方案数超过了长整形数的范围，程序采用了高精

第 27 页 共 29 页

数学与程序设计 章维铣

度加法运算。

【参考程序】 Program tuita；

const maxn=40； maxlen=maxn div 3；

type arraytype=array[0..maxlen] of integer； var i,j,k,n,nn:longint； total:arraytype；

f:array [0..maxn,0..maxn] of arraytype；

procedure add(var a:arraytype；b:arraytype)； var i:longint； begin

for i:=0 to maxlen do a[i]:=a[i]+b[i]； for i:=0 to maxlen-1 do if a[i]>=10 then begin

a[i+1]:=a[i+1]+1； a[i]:=a[i]-10 end end；

procedure print(a:arraytype)； var i,j:longint； begin

i:=maxlen；

while (i>0) and (a[i]=0) do i:=i-1； for j:=i downto 0 do write(a[j]) end；

begin {main}

write('Input n:')； readln(n)；

for i:=1 to maxlen do total[i]:=0； total[0]:=1；

for i:=1 to n-1 do add(total,total)； for i:=1 to maxn do for j:=1 to maxn do

for k:=0 to maxlen do f[i,j,k]:=0； for i:=1 to maxn do f[i,1,0]:=1； for i:=1 to maxn do f[i,i,0]:=1； for nn:=2 to n do

for k:=2 to nn-1 do begin

第 28 页 共 29 页

数学与程序设计 章维铣

for i:=1 to k-1 do add(f[nn,k],f[nn-i,k])； for i:=1 to k do

if nn-k>=i then add(f[nn,k],f[nn-k,i]) end；

write('Total=')； print(total)； writeln；

for k:=1 to n do begin

write('Height=',k:2,'Kind=':10)； print(f[n,k])； writeln； if k mod 23=0 then begin

write('Press to continue!')； readln end end；

write('Press to continue!')； readln end.

第 29 页 共 29 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学与程序设计(6)在线全文阅读。