大数组合数学算法-ACM.ppt

《大数组合数学算法-ACM.ppt》由会员分享，可在线阅读，更多相关《大数组合数学算法-ACM.ppt（84页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、大大数运算与组合数学数运算与组合数学ACM国际大学生程序设计竞赛主讲：王树林主讲：王树林主讲：王树林主讲：王树林問題問題當有一個很大的整數要運算時,如何算?例如:一個一佰位數的數字.int 最大只能到 232 約十個位數的十進位數字.最簡單的方法最簡單的方法先看大數加法.就是改成手動去算加法,而不是由電腦算.123456789123 +234123467890-寫成電腦程式寫成電腦程式方法一:使用陣列(array)例如:int a100,b100,sum100;然後 sumi=ai+bi+c記住,c 是進位(carry),這邊我們要自行處理.那輸入呢那輸入呢?輸入成字串再把字串分解成陣列中各個

2、元素.需要一個parse字串的副程式.void void parse(charparse(char*s,*s,intint*a)*a)intint i,j i,j;j=j=strlen(sstrlen(s););for(ifor(i=0;i=0;ij;i j;i+)+)aj-1-i=s0-30;aj-1-i=s0-30;void void add(intadd(int*a,*a,intint*b,*b,intint*sum)*sum)intint i,ci,c;c=0;c=0;for(ifor(i=0;i100;i+)=0;i=10)=10)sumisumi=sumi-10;=sumi-10;

3、c=1;c=1;else else c=0;c=0;改進改進array 改成 byte的元素.(省空間)更省?一個元素就可以到255,256才進位.用bool用link list 方式(可以讓輸入的數字更大)其他?減法減法?乘法乘法?除法除法?同樣的原理.大數運算大數運算现将一些关键算法的实现方法描述如下：现将一些关键算法的实现方法描述如下：大数的一些简单计算的算法大数的一些简单计算的算法大数的一些简单计算的算法大数的一些简单计算的算法1 1、大数加法运算的实现算法、大数加法运算的实现算法、大数加法运算的实现算法、大数加法运算的实现算法(1)(1)将将A A、B B按位对齐；按位对齐；(2)(

4、2)低位开始逐位相加；低位开始逐位相加；(3)(3)对结果做进位调整；对结果做进位调整；2 2、大数减法运算实现算法、大数减法运算实现算法、大数减法运算实现算法、大数减法运算实现算法(1)(1)将将A A、B B按位对齐；按位对齐；(2)(2)低位开始逐位相减；低位开始逐位相减；(3)(3)对结果做借位调整；对结果做借位调整；大數運算大數運算 3 3、大数乘法运算实现算法、大数乘法运算实现算法、大数乘法运算实现算法、大数乘法运算实现算法(1)(1)引入引入sum2 sum2、sum1sum1中间过渡量；中间过渡量；(2)(2)在在n n的每一位上处理的每一位上处理mm；(3)(3)通过每一层循

5、环，实现乘法的加法化；通过每一层循环，实现乘法的加法化；(4)(4)对结果做进位调整；对结果做进位调整；4 4、大数除法运算的算法实现、大数除法运算的算法实现、大数除法运算的算法实现、大数除法运算的算法实现(1)(1)引入引入alal来标识来标识a a的长度的长度,blbl来标识来标识b b的长度；的长度；(2)(2)测算测算a a和和b b的长度；的长度；(3)(3)高位开始，对位做减法，并完成借位；高位开始，对位做减法，并完成借位；(4)(4)高位开始逐位计算商高位开始逐位计算商(5)(5)整理商整理商,产生余数产生余数;5 5、大数取模运算的算法实现、大数取模运算的算法实现、大数取模运算

6、的算法实现、大数取模运算的算法实现 在取模运算中用到了上面的除法运算，只需返回余数即可。在取模运算中用到了上面的除法运算，只需返回余数即可。大整数的乘法大整数的乘法ACDBX=Y=例子例子 題意：題意：題意：題意：本題目給三個數字本題目給三個數字t,a,bt,a,b(都比都比21474836472147483647小小)，問，問(tata-1)/(tb-1)/(tb-1)1)是大小於是大小於100100位數或是否為整數，若小於位數或是否為整數，若小於100100位數，就印該值。位數，就印該值。題意範例：題意範例：題意範例：題意範例：Sample InputSample Input 2 9 32

