mathformulae.rar_adder_数论_线段相交_计算几何PDF

共1个文件

doc：1个

版权申诉

adder

131 浏览量 2022-09-20 14:16:34 上传评论收藏 38KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

mathformulae.rar （1个子文件）

数学知识及其相关算法.doc 186KB

数学知识及其相关算法

第一章有关数论的算法 ....................................................................................................................................2

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

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

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

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

第二章高精度计算............................................................................................................................................6

2.1 高精度加法 ..................................................................................................................................................................6

2. 2 高精度减法 ...............................................................................................................................................................8

2.３高精度乘法 .................................................................................................................................................................9

2.4 高精度除法 ...............................................................................................................................................................12

练习....................................................................................................................................................................................16

第三章排列与组合..........................................................................................................................................16

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

练习：............................................................................................................................................................................16

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

练习：............................................................................................................................................................................17

3.３排列与组合的产生算法 ...........................................................................................................................................18

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

第四章计算几何 .............................................................................................................................................20

4.1 基础知识 ...................................................................................................................................................................20

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

4.３寻找凸包算法 ...........................................................................................................................................................22

练习....................................................................................................................................................................................24

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

5.1 鸽巢原理 ...................................................................................................................................................................24

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

5.３常见递推关系及应用 .............................................................................................................................................24

第一章有关数论的算法

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;

（理论依据：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: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); p[pnum]:=x; end;

end;

procedure out;

var i,t:integer;

begin

function gcd(a,b:longint):longint;

begin

if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b);

end;

for i:=1 to n do

begin

write(p[i]:5);t:=t+1;

if t mod 10=0 then writeln;

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

begin

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;

procedure out;

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;

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;

type

node=array[0..1] of longint;

var

a,b,c:node;

d,step,x,y:longint;

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

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

t:=x;x:=y;y:=t-(a div b)*y

end;

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;

procedure fill(var a,b:node);

var t:longint;

begin

if a[1]<b[0]-b[1] then t:=a[1]

else t:=b[0]-b[1];

a[1]:=a[1]-t;

b[1]:=b[1]+t

end;

begin

write('a,b,c,d=');

readln(a[0],b[0],c[0],d);

equation(a[0],b[0],d,x,y);

step:=0;

a[1]:=0;b[1]:=0;c[1]:=c[0];

writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);

if x>0 then

repeat

if a[1]=0 then fill(c,a) else

if b[1]=b[0] then fill(b,c) else fill(a,b);

inc(step);

writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);

until c[1]=d

else

评论收藏

内容反馈

版权申诉

林当时

粉丝: 97
资源: 1万+

mathformulae.rar_adder_数论_线段相交_计算几何 PDF_高精度

最新资源

mathformulae.rar_adder_数论_线段 相交_计算几何 PDF_高精度

adder_sub_struct.rar_adder_adder_sub_struct_sub_vhd_vhdl

adder32_carry_select.rar_adder32_adder32_carry_select_hspice_hsp

select_adder.rar_Verilog adder_adder_select

FA.rar_adder_continentqaa_full_occasionally3HT_steamtem

adder4.rar_adder4

bcd_adder.rar_Verilog BCD_Verilog adder_adder_adder verilog _ver

adder-mutiplier.rar_adder_fixed point_乘法_定点乘法_浮点数乘法器

carry_select_adder.rar_ Carry Select Adder_carry select adder_it

FourBit_Adder.rar_four bit adder

bcd_adder_8.rar_8421bcd码加法_bcd_bcd adder

MIPS32.rar_control.v_mips pipeline

FP_adder.rar_32 bit adder_floating_verilog hdl

BCD-adder.rar_SUM_adder bcd

float_adder.rar_basis8sq_float_float_adder_浮点数 加法_浮点数加法

model_adder.rar_modelsim 例程_quartus adder命令

BCD_adder_4digit.rar_4位bcd加法_bcd_adder_4digit

quanjiaqi.rar_full adder matlab_matlab adder_matlab full adder

butterfly1.rar_BUTTERFLY ADDER_fft_fft adder

adder4.rar_4adder_8421BCD码全加器_8421bcd全加器_adder bcd_bcd adders vh

冰河的渗透实战笔记-冰河.pdf

大灰狼远控2021最新版，解压密码222

J-LINK V10 V11固件.rar

ISO21434.pdf

Web安全漏洞扫描工具-AWVS14

CTF 竞赛入门指南（ctf-all-in-one）.pdf

Web中间件常见漏洞总结.pdf

stm32f103 adc采样+dma传输+fft处理 频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_

jts-1.14.zip

CobaltStrike4.4.zip

最新资源

mathformulae.rar_adder_数论_线段相交_计算几何 PDF_高精度

float_adder.rar_basis8sq_float_float_adder_浮点数加法_浮点数加法

stm32f103 adc采样+dma传输+fft处理频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_