开源中文网

您的位置: 首页 > Pascal语言 > 正文

PASCAL算法

来源:  作者:

求两数的最小公倍数 


function lcm(a,b:integer):integer; 
begin 
if a<b then swap(a,b); 
lcm:=a; 
while lcm mod b>0 do inc(lcm,a); 
end;

2.判断一个书是否为素数 
算法分析: 
方法1:建立素数表(程序同上) 
方法2:枚举这个数可能的约数 
function pd_prime(n:longint):boolean; 
var i:longint; 
begin 
for i:=2 to trunc(sqrt(n)) do 
if n mod i=0 then 
begin 
pd_prime:=false; 
exit; 
end; 
pd_prime:=true; 
end;

两数的最大公约数
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;

 

{=== 欧几里德算法求a,b的最大公倍数 ===} 
function euclid(a,b:longint):longint; 
begin 
if b=0 then euclid:=a 
else eucild:=euclid(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;
begin
if b=0 then 
begin
result:=a;
x:=1;
y:=0;
end
else
begin
result:=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: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;

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
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;
   end;
end;
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;
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;
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;
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
   repeat
    if b[1]=0 then fill(c,b) else
              if a[1]=a[0] then fill(a,c) else fill(b,a);
    inc(step);
   writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
   until c[1]=d;
end.

1.4 求a^b mod n

1.算法8:直接叠代法求a^b 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.算法9:加速叠代法

function f(a,b,n:longint):longint;

var d,t:longint;

begin

d:=1;t:=a;

while b>0 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;

Tags:PASCAL算法
相关文章列表:
关于开源中文网 - 联系我们 - 广告服务 - 网站地图 - 版权声明