7、 9 3 2 3 22 3 2 21 42 721 42 7 123 911 1123 911 1 Sample OutputSample Output(29-1)/(23-1)73(29-1)/(23-1)73(23-1)/(22-1)is not an integer with less than 100 digits.(23-1)/(22-1)is not an integer with less than 100 digits.(2142-1)/(217-1)18952884496956715554550978627384117011154680106(2142-1)/(217-1)1

8、8952884496956715554550978627384117011154680106(123911-1)/(1231-1)is not an integer with less than 100 digits.(123911-1)/(1231-1)is not an integer with less than 100 digits.例子例子 解法：解法：解法：解法：1 1）t=1t=1 Its easy to see that its answer isnt a integer Its easy to see that its answer isnt a integer with l

9、ess than 100 digits.with less than 100 digits.2 2）a=ba=b Its easy to see that its answer is 1.Its easy to see that its answer is 1.3 3）if(aif(a%b!=0)%b!=0)Its answer isnt a integer with less Its answer isnt a integer with less than 100 digits.than 100 digits.証明：証明：令令(tata-1)/(tb-1)=n,n-1)/(tb-1)=n,n

10、是整數，証明是整數，証明a%ba%b=0=0(tata-1)/(-1)/(tbtb-1)=-1)=t(a-bt(a-b)+t(a-2b)+t(a-)+t(a-2b)+t(a-3b)+3b)+t(a-nbt(a-nb)因為一定除的進因為一定除的進(這是我們的假設這是我們的假設)，所以，所以a-a-nbnb=0,=0,a%ba%b=0=0 p-q,-q-p,p-q,-q-p,a%ba%b!=0,!=0,就不會是整數。就不會是整數。例子例子 令令x=x=tbtb,a/b=y,y,a/b=y,y是正整數，是正整數，(tata-1)/(tb-1)=(xy-1)/(tb-1)=(xy-1)/(x-1)1)

11、/(x-1)(xy-1)/(x-1)=x(y-1)+x(y-2)+x(y-3)+.+x0(xy-1)/(x-1)=x(y-1)+x(y-2)+x(y-3)+.+x0 x(y-1)x(y-2)+x(y-3)+.+x0 x(y-1)x(y-2)+x(y-3)+.+x0 x(y-1)x(y-1)加上加上 x(y-2)+x(y-3)+.+x0 x(y-2)+x(y-3)+.+x0 最多進一位數。最多進一位數。Log10(x(y-1)=log10(t(a-b)=(a-b)*log10(t)Log10(x(y-1)=log10(t(a-b)=(a-b)*log10(t)if(a-bif(a-b)*log1

12、0(t)=99),)*log10(t)=99),就一定會大於就一定會大於100100位數位數 若沒有大於若沒有大於100100位數，有可能等於位數，有可能等於100100位數，所以要算位數，所以要算出來。出來。5 5、(xy-1)/(x-1)=x(y-1)+x(y-2)+x(y-3)+.+x0(xy-1)/(x-1)=x(y-1)+x(y-2)+x(y-3)+.+x0 將這個值算出來將這個值算出來.例子例子討論：討論：這題目一定要先判斷位數，如果大於100位就不用算了，不然會超過時間，且要用比較好的方法算真正的值，若用大數除法，會太慢，所以改成(xy-1)/(x-1)=x(y-1)+x(y-2

13、)+x(y-3)+.+x0，這樣的方式來算，比較快!随机产生一个随机产生一个200位的数位的数 intint random(intrandom(int p201)/p201)/随机产生一个随机产生一个200200位的数位的数 p1=1;/p1=1;/低位低位1 1为保证该素数为奇数为保证该素数为奇数 intint i;i;for(i=2;i=200;i+)for(i=2;i=200;i+)pipi=rand()*10/RAND_MAX;=rand()*10/RAND_MAX;while(p200=0)/while(p200=0)/高位不能为高位不能为0 0，保证素数，保证素数达到要求的长度达到

14、要求的长度 p200=rand()*10/RAND_MAX;p200=rand()*10/RAND_MAX;return 0;return 0;乘法运算乘法运算 intint multiply(intmultiply(int m101,int n201,int product301)/m101,int n201,int product301)/两因子两因子m m、n n，乘积，乘积productproduct intint sum1102,sum2102,i,j,k,s;/sum2 sum1102,sum2102,i,j,k,s;/sum2、sum1sum1中间过渡量中间过渡量 for(i=1

15、;i=101;i+)sum2i=0;/sum2for(i=1;i=101;i+)sum2i=0;/sum2所有位置零所有位置零 for(j=1;j201;j+)/for(j=1;j201;j+)/在在n n的每一位上处理的每一位上处理mm for(ifor(i=1;i=101;i+)sum1i=0;/sum1=1;i=101;i+)sum1i=0;/sum1所有位置零所有位置零 for(i=1;i=for(i=1;i=nj;inj;i+)/+)/通过每一层循环，实现乘法的加法化通过每一层循环，实现乘法的加法化 for(s=1;s101;s+)for(s=1;s101;s+)sum2s=ms+s

16、um1s;sum2s=ms+sum1s;for(k=1;k=101;k+)for(k=1;k=101;k+)sum1k=sum2k;sum1k=sum2k;for(k=for(k=j;kj;k=100+j;k+)=100+j;k+)productkproductk=sum2k-j+1+productk;/=sum2k-j+1+productk;/即是实现了乘法过程中的加法即是实现了乘法过程中的加法 for(i=1;i301;i+)/for(i=1;i =300;i abab;i-);i-)if(aiif(ai!=0)return 1;!=0)return 1;for(ifor(i=0;i bb

17、;i+)=0;i -i bbbbbb-i)-i)result=1;result=1;/a b;/a b;break;break;if(aabif(aab-i -i bbbbbb-i)-i)result=-1;result=-1;/a b;/a b;break;break;return result;return result;除法运算除法运算 void void division(intdivision(int a301,a301,intint b201,b201,intint c301,c301,intint d201)d201)/除法函数，除法函数，300300位除位除200200位位,c

