大数组合数学算法-ACM

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,大,数运算与组合数学,ACM,国际大学生程序设计竞赛,主讲：王树林,問題,當有一個很大的整數要運算時,如何算,?,例如,:,一個一佰位數的數字,.,int,最大只能到,2,32,約十個位數的十進位數字,.,最簡單的方法,先看大數加法,.,就是改成手動去算加法,而不是由電腦算,.,123456789123,+ 234123467890,-,寫成電腦程式,方法一,:,使用陣列,(array),例如,:,int,a100, b100, sum100;,然後,sumi,=,ai+bi+c,記住, c,是進位,(carry),這邊我們要自行處理,.,那輸入呢,?,輸入成字串,再把字串分解成陣列中各個元素,.,需要一個,parse,字串的副程式,.,void,parse(char,*s,int,*a),int,i,j,;,j=,strlen(s,);,for(i,=0;i,j;i,+),aj-1-i=s0-30;,void,add(int,*a,int,*b,int,*sum),int,i,c,;,c=0;,for(i,=0;i=10),sumi,=sumi-10;,c=1;, else ,c=0;,改進,array,改成,byte,的元素,. (,省空間,),更省,?,一個元素就可以到,255, 256,才進位,.,用,bool,用,link list,方式,(,可以讓輸入的數字更大,),其他,?,減法,?,乘法,?,除法,?,同樣的原理,.,大數運算,现将一些关键算法的实现方法描述如下：,大数的一些简单计算的算法,1,、大数加法运算的实现算法,(1),将,A,、,B,按位对齐；,(2),低位开始逐位相加；,(3),对结果做进位调整；,2,、大数减法运算实现算法,(1),将,A,、,B,按位对齐；,(2),低位开始逐位相减；,(3),对结果做借位调整；,大數運算,3,、大数乘法运算实现算法,(1),引入,sum2,、,sum1,中间过渡量；,(2),在,n,的每一位上处理,m,；,(3),通过每一层循环，实现乘法的加法化；,(4),对结果做进位调整；,4,、大数除法运算的算法实现,(1),引入,al,来标识,a,的长度,bl,来标识,b,的长度；,(2),测算,a,和,b,的长度；,(3),高位开始，对位做减法，并完成借位；,(4),高位开始逐位计算商,(5),整理商,产生余数,;,5,、大数取模运算的算法实现,在取模运算中用到了上面的除法运算，只需返回余数即可。,大整数的乘法,A,C,D,B,X=,Y=,例子,題意：,本題目給三個數字,t,a,b,(,都比,2147483647,小,),，問,(,ta,- 1)/(tb -1),是大小於,100,位數或是否為整數，若小於,100,位數，就印該值。,題意範例：,Sample Input,2 9 3,2 3 2,21 42 7,123 911 1,Sample Output,(29-1)/(23-1) 73,(23-1)/(22-1) is not an integer with less than 100 digits.,(2142-1)/(217-1) 18952884496956715554550978627384117011154680106,(123911-1)/(1231-1) is not an integer with less than 100 digits.,例子,解法：,1,）,t=1,Its easy to see that its answer isnt a integer with less than 100 digits.,2,）,a=b,Its easy to see that its answer is 1.,3,）,if(a,%b != 0),Its answer isnt a integer with less than 100 digits.,証明：,令,(,ta,- 1)/(tb -1) = n, n,是整數，証明,a%b,=0,(,ta,- 1)/ (,tb,- 1) =,t(a-b,) +t(a-2b)+t(a-3b)+,t(a-nb,),因為一定除的進,(,這是我們的假設,),，所以,a-,nb,= 0,a%b,= 0, p-q, -q-p, ,a%b,!=0,就不會是整數。,例子,令,x=,tb, a/b=y, y,是正整數，,(,ta,- 1)/(tb -1) = (xy-1)/(x-1),(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,最多進一位數。,Log10(x(y-1) = log10(t(a-b) = (a-b)*log10(t),if(a-b,)*log10(t) =99),就一定會大於,100,位數,若沒有大於,100,位數，有可能等於,100,位數，所以要算出來。,5,、,(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)+x(y-3)+.+x0,，這樣的方式來算，比較快,!,随机产生一个,200,位的数,int,random(int,p201) /,随机产生一个,200,位的数,p1=1; /,低位,1,为保证该素数为奇数,int,i;,for (i=2;i=200;i+),pi,=rand()*10/RAND_MAX;,while (p200=0) /,高位不能为,0,，保证素数达到要求的长度,p200=rand()*10/RAND_MAX;,return 0;,乘法运算,int,multiply(int,m101,int n201,int product301)/,两因子,m,、,n,，乘积,product,int,sum1102,sum2102,i,j,k,s; / sum2,、,sum1,中间过渡量,for (i=1; i=101;i+)sum2i=0;/ sum2,所有位置零,for (j=1;j201;j+)/,在,n,的每一位上处理,m,for(i,=1;i=101;i+)sum1i=0; /sum1,所有位置零,for (i=1;i=,nj;i,+)/,通过每一层循环，实现乘法的加法化, for (s=1;s101;s+),sum2s=ms+sum1s;,for (k=1;k=101; k+),sum1k=sum2k;,for (k=,j;k,=100+j;k+),productk,=sum2k-j+1+productk;/,即是实现了乘法过程中的加法,for (i=1;i,ab,; i-),if(ai, != 0) return 1;,for(i,= 0; i ,bbb,- i), result = 1; / a b;,break;,if(aab,- i ,bbb,- i), result = -1; / a b;,break;,return result;,除法运算,void,division(int,a301,int,b201,int,c301,int,d201),/,除法函数，,300,位除,200,位,c,为商，,d,为余数,int,al,bl, t301; / al,用来标识,a,的长度,bl,用来标识,b,的长度,int,i, j, al2;,for(i,= 0; i 301; i+),ci, = 0;/,商置零,if(i, 0; i-)/,测算,a,的长度,if(ai, != 0),al = i;,break;,for(i,= 200; i 0; i-)/,测算,b,的长度,if(bi, != 0),bl,= i;,break;,除法运算（续）,al2 = al;,for(i,= 0; i al -,bl,+ 1; i+)/,高位开始,while(cmp(t, al2, b,bl,)!=-1)/,比较,a,、,b,首位大小,for(j,= 0; j ,bl,; j+),tal2 - j -=,bbl,- j;/,对位做减法,for(j,= 1; j 301; j+),if(tj, 0)/,完成借位,tj, += 10;,tj,+ 1-;,cal,-,bl,+ 1 - i+;/,高位开始逐位计算商,al2-;,for(i,= 0; i=1,）个元素分成,n,个组，那么总有一个组至少含有元素个数为,m/n,。上取整。,例子：,13,个人的小组至少有,13/12=2,人生日在同一个月。,2 Ramsey,问题和,Ramsey,数,用红篮两种颜色去涂,n,个顶点完全图的边，每边涂且仅涂一种颜色，得到的图叫做,2,色完全图，记为,k,n,Ramsey,数,用 表示这样的正整数，即当,时，任何一个,2,色完全图,k,n,，,或者含有红色完全图,k,p,，或者含有蓝色完全图,k,g,，两者必居其一；而当 存在,2,色完全图,k,n,它不含红色完全子图,k,p,和蓝色完全图,k,g,，,这个数就称之为,Ramsey,数。,确定,Ramsey,数是很难的问题。到目前为止，主要还是研究 ，精确求得的数值为数甚少,另一种表述,一对常数,p,和,g,对应一个常数,n,，使得,n,个人中或有,p,个人互相认识，或者有,g,个人互相不认识，这个,n,的最小值用 表示,显然,Ramsey,数上界估计公式,下面估计 的上界,可改进为：,递归边界,上界估计程序,Program,ramsey,uses,crt,;,Const,maxn,=50;,Type,rtype,=array1.maxn, 1.maxn of integer;,Var,r:,rtype,; ,ramsey,数组,a, b :integer; ,ramsey,数的两个参数,Procedure init; ,输入,ramsey,数的两个参数,Begin,clrscr,;,repeat,write(a,=);,readln(a,);,until (a1) and (a1) and (b=,maxn,);,end;,Procedure main,var,I, j :integer;,Begin,for i:=2 to a do rI,2:=I; ,建立递归边界,for i:=2 to b do r2,i:=I;,for i:=3 to a do,for j:=3 to b do,if (odd(ri-1,j) or (odd(rI,j-1) then,rI,j,:=ri-1,j+rI,j-1,else,rI,j,:=ri-1,j+rI,j-1-1;,writeln(R(,a,b,)=,ra,b,);,end;,Begin,init; ,输入参数,a,和,b,main; ,计算和输出,ramsey,数,r,（,a,，,b,）,End,；,程序只能估计上界，一些运行结果与精确值有一定误差。要准确计算,Ramsey,数，只要将程序返回的整数值逐一递减。直至递减后的,n,值所对应的,kn,图中出现了不含红色完全子图,kp,或蓝色完全子图,kg,的情形，则,n+1,就是精确的,RAMSEY,数了。,排列组合与计数问题,两个基本计数原理,加法原理,乘法原理,排列问题,线排列 从,n,个不同的元素中，取,r,个按次序排列，称为从,n,中取,r,个排列，其排列数记为,P,（,n,，,r,）,圆排列 从集合,S,a1,a2,an,的,n,个不同元素中，取出,r,个元素按照某种次序排成一个圆圈，称这样的排列为圆排列。,重排列,无限,有限重排列,一般地，把,r,只彩色球放到,n,个编号不同的盒子中去的方法种数是,组合,C,（,n,，,r,）,非重组合,重组合,H(n,，,r),或者,C(n+r-1,r),ACM,赛题,某机要部门安装了电子锁。,m,个工作人员每人发一张磁卡，卡上有开锁的密码特征。为了确保安全，规定至少要有,n,个人同时使用各自的磁卡才能将锁打开。现在需要你计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少有几个特征。如果特征的编号以小写英文字符表示，将每个人的磁卡的特征编号打印出来。要求输出的电子锁的总特征数最少。,解题分析,题意告诉我们，至少要有,n,个人在场并同时使用磁卡才能将锁打开。换言之，任意,n,1,个人在一起，至少缺少一种开锁的密码特征，故不能打开电子锁，剩下的,m-(n-1),个人中的任意一个人到场，就一定能将锁打开。故电子锁至少应有,C,（,m,，,m,n,1,）中特征。对于任何一个工作人员来说，其余,m,1,个人中任意,n,1,个人在场，至少缺少一个这个工作人员磁卡上具有的特征而无法打开锁。所以每个人至少要有,C,（,m-1,n-1,）种特征。,虽然通过组合数学知识是能够求出电子锁的最少总特征数和每个人磁卡的最少特征数。但题目还要求枚举出电子锁的所有特征。并输出,m,张磁卡。,计算出特征数,1,，,2,，,.,#m,表示工作人员编号,a,，,b,等小写字母表示磁卡的特征编号，超过,26,个，用,aa,，,ba,，,ca,，,.,表示。,m,4,N,2,Make(1,0),开始递归,母函数,二项展开式,从组合学角度看，相当于,(,x+y,)(,x+y,),共,n,个括号相乘相当于,n,个无区别的球，放到,x,，,y,两个编号不同的盒子中，每个盒子放入的球数不限。,二项式定理,从二项式展开出发，人们自然会想到研究多项展开式：,普通母函数：下式称为序列,a,i,的普通母函数,1,天平称物问题：设有质量分别为,n1,克，,n2,克,，,nk,克的整数值砝码，欲称,i,克的物体。物体在左，砝码在右，共有多少中不同的称法？,设有,ai,种方法称,i,克物体，则,a0,，,a1,，,ai,，,作系数序列的母函数是,这是因为每个括号,(1+x,nj,),如提供,1,，表示,n,j,克砝码没有用上；如果提供,x,nj,，表示,nj,砝码用上了。右边多项展开式中的每一个,x,i,表示可称出,i,克物体，其系数便是,i,克物体的方案数。,例子：共有,1,克，,2,克，,3,克，,4,克的砝码各一枚，问能称出哪几种重量？有几种可能方案？,2,允许重复的组合问题,设有几种相异物体。如果允许重复，即每种物体的可取数依次为,则从中取 个物体的可重复的组合数 为多少？,3,整数拆分,整数拆分就是把一个整数分解成若干整数的和。,不定方程的解，非负整数解的个数,枚举整数拆分,题目：输入正整数,m,和,k,， 输出将,m,拆分成,k,项整数和的所有方案。,由交换律产生的诸个方案算作同一个方案，例如,m,6,，,k,3,时,1,2,3,6,1,3,2,6,2,1,3,6,算作,1,2,3,6,Program,Integerspliting,Const,maxm,=100;,Var,k,M,: integer; ,项数，数和,ans,: array1.maxm of integer; ,存储方案,Total : integer; ,拆分数,Procedure print,var,I : integer;,begin,inc(total,); ,累计拆分数,write(ans,No., total:4,:);,for i:=1 to k-1 do,write(ansi, +); ,拆分方案,writeln(ansk,), =, m),end;,Procedure,Solve(step,index,sum,: integer);,step,形成的项数；,index,第,step,项的值；,sum,第,1.Step,项的和,var,i: integer,Begin,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,sum+i,time) and (time,r.time,) ,若,time,次幂在,r,的相邻项之间，则在中间插入,aX,time,then begin,New(t,);,t.time,:=time;,t.a,:=a;,t.next,:=,r.next,;,r.next,:=t;,End;,Else,add(time, a,r.next,) ,往下递归合并,End;,Procedure proceed; ,计算若干多项式之积,Var,time,：,integer,；,a,：,real,；,t,：,link,；,Begin,new,（,p,）；,new,（,p.next,）,;,中间,p,链初始化,p.next.time,:=0;,p.next.a,:=1;,p.next.next,:=nil;,read(f,a,time,); ,读入第,1,个多项式的首项,while not,eof(f,) do,begin,new(r,);,r.next,:=nil; ,展开式初始化,repeat ,aX,time,乘以,p,链上的各项，并合并同类项，结果存入,r,链,if a0 then begin,t:=,p.next,;,while tnil do begin,add(time+t.time, a*,t.a, r);,t:=,t.next,;,end;,end;,read(f,a,time,) ,读入当前多项式的下一项,until (a=0) or,eof(f,);,Read(f,a,time,); ,再读下一项,if not,eof,（,f,）,若当前项不是最后一项，则将当前展开的结果转赋给,p,，释放以前各多项式的展开式,then begin,t:=p,；,p:=r;,free(t,);,end;,End;,End;,Procedure,print(r:link,); ,打印结果,Begin,if rnil then begin,write(a,r.time, _,r.a:3:0, );,print(r.next,);,end;,End;,Begin,init; ,文件读前准备,proceed; ,展开多项式,print,（,r.next,）,; ,打印展开式各项系数,writeln,；,End;,结束语,组合数学中的算法很多，有一定的难度,希望大家在掌握组合数学基本概念和基本原理的基础上，适当作一些中等难度的题目。,