数学知识及其相关算法.pdfVIP

数学知识及其相关算法 第一章 有关数论的算法2 1.1 最大公约数与最小公倍数 2 1. 2 有关素数的算法 3 1.3 方程ax+by=c的整数解及应用 5 1.4 求a^b mod n 7 第二章 高精度计算8 2.1 高精度加法 8 2. 2 高精度减法 10 2. ３高精度乘法 12 2.4 高精度除法 16 练习 21 第三章 排列与组合21 3.1 加法原理与乘法原理 21 练习： 21 3. 2 排列与组合的概念与计算公式 22 练习： 22 3. ３排列与组合的产生算法 23 练习 26 第四章 计算几何 27 4.1 基础知识 27 4. 2 线段的相交判断 27 4. ３寻找凸包算法 29 练习 32 1 第五章 其它数学知识及算法32 5.1 鸽巢原理 32 5. 2 容斥原理及应用 32 5. ３ 常见递推关系及应用 33 第一章 有关数论的算法 1.1 最大公约数与最小公倍数 1.算法 1: 欧几里德算法求 a，b 的最大公约数 function gcd(a,b:longint):longint; begin if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b); end; function gcd(a,b:longint):longint; begin if b=0 then gcdd:=a else 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 和 y （一组解） function exgcd(a,b:longint;var x,y:longint):longint; var t:longint; begin if b=0 then begin exgcd:=a; x:=1; y:=0; end else begin 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) ） 2 1. 2 有关素数的算法 1.算法 4:求前 n 个素数: program BasicMath_Prime; const maxn=1000; var pnum,n:longint; p:array[1..maxn] of longint; function IsPrime(x:longint):boolean; var i:integer; begin for i:=1 to pnum do if sqr(p[i])=x then begin if x mod p[i]=0 then begin IsPrime:=false; exit; end; end else begin IsPrime:=true; exit; end; IsPrime:=true; end; procedure main; var x:longint; begin pnum:=0; x:=1; while(pnumn) do begin i