组合数学一些结论.doc_第1页
组合数学一些结论.doc_第2页
组合数学一些结论.doc_第3页
组合数学一些结论.doc_第4页
组合数学一些结论.doc_第5页
已阅读5页,还剩29页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第一章 有关数论的算法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五个数字组成无重复数字的五位数从小到

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论