18、,c为商，为商，d d为余数为余数 intint al,al,blbl,t301;/al,t301;/al用来标识用来标识a a的长度的长度,blbl用来标识用来标识b b的长度的长度 intint i,j,al2;i,j,al2;for(ifor(i=0;i 301;i+)=0;i 301;i+)cici=0;/=0;/商置零商置零 if(iif(i 202)0;i-)/=300;i 0;i-)/测算测算a a的长度的长度 if(aiif(ai!=0)!=0)al=i;al=i;break;break;for(ifor(i=200;i 0;i-)/=200;i 0;i-)/测算测算b b的长

19、度的长度 if(biif(bi!=0)!=0)blbl=i;=i;break;break;除法运算（续）除法运算（续）al2=al;al2=al;for(ifor(i=0;i al-=0;i al-blbl+1;i+)/+1;i+)/高位开始高位开始 while(cmp(twhile(cmp(t,al2,b,al2,b,blbl)!=-1)/)!=-1)/比较比较a a、b b首位大小首位大小 for(jfor(j=0;j =0;j blbl;j+);j+)tal2-j-=tal2-j-=bblbbl-j;/-j;/对位做减法对位做减法 for(jfor(j=1;j 301;j+)=1;j 3

20、01;j+)if(tjif(tj 0)/0)/完成借位完成借位 tjtj+=10;+=10;tjtj+1-;+1-;calcal-blbl+1-i+;/+1-i+;/高位开始逐位计算商高位开始逐位计算商 al2-;al2-;for(ifor(i=0;i 201;i+)=0;i=1）个元素分成n个组，那么总有一个组至少含有元素个数为m/n。上取整。例子：13个人的小组至少有13/12=2人生日在同一个月。2 Ramsey问题和问题和Ramsey数数用红篮两种颜色去涂n个顶点完全图的边，每边涂且仅涂一种颜色，得到的图叫做2色完全图，记为knRamsey数数用用 表示这样的正整数，即当表示这样的正整

21、数，即当时，任何一个时，任何一个2 2色完全图色完全图k kn n，或者含有红色完或者含有红色完全图全图k kp p，或者含有蓝色完全图，或者含有蓝色完全图k kg g，两者必居，两者必居其一；而当其一；而当 存在存在2 2色完全图色完全图k kn n它它不含红色完全子图不含红色完全子图k kp p和蓝色完全图和蓝色完全图k kg g，这个这个数就称之为数就称之为RamseyRamsey数。数。确定确定RamseyRamsey数是很难的问题。到目前为止，数是很难的问题。到目前为止，主要还是研究主要还是研究 ，精确求得的数值，精确求得的数值为数甚少为数甚少另一种表述另一种表述一对常数一对常数p

22、p和和g g对应一个常数对应一个常数n n，使得，使得n n个人中或个人中或有有p p个人互相认识，或者有个人互相认识，或者有g g个人互相不认识，个人互相不认识，这个这个n n的最小值用的最小值用 表示表示显然显然Ramsey数上界估计公式数上界估计公式下面估计下面估计 的上界的上界 可改进为：可改进为：递归边界递归边界上界估计程序上界估计程序Program ramseyuses crt;Const maxn=50;Type rtype=array1.maxn,1.maxn of integer;Var r:rtype;ramsey数组 a,b :integer;ramsey数的两个参数Pr

23、ocedure init;输入ramsey数的两个参数Begin clrscr;repeat write(a=);readln(a);until(a1)and(a1)and(b=maxn);end;Procedure mainProcedure main varvar I,j:integer;I,j:integer;BeginBegin for i:=2 to a do rI,2:=I;for i:=2 to a do rI,2:=I;建立递归边界建立递归边界 for i:=2 to b do r2,i:=I;for i:=2 to b do r2,i:=I;for i:=3 to a do

24、for i:=3 to a do for j:=3 to b do for j:=3 to b do if(odd(ri-1,j)or(odd(rI,j-1)then if(odd(ri-1,j)or(odd(rI,j-1)then rI,jrI,j:=ri-1,j+rI,j-1:=ri-1,j+rI,j-1 else else rI,jrI,j:=ri-1,j+rI,j-1-1;:=ri-1,j+rI,j-1-1;writeln(R(,a,bwriteln(R(,a,b,)=,)=,ra,bra,b););end;end;BeginBegin init;init;输入参数输入参数a a和和b

25、b main;main;计算和输出计算和输出ramseyramsey数数r r（a a，b b）EndEnd；程序只能估计上界，一些运行结果与精确值有一定误差。要准确计算程序只能估计上界，一些运行结果与精确值有一定误差。要准确计算RamseyRamsey数，数，只要将程序返回的整数值逐一递减。直至递减后的只要将程序返回的整数值逐一递减。直至递减后的n n值所对应的值所对应的knkn图中出现了不图中出现了不含红色完全子图含红色完全子图kpkp或蓝色完全子图或蓝色完全子图kgkg的情形，则的情形，则n+1n+1就是精确的就是精确的RAMSEYRAMSEY数了。数了。排列组合与计数问题排列组合与计数

26、问题 两个基本计数原理两个基本计数原理 加法原理加法原理 乘法原理乘法原理 排列问题排列问题 线排列线排列 从从n n个不同的元素中，取个不同的元素中，取r r个按次序排列，称为从个按次序排列，称为从n n中取中取r r个排个排列，其排列数记为列，其排列数记为P P（n n，r r）圆排列圆排列 从集合从集合S Sa1,a2,ana1,a2,an的的n n个不同元素中，取出个不同元素中，取出r r个元素按照某个元素按照某种次序排成一个圆圈，称这样的排列为圆排列。种次序排成一个圆圈，称这样的排列为圆排列。重排列重排列 无限无限有限重排列 一般地，把r只彩色球放到n个编号不同的盒子中去的方法种数是

27、组合 C（n，r）非重组合 重组合H(n，r)或者C(n+r-1,r)ACM赛题赛题某机要部门安装了电子锁。m个工作人员每人发一张磁卡，卡上有开锁的密码特征。为了确保安全，规定至少要有n个人同时使用各自的磁卡才能将锁打开。现在需要你计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少有几个特征。如果特征的编号以小写英文字符表示，将每个人的磁卡的特征编号打印出来。要求输出的电子锁的总特征数最少。解题分析解题分析题意告诉我们，至少要有题意告诉我们，至少要有n n个人在场并同时使用个人在场并同时使用磁卡才能将锁打开。换言之，任意磁卡才能将锁打开。换言之，任意n n1 1个人在个人在一起，至少缺少

28、一种开锁的密码特征，故不能打一起，至少缺少一种开锁的密码特征，故不能打开电子锁，剩下的开电子锁，剩下的m-(n-1)m-(n-1)个人中的任意一个人个人中的任意一个人到场，就一定能将锁打开。故电子锁至少应有到场，就一定能将锁打开。故电子锁至少应有C C（mm，mmn n1 1）中特征。对于任何一个工作人）中特征。对于任何一个工作人员来说，其余员来说，其余mm1 1个人中任意个人中任意n n1 1个人在场，个人在场，至少缺少一个这个工作人员磁卡上具有的特征而至少缺少一个这个工作人员磁卡上具有的特征而无法打开锁。所以每个人至少要有无法打开锁。所以每个人至少要有C C（m-1,n-m-1,n-1 1

29、）种特征。）种特征。虽然通过组合数学知识是能够求出电子锁的最少总特征数和每个人磁卡的最少特征数。但题目还要求枚举出电子锁的所有特征。并输出m张磁卡。计算出特征数1，2，.,#m 表示工作人员编号a，b等小写字母表示磁卡的特征编号，超过26个，用aa，ba，ca，.表示。m4N2Make(1,0)开始递归母函数母函数二项展开式从组合学角度看，相当于(x+y)(x+y)共n个括号相乘相当于n个无区别的球，放到x，y两个编号不同的盒子中，每个盒子放入的球数不限。二项式定理从二项式展开出发，人们自然会想到研究多项展开式：普通母函数：下式称为序列 ai 的普通母函数1 天平称物问题：设有质量分别为n1克

30、，n2克,，nk克的整数值砝码，欲称i克的物体。物体在左，砝码在右，共有多少中不同的称法？设有ai种方法称i克物体，则a0，a1，,ai，作系数序列的母函数是这是因为每个括号(1+xnj)如提供1，表示nj克砝码没有用上；如果提供xnj，表示nj砝码用上了。右边多项展开式中的每一个xi表示可称出i克物体，其系数便是i克物体的方案数。例子：共有1克，2克，3克，4克的砝码各一枚，问能称出哪几种重量？有几种可能方案？2 允许重复的组合问题 设有几种相异物体。如果允许重复，即每种物体的可取数依次为则从中取 个物体的可重复的组合数 为多少？3 整数拆分整数拆分整数拆分就是把一个整数分解成若干整数的和。

31、不定方程的解，非负整数解的个数 枚举整数拆分枚举整数拆分题目：输入正整数m和k，输出将m拆分成k项整数和的所有方案。由交换律产生的诸个方案算作同一个方案，例如m6，k3时 1236 1326 2136算作1236Program Program IntegersplitingIntegersplitingConst Const maxmmaxm=100;=100;VarVar k,Mk,M:integer;:integer;项数，数和项数，数和 ansans :array1.maxm of integer;:array1.maxm of integer;存储方案存储方案 Total :integ

32、er;Total :integer;拆分数拆分数 Procedure printProcedure print varvar I:integer;I:integer;begin begin inc(totalinc(total););累计拆分数累计拆分数 write(answrite(ans No.,total:4,:);No.,total:4,:);for i:=1 to k-1 do for i:=1 to k-1 do write(ansiwrite(ansi,+);,+);拆分方案拆分方案 writeln(anskwriteln(ansk),=,m),=,m)end;end;Proce

33、dure Solve(step,index,sum:integer);step形成的项数；index第step项的值；sum第1.Step项的和 var i:integerBegin if step=k then 若拆分成k项，且数和为M，则打印拆分方案；若k项的数和不等于M，则执行空语句 if sum=m then print else for i:=index to m do 否则还未拆分第k项。在index.M之间选择某值i，使得前step项的数和加上i后小于等于M If If sum+isum+i=m then=m then begin begin ansstep+1:=I;i ans

34、step+1:=I;i值作为第值作为第stepstep项项 solve(step+1,I,sum+i)solve(step+1,I,sum+i)递归搜索下一项的值递归搜索下一项的值 end end End;End;VarVar i:integeri:integer;BeginBegin repeat repeat write(Mwrite(M=);=);输入数和输入数和MM read(mread(m););until m in 1.maxm;until m in 1.maxm;repeat repeat write(kwrite(k=);=);输入项数输入项数kk read(kread(k);

35、);until k in 1.m;until k in 1.m;total:=0;total:=0;拆分数初始化拆分数初始化 For i:=1 to m div k do 试选1。M，分别作为第一项的值 begin ans1:=i;solve(1,i,i);i作为第1项的值，递归搜索首项为i的所有拆分方案 end;readln;End.End.求普通母函数的系数序列求普通母函数的系数序列如果已经求得普通母函数，可以通过展开多项式的办法确定其系数序列。这个系数序列对研究组合问题有相当重要的意义。下面我们来编写一个程序从一个指定文件中读入普通母函数。文件格式为：每行表示一个多项式，按幂次数递增的顺

36、序输入各项。每项系数在前，指数在后，各项间以空格隔开，每行最后加00，表示一个多项式输入结束。行间的回车表明多项式之间的连乘关系。算法分析算法分析 用单链表P存储普通型母函数的展开式，链结点存储当前项，结点形式为初始时，P为程序清单程序清单Program multiplyProgram multiplyType Type link=node;link=node;指针指针 node noderecord record 项结点项结点 time:integer;time:integer;次幂次幂 a:real;a:real;系数系数；nextnext：link link 指向下项的指针指向下项的指针

37、 end end；VarVar p,rp,r :link;P :link;P存储以前各多项式的展开式；存储以前各多项式的展开式；r r加入当前多项式后展开的结果加入当前多项式后展开的结果 f:text;f:text;输入文件输入文件 Procedure initProcedure init；文件读前准备文件读前准备 VarVar strstr：stringstring；BeginBegin write(Filewrite(File Name=);Name=);readln(strreadln(str););Assign(f,strAssign(f,str););reset(freset(f);

38、);End;End;Procedure free(p:link);释放P链Begin if pnil then begin free(p.next);dispose(p);end;End;Procedure Procedure add(time:integeradd(time:integer;a:real;r:linka:real;r:link););通过合并同类项，将通过合并同类项，将aXaXtimetime链入链入r r链链 VarVar t t：linklink；BeginBegin if if r.nextr.next=nil=nil 若次幂若次幂timetime最大，则最大，则aXa

39、Xtimetime加入加入r r链尾链尾 then begin then begin new(r.nextnew(r.next););r.next.timer.next.time:=time;:=time;r.next.ar.next.a:=a;:=a;r.next.nextr.next.next:=nil;:=nil;end;end;Else if Else if r.next.timer.next.time=time=time 将将aXaXtimetime并入并入r r中次幂为中次幂为timetime的项的项 then then beginbegin r.next.ar.next.a:=:

40、=r.next.a+ar.next.a+a;if if r.next.ar.next.a=0 then begin =0 then begin 删除删除r r中为中为0 0的项的项 t:=t:=r.nextr.next;r.nextr.next:=:=r.next.nextr.next.next;dispose(tdispose(t););end;end;end;end;Else if(Else if(r.next.timer.next.timetime)and(timetime)and(timer.timer.time)若若timetime次幂在次幂在r r的相邻项之的相邻项之间，则在中间插

41、入间，则在中间插入aXaXtimetime then begin then beginNew(t);t.time:=time;t.a:=a;t.next:=r.next;r.next:=t;End;Else add(time,a,r.next)往下递归合并End;Procedure proceed;Procedure proceed;计算若干多项式之积计算若干多项式之积 VarVar time time：integerinteger；a a：realreal；t t：linklink；BeginBegin new new（p p）；）；newnew（p.nextp.next）;中间中间p p链

42、初始化链初始化 p.next.timep.next.time:=0;:=0;p.next.ap.next.a:=1;:=1;p.next.nextp.next.next:=nil;:=nil;read(f,a,timeread(f,a,time););读入第读入第1 1个多项式的首项个多项式的首项 while not while not eof(feof(f)do)do begin begin new(rnew(r););r.nextr.next:=nil;:=nil;展开式初始化展开式初始化 repeat repeat aXaXtimetime乘以乘以p p链上的各项，并合并同类项，结果存入

43、链上的各项，并合并同类项，结果存入r r链链 if a0 then begin if a0 then begin t:=t:=p.nextp.next;while tnil do begin while tnil do begin add(time+t.timeadd(time+t.time,a*,a*t.at.a,r);,r);t:=t:=t.nextt.next;end;end;end;end;read(f,a,timeread(f,a,time)读入当前多项式的下一项读入当前多项式的下一项 until(a=0)or until(a=0)or eof(feof(f););Read(f,a,

44、time);再读下一项 if not eof（f）若当前项不是最后一项，则将当前展开的结果转赋给p，释放以前各多项式的展开式 then begin t:=p；p:=r;free(t);end;End;End;Procedure Procedure print(r:linkprint(r:link););打印结果打印结果 BeginBegin if rnil then begin if rnil then begin write(a,r.timewrite(a,r.time,_,r.a:3:0,);,_,r.a:3:0,);print(r.nextprint(r.next););end;end;End;End;BeginBegin init;init;文件读前准备文件读前准备 proceed;proceed;展开多项式展开多项式 print print（r.nextr.next）;打印展开式各项系数打印展开式各项系数 writelnwriteln；End;End;结束语结束语组合数学中的算法很多，有一定的难度希望大家在掌握组合数学基本概念和基本原理的基础上，适当作一些中等难度的题目。