组合数学一些结论.doc

第一章 有关数论的算法1.1最大公约数与最小公倍数function gcd(a,b:longint):longint;beginif a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b);end;1.算法1: 欧几里德算法求a，b的最大公约数function gcd(a,b:longint):longint;beginif b=0 then gcdd:=aelse gcd:=gcd(b,a mod b);end;2.算法2:最小公倍数acm=a*b div gcd(a,b); function gcd(a,b:longint):longint;beginif a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b);end;3.算法3:扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y（一组解）function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 thenbegin exgcd:=a; x:=1; y:=0;endelsebegin exgcdt:=exgcd(b,a mod b,x,y); t:=x; x:=y; y:=t-(a div b)*y;end;end;（理论依据：gcd(a,b)=ax+by=bx1+(a mod b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1)）1. 2有关素数的算法1.算法4:求前n个素数:program BasicMath_Prime;const maxn=1000;var pnum,n:longint; p:array1.maxn of longint;function IsPrime(x:longint):boolean;var i:integer;beginfor i:=1 to pnum do if sqr(pi)=x then begin if x mod pi=0 then begin IsPrime:=false; exit; end;endelse begin IsPrime:=true; exit;end;IsPrime:=true;end;procedure main;var x:longint;beginpnum:=0; x:=1;while(pnumn) dobegininc(x);if IsPrime(x) then begin inc(pnum); ppnum:=x; end;end;end;procedure out;var i,t:integer;beginfor i:=1 to n dobeginwrite(pi:5);t:=t+1;if t mod 10=0 then writeln;end;end;begin readln(n); main; out; end.2.算法5:求不大于n的所有素数program sushu3;const maxn=10000;var i,k,n:integer; a:array1.maxn of integer;beginreadln(n);for i:=1 to n do ai:=i;a1:=0; i:=2;while in do begin k:=2*i; while k=n do begin ak:=0; k:=k+i; end; i:=i+1; while (ai=0) and (in) do i:=i+1;end;k:=0;for i:=1 to n do if ai0 then begin write(ai:5); k:=k+1; if k mod 10 =0 then writeln; endend.3.算法6:将整数分解质因数的积program BasicMath_PolynomialFactors;constmaxp=1000;varpnum,n:longint;num,p:array1.maxp of longint;procedure main;var x:longint;beginfillchar(num,sizeof(num),0);fillchar(p,sizeof(p),0);pnum:=0;x:=1;while(n1) do begin inc(x); if n mod x=0 then begin inc(pnum); ppnum:=x; while(n mod x=0) do begin n:=n div x; inc(numpnum); end; end;end;end;procedure out;var j,i:integer;beginfor i:=1 to pnum dofor j:=1 to numi dowrite(pi:5);writeln;end;beginmain;out;end.1.3方程ax+by=c的整数解及应用1.算法7：求方程ax+by=c的整数解procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d0 thenbegin writeln(no answer); halt;end elsebegin x0:=x*(c div d); y0:=y*(c div d);end;end;2.方程ax+by=c整数解的应用例1：有三个分别装有a升水、b升水和c升水的量筒(gcd(a，b)1，cba0),现c筒装满水，问能否在c筒个量出d升水(cd0)。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2不是一个筒被倒满就是另一个筒被倒光；3c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其 它限制。程序如下:program mw;typenode=array0.1 of longint;vara,b,c:node;d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 then begin exgcd:=a;x:=1;y:=0; end else begin exgcd:=exgcd(b,a mod b,x,y); t:=x;x:=y;y:=t-(a div b)*y end;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d0 thenbegin writeln(no answer); halt;end elsebegin x0:=x*(c div d); y0:=y*(c div d);end;end;procedure fill(var a,b:node);var t:longint;beginif a10 then repeat if a1=0 then fill(c,a) else if b1=b0 then fill(b,c) else fill(a,b); inc(step); writeln(step:5,:,a1:5,b1:5,c1:5); until c1=d else repeat if b1=0 then fill(c,b) else if a1=a0 then fill(a,c) else fill(b,a); inc(step); writeln(step:5,:,a1:5,b1:5,c1:5); until c1=d;end.1.4 求ab mod n1.算法8:直接叠代法求ab mod nfunction f(a,b,n:longint): longint;var d,i:longint;begind:=a;for i:=2 to b do d:=d mod n*a;d:=d mod n;f:=d;end;2.算法9:加速叠代法function f(a,b,n:longint):longint;var d,t:longint;begind:=1;t:=a;while b0 do beginif t=1 then beginf:=d;exit end ;if b mod 2 =1 then d:=d*t mod n; b:=b div 2; t:=t*t mod n; end;f:=dend;第二章 高精度计算2.1高精度加法高精度加法程序如下：program HighPrecision1_Plus;const fn_inp=hp1.inp; fn_out=hp1.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x:array1.2 of hp; y:hp; x:input ; y:output procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; j,i:integer; begin assign(input,fn_inp); reset(input); for j:=1 to 2 do begin readln(st); xj.len:=length(st); for i:=1 to xj.len do change string to HP xj.si:=ord(stxj.len+1-i)-ord(0); end; close(input); end; procedure Plus(a,b:hp;var c:hp); c:=a+b var i,len:integer; begin fillchar(c,sizeof(c),0); if a.lenb.len then len:=a.len get the bigger length of a,b else len:=b.len; for i:=1 to len do plus from low to high begin inc(c.si,a.si+b.si); if c.si=10 then begin dec(c.si,10); inc(c.si+1); add 1 to a higher position end; end; if c.slen+10 then inc(len); c.len:=len; end; procedure main; begin Plus(x1,x2,y); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; close(output); end; begin init; main; out; end.2. 2 高精度减法高精度减法程序如下：program HighPrecision2_Subtract;const fn_inp=hp2.inp; fn_out=hp2.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x:array1.2 of hp; y:hp; x:input ; y:output positive:boolean; procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; j,i:integer; begin assign(input,fn_inp); reset(input); for j:=1 to 2 do begin readln(st); xj.len:=length(st); for i:=1 to xj.len do change string to HP xj.si:=ord(stxj.len+1-i)-ord(0); end; close(input); end; procedure Subtract(a,b:hp;var c:hp); c:=a-b, suppose a=b var i,len:integer; begin fillchar(c,sizeof(c),0); if a.lenb.len then len:=a.len get the bigger length of a,b else len:=b.len; for i:=1 to len do subtract from low to high begin inc(c.si,a.si-b.si); if c.si1) and (c.slen=0) do dec(len); c.len:=len; end; function Compare(const a,b:hp):integer; 1 if ab 0 if a=b -1 if ab.len then len:=a.len get the bigger length of a,b else len:=b.len; while(len0) and (a.slen=b.slen) do dec(len); find a position which have a different digit if len=0 then compare:=0 no difference else compare:=a.slen-b.slen; end; procedure main; begin if Compare(x1,x2)=10) do begin inc(c.slen+1,c.slen div 10); c.slen=c.slen mod 10; inc(len); end; while(len1) and (c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Multiply(x,z,y); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; close(output); end; begin init; main; out; end.2.高精度乘一个整型数据(integer)只需要将上述程序的hp类型定义如下即可:type hp=record len:integer length of the number s:array1.maxlen of longint s1 is the lowest position slen is the highest position end;3.高精度乘高精度程序如下:program HighPrecision4_Multiply2;const fn_inp=hp4.inp; fn_out=hp4.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x:array1.2 of hp; y:hp; x:input ; y:output procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; j,i:integer; begin assign(input,fn_inp); reset(input); for j:=1 to 2 do begin readln(st); xj.len:=length(st); for i:=1 to xj.len do change string to HP xj.si:=ord(stxj.len+1-i)-ord(0); end; close(input); end; procedure Multiply(a,b:hp;var c:hp); c:=a+b var i,j,len:integer; begin fillchar(c,sizeof(c),0); for i:=1 to a.len do for j:=1 to b.len do begin inc(c.si+j-1,a.si*b.sj); inc(c.si+j,c.si+j-1 div 10); c.si+j-1:=c.si+j-1 mod 10; end; len:=a.len+b.len+1; the product of a number with i digits and a number with j digits can only have at most i+j+1 digits while(len1)and(c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Multiply(x1,x2,y); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; close(output); end; begin init; main; out; end.2.4 高精度除法1.高精度除以整型数据(integer);程序如下:program HighPrecision3_Multiply1;const fn_inp=hp5.inp; fn_out=hp5.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x,y:hp; z,w:integer; procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; i:integer; begin assign(input,fn_inp); reset(input); readln(st); x.len:=length(st); for i:=1 to x.len do change string to HP x.si:=ord(stx.len+1-i)-ord(0); readln(z); close(input); end; procedure Divide(a:hp;b:integer;var c:hp;var d:integer); c:=a div b ; d:=a mod b var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a.len; d:=0; for i:=len downto 1 do from high to low begin d:=d*10+a.si; c.si:=d div b; d:=d mod b; end; while(len1) and (c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Divide(x,z,y,w); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; writeln(w); close(output); end; begin init; main; out; end.2.高精度除以高精度程序如下:program HighPrecision4_Multiply2;const fn_inp=hp6.inp; fn_out=hp6.out; maxlen=100; max length of the number type hp=record len:integer; length of the number s:array1.maxlen of integer s1 is the lowest position slen is the highest position end;var x:array1.2 of hp; y,w:hp; x:input ; y:output procedure PrintHP(const p:hp); var i:integer; begin for i:=p.len downto 1 do write(p.si); end; procedure init; var st:string; j,i:integer; begin assign(input,fn_inp); reset(input); for j:=1 to 2 do begin readln(st); xj.len:=length(st); for i:=1 to xj.len do change string to HP xj.si:=ord(stxj.len+1-i)-ord(0); end; close(input); end; procedure Subtract(a,b:hp;var c:hp); c:=a-b, suppose a=b var i,len:integer; begin fillchar(c,sizeof(c),0); if a.lenb.len then len:=a.len get the bigger length of a,b else len:=b.len; for i:=1 to len do subtract from low to high begin inc(c.si,a.si-b.si); if c.si1) and (c.slen=0) do dec(len); c.len:=len; end; function Compare(const a,b:hp):integer; 1 if ab 0 if a=b -1 if ab.len then len:=a.len get the bigger length of a,b else len:=b.len; while(len0) and (a.slen=b.slen) do dec(len); find a position which have a different digit if len=0 then compare:=0 no difference else compare:=a.slen-b.slen; end; procedure Multiply10(var a:hp); a:=a*10 var i:Integer; begin for i:=a.len downto 1 do a.si+1:=a.si; a.s1:=0; inc(a.len); while(a.len1) and (a.sa.len=0) do dec(a.len); end; procedure Divide(a,b:hp;var c,d:hp); c:=a div b ; d:=a mod b var i,j,len:integer; begin fillchar(c,sizeof(c),0); len:=a.len; fillchar(d,sizeof(d),0); d.len:=1; for i:=len downto 1 do begin Multiply10(d); d.s1:=a.si; d:=d*10+a.si c.si:=d div b ; d:=d mod b; while(d=b) do begin d:=d-b;inc(c.si) end while(compare(d,b)=0) do begin Subtract(d,b,d); inc(c.si); end; end; while(len1)and(c.slen=0) do dec(len); c.len:=len; end; procedure main; begin Divide(x1,x2,y,w); end; procedure out; begin assign(output,fn_out); rewrite(output); PrintHP(y); writeln; PrintHP(w); writeln; close(output); end; begin init; main; out; end.第三章 排列与组合3.1加法原理与乘法原理1.加法原理：做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+.+mn 种不同的方法。2.乘法原理：做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有种mn不同的方法，那么完成这件事有 N=m1*m2*.*mn 种不同的方法。3.两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。练习：1.由数字1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？2.由数字0、1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？3.由数字0，1，2，3，4，5可以组成多少个十位数字大于个位数字的两位数？4. 一个三位密码锁,各位上数字由0,1,2,3,4,5,6,7,8,9十个数字组成,可以设置多少种三位数的密码(各位上的数字允许重复)？首位数字不为0的密码数是多少种？首位数字是0的密码数又是多少种？5.如图，要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，不同的涂色方案有多少种？6.某班有22名女生，23名男生. 选一位学生代表班级去领奖，有几种不同选法？ 选出男学生与女学生各一名去参加智力竞赛，有几种不同的选法？7.105有多少个约数？并将这些约数写出来.8.从5幅不同的国画、2幅不同的油画、7幅不同的水彩画中选不同画种的两幅画布置房间，有几种选法？9.若x、y可以取1，2，3，4，5中的任一个，则点(x,y)的不同个数有多少？10.一个口袋内装有5个小球另一个口袋内装有4个小球，所有这些小球的颜色各不相同 从两个口袋内任取一个小球，有 种不同的取法；11.从两个口袋内各取一个小球，有 种不同的取法.12.乘积（a1+a2+a3）(b1+b2+b3+b4)(c1+c2+c3+c4+c5)展开共有 个项。13.有四位考生安排在5个考场参加考试.有 种不同的安排方法。(答案:125；180；15；1000，900，100；6；45，506；8；59；25；9；20；60；625）3. 2 排列与组合的概念与计算公式1排列及计算公式从n个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 p(n,m)表示.p(n,m)=n(n-1)(n-2)(n-m+1)= n!/(n-m)!(规定0!=1).2组合及计算公式从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m)表示.c(n,m)=p(n,m)/m!=n!/(n-m)!*m!)；c(n,m)=c(n,n-m);其他排列与组合公式从n个元素中取出r个元素的循环排列数p(n,r)/r=n!/r(n-r)!.n个元素被分成k类，每类的个数分别是n1,n2,.nk这n个元素的全排列数为n!/(n1!*n2!*.*nk!).k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m).练习：1（1）用0，1，2，3，4组合多少无重复数字的四位数？（96）（2）这四位数中能被4整除的数有多少个？（30）（3）这四位数中能被3整除的数有多少个？（36）2用0，1，2，3，4五个数字组成无重复数字的五位数从小到