基本算法（pascal版）

一、高精度乘法

1.高精度乘单精度(1位数)

程序如下:

program HighPrecision3_Multiply1; const

maxlen=100; { max length of the number } type

hp=record

len:integer; { length of the number } s:array[1..maxlen] of integer; end; var

x,y:hp; { x:input hp ; y:output } z:integer; { z:input lp }

procedure PrintHP(const p:hp); var i:integer; begin

for i:=p.len downto 1 do write(p.s[i]); end;

procedure init; var

st:string; i:integer; begin

readln(st);

x.len:=length(st);

for i:=1 to x.len do { change string to HP } x.s[i]:=ord(st[x.len+1-i])-ord('0'); readln(z); end;

procedure Multiply(a:hp;b:integer;var c:hp); { c:=a*b } var i,len:integer; begin

fillchar(c,sizeof(c),0); len:=a.len;

for i:=1 to len do begin

inc(c.s[i],a.s[i]*b);

inc(c.s[i+1],c.s[i] div 10); c.s[i]:=c.s[i] mod 10; end; inc(len);

while(c.s[len]>=10) do begin

inc(c.s[len+1],c.s[len] div 10);

1

c.s[len]=c.s[len] mod 10; inc(len); end;

while(len>1) and (c.s[len]=0) do dec(len); c.len:=len; end;

procedure main; begin

Multiply(x,z,y); end;

procedure out; begin

PrintHP(y); writeln; end;

begin init; main; out; end.

2.高精度乘一个整型数据(integer)

只需要将上述程序的hp类型定义如下即可: type

hp=record

len:integer { length of the number } s:array[1..maxlen] of longint { s[1] is the lowest position s[len] is the highest position } end;

3.高精度乘高精度 程序如下:

program HighPrecision4_Multiply2; const

maxlen=100; { max length of the number } type

hp=record

len:integer; { length of the number } s:array[1..maxlen] of integer end; var

x:array[1..2] of hp;

y:hp; { x:input ; y:output }

procedure PrintHP(const p:hp); var i:integer;

2

begin

for i:=p.len downto 1 do write(p.s[i]); end;

procedure init; var

st:string; j,i:integer; begin

for j:=1 to 2 do begin

readln(st);

x[j].len:=length(st);

for i:=1 to x[j].len do { change string to HP } x[j].s[i]:=ord(st[x[j].len+1-i])-ord('0'); end; end;

procedure Multiply(a,b:hp;var c:hp); { c:=a+b } var i,j,len:integer; begin

fillchar(c,sizeof(c),0); for i:=1 to a.len do for j:=1 to b.len do begin

inc(c.s[i+j-1],a.s[i]*b.s[j]); inc(c.s[i+j],c.s[i+j-1] div 10); c.s[i+j-1]:=c.s[i+j-1] mod 10; end;

len:=a.len+b.len+1;

while(len>1)and(c.s[len]=0) do dec(len); c.len:=len; end;

procedure main; begin

Multiply(x[1],x[2],y); end;

procedure out; begin

PrintHP(y); writeln; end;

begin init; main; out; end.

3

高精度相关题目noip2006第四题、noip2007第三题。

二、快速排序和堆排序

1快速排序

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束. const max=100000; var

a:array[1..max] of longint; n:longint;

procedure sort(l, r: longint); var

i, j, t, x: longint; begin i := l; j := r;

x := a[l + random(r - l + 1)]; while i <= j do begin

while a[i] < x do inc(i); while a[j] > x do dec(j); if i <= j then begin

t := a[i]; a[i] := a[j]; a[j] := t; inc(i); dec(j); end; end;

if l < j then sort(l, j); if i < r then sort(i, r); end;

2.堆排序

堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有 Ri<=R2i 和Ri<=R2i+1(或>=)

堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。 堆排序的思想是：

1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆） 2）当未排序完时

输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。 程序如下： program duipx; const n=8;

type arr=array[1..n] of integer; var a:arr;i:integer;

procedure sift(var a:arr;l,m:integer); var i,j, t:integer; begin

4

i:=l;j:=2*i;t:=a[i]; while j<=m do begin

if (ja[j+1]) then j:=j+1;

if t>a[j] then begin a[i]:=a[j];i:=j;j:=2*i; end else exit; a[i]:=t; end; end;

begin

for i:=1 to n do read(a[i]); for i:=(n div 2) downto 1 do sift(a,i,n);

for i:=n downto 2 do begin

write(a[1]:4); a[1]:=a[i]; sift(a,1,i-1); end;

writeln(a[1]:4); end.

堆排序和快速排序的相关题目为noip2004的合并果子，请大家用堆和快排加两个队列这两种方法分别实现。

三、动态规划

1 动态规划的概念

在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。 2 动态规划适合解决什么样的问题

动态规划的最优化原理是无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。 可以通俗地理解为子问题的局部最优将导致整个问题的全局最优在上例中例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。

动态规划的无后效性原则某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I之前的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。 3 用动态规划法解题的一般模式

5

本文来源：https://www.bwwdw.com/article/oz4f.html