1、1数学知识及其相关算法第一章 有关数论的算法 .21.1 最大公约数与最小公倍数 .21. 2 有关素数的算法 .21.3 方程 ax+by=c 的整数解及应用 .41.4 求 ab mod n.6第二章 高精度计算 .62.1 高精度加法 .62. 2 高精度减法 .82.高精度乘法 .92.4 高精度除法 .12练习 .16第三章 排列与组合 .163.1 加法原理与乘法原理 .16练习： .163. 2 排列与组合的概念与计算公式 .17练习： .173.排列与组合的产生算法 .18练习 .20第四章 计算几何 .204.1 基础知识 .204. 2 线段的相交判断 .204.寻找凸包算
2、法 .22练习 .24第五章 其它数学知识及算法 .245.1 鸽巢原理 .245. 2 容斥原理及应用 .245. 常见递推关系及应用 .242第一章 有关数论的算法1.1 最大公约数与最小公倍数 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);3.算法 3:扩展的欧几里德算法，求出 gcd(a,b)和满足 gcd(a,b)=ax+by 的整数 x
3、 和 y （一组解）function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 then begin exgcd:=a; x:=1; y:=0; endelsebeginexgcdt:=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:
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 doif sqr(pi)0 thenbeginwrite(ai:5); k:=k+1;if k mod 10 =0 then writeln;endend.3.算法 6:将整数分解质因数的积program BasicMath_PolynomialFactors;con
5、stmaxp=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) dobegininc(x);if n mod x=0 then4begininc(pnum);ppnum:=x;while(n mod x=0) dobeginn:=n div x;inc(numpnum);end;end;end;end;procedure ou
6、t;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 thenbeginwriteln(no answer);halt;end elsebegi
7、nx0:=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.不是一个筒被倒满就是另一个筒被倒光；3.c 筒仅起中转作用，而本身容积除了必须足够装下 a 简和 b 简的全部水外，别无其它限制。 程序如下: program mw;typenode=array0
8、.1 of longint;5vara,b,c:node;d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 thenbeginexgcd:=a;x:=1;y:=0;endelsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*yend;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;be
9、gind:=exgcd(a,b,x,y);if c mod d0 thenbeginwriteln(no answer);halt;end elsebeginx0:=x*(c div d);y0:=y*(c div d);end;end;procedure fill(var a,b:node);var t:longint;beginif a10 thenrepeatif a1=0 then fill(c,a) elseif b1=b0 then fill(b,c) else fill(a,b);inc(step);writeln(step:5,:,a1:5,b1:5,c1:5);until c
10、1=delse6repeatif b1=0 then fill(c,b) elseif 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 n 1.算法 8:直接叠代法求 ab mod n function f(a,b,n:longint): longint; var d,i:longint; begin d:=a; for i:=2 to b do d:=d mod n*a; d:=d mod n; f:=d; end; 2.算法
11、9:加速叠代法 function f(a,b,n:longint):longint; var d,t:longint; begin d:=1;t:=a; while b0 do begin if t=1 then begin f:=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:=d end; 第二章 高精度计算2.1 高精度加法 高精度加法程序如下： program HighPrecision1_Plus;constfn_inp=hp1.inp;fn_out=hp1.out;maxl
12、en=100; max length of the number typehp=recordlen:integer; length of the number s:array1.maxlen of integer s1 is the lowest positionslen is the highest position end;var7x:array1.2 of hp;y:hp; x:input ; y:output procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.si);end
13、; procedure init;varst:string;j,i:integer;beginassign(input,fn_inp);reset(input);for j:=1 to 2 dobeginreadln(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;beginfillchar(
14、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 begininc(c.si,a.si+b.si);if c.si=10 thenbegindec(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
15、Plus(x1,x2,y);end; procedure out;beginassign(output,fn_out);rewrite(output);PrintHP(y);writeln;close(output);end; 8begin init; main; out; end. 2. 2 高精度减法 高精度减法程序如下： program HighPrecision2_Subtract;constfn_inp=hp2.inp;fn_out=hp2.out;maxlen=100; max length of the number typehp=recordlen:integer; lengt
16、h of the number s:array1.maxlen of integer s1 is the lowest positionslen is the highest position end;varx:array1.2 of hp;y:hp; x:input ; y:output positive:boolean; procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.si);end;procedure init;varst:string; j,i:integer;begin
17、assign(input,fn_inp);reset(input);for j:=1 to 2 dobeginreadln(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;beginfillchar(c,sizeof(c),0);if a.lenb.len th
18、en 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 begininc(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 ab0 if a=b-1 if ab.len then len:=a.len get the bigger length of a,b else le
19、n:=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;beginif Compare(x1,x2)=10) dobegininc(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;beginMultiply(x,z,y);end;procedure out;beginassign(output,fn_out);rewrite(output);PrintHP(y);writeln;close(output);
