数学知识及其相关算法

导读:数学知识及其相关算法,第一章有关数论的算法2,1.2有关素数的算法..............................,3.3排列与组合的产生算法...........................,4.1基础知识.................................,4.3寻找凸包算法...............................,第五章其它数学知识及算

数学知识及其相关算法

数学知识及其相关算法

第一章 有关数论的算法 2

1.1最大公约数与最小公倍数 ......................................................................................................... 2

1. 2有关素数的算法 ........................................................................................................................ 2

1.3方程ax+by=c的整数解及应用 ................................................................................................ 5

1.4 求a^b mod n ............................................................................................................................ 7

第二章 高精度计算 8

2.1高精度加法 ................................................................................................................................. 8

2. 2 高精度减法 ............................................................................................................................. 10

2.3高精度乘法 .............................................................................................................................. 12

2.4 高精度除法 .............................................................................................................................. 15

练习 ................................................................................................................................................ 20

第三章 排列与组合 20

3.1加法原理与乘法原理 ............................................................................................................... 20

练习: ........................................................................................................................................ 20

3. 2 排列与组合的概念与计算公式 ............................................................................................. 21

练习: ........................................................................................................................................ 21

3.3排列与组合的产生算法 .......................................................................................................... 22

练习 ............................................................................................................................................ 25

第四章 计算几何 25

4.1 基础知识.................................................................................................................................. 25

4. 2 线段的相交判断 ..................................................................................................................... 26

4.3寻找凸包算法 .......................................................................................................................... 27

练习 ................................................................................................................................................ 30

第五章 其它数学知识及算法

30

5.1 鸽巢原理.................................................................................................................................. 30

5. 2 容斥原理及应用 ................................................................................................................... 31

5.3 常见递推关系及应用 ............................................................................................................ 31

第一章 有关数论的算法

1.1最大公约数与最小公倍数

1.算法1: 欧几里德算法求a,b的最大公约数

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)) function gcd(a,b:longint):longint; begin if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b); end;

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(pnum<n) do

begin

inc(x);

if IsPrime(x) then begin inc(pnum);

end;

end;

procedure out;

var i,t:integer;

begin

for i:=1 to n do

begin

write(p[i]: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:array[1..maxn] of integer;

begin

readln(n);

for i:=1 to n do a[i]:=i;

a[1]:=0; i:=2;

while i<n do

begin

k:=2*i;

while k<=n do

p[pnum]:=x; end;

a[k]:=0;

k:=k+i;

end;

i:=i+1;

while (a[i]=0) and (i<n) do i:=i+1;

end;

k:=0;

for i:=1 to n do

if a[i]<>0 then

begin

write(a[i]:5); k:=k+1;

if k mod 10 =0 then writeln;

end

end.

3.算法6:将整数分解质因数的积

program BasicMath_PolynomialFactors;

const

maxp=1000;

var

pnum,n:longint;

num,p:array[1..maxp] of longint;

procedure main;

var x:longint;

begin

fillchar(num,sizeof(num),0);

fillchar(p,sizeof(p),0);

pnum:=0;

x:=1;

while(n>1) do

begin

inc(x);

if n mod x=0 then

begin

inc(pnum);

p[pnum]:=x;

while(n mod x=0) do

begin

n:=n div x;

inc(num[pnum]);

end;

end;

end;

end;

var j,i:integer;

begin

for i:=1 to pnum do

for j:=1 to num[i] do

write(p[i]:5);

writeln;

end;

begin

main;

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;

begin

d:=exgcd(a,b,x,y);

if c mod d>0 then

begin

writeln('no answer');

halt;

end else

begin

x0:=x*(c div d);

y0:=y*(c div d);

end;

end;

2.方程ax+by=c整数解的应用

例1:有三个分别装有a升水、b升水和c升水的量筒(gcd(a,b)=1,c>b>a>0),现c筒装满水,

问能否在c筒个量出d升水(c>d>0)。若能,请列出一种方案。

算法分析:

量水过程实际上就是倒来倒去,每次倒的时候总有如下几个持点:

1.总有一个筒中的水没有变动;

2.不是一个筒被倒满就是另一个筒被倒光;

3.c筒仅起中转作用,而本身容积除了必须足够装下a简和b简的全部水外,别无其 它限制。

程序如下:

program mw;

博泰典藏网btdcw.com包含总结汇报、经管营销、外语学习、出国留学、高中教育、工程科技、行业论文、自然科学、IT计算机、教学研究、农林牧渔、计划方案、表格模板、初中教育以及数学知识及其相关算法等内容。

本文共6页1234>>6