文档库 最新最全的文档下载
当前位置:文档库 › Pascal程序设计经典算法

Pascal程序设计经典算法

Pascal程序设计经典算法
Pascal程序设计经典算法

一、数论算法

1.求两数的最大公约数

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

begin

if b=0 then gcd:=a

else gcd:=gcd (b,a mod b);

end ;

2.求两数的最小公倍数

function lcm(a,b:integer):integer;

begin

if a

lcm:=a;

while lcm mod b>0 do inc(lcm,a);

end;

3.素数的求法

A.小范围内判断一个数是否为质数:

function prime (n: integer): Boolean;

var I: integer;

begin

for I:=2 to trunc(sqrt(n)) do

if n mod I=0 then begin

prime:=false; exit;

end;

prime:=true;

end;

B.判断longint范围内的数是否为素数(包含求50000以内的素数表):

procedure getprime;

var

i,j:longint;

p:array[1..50000] of boolean;

begin

fillchar(p,sizeof(p),true);

p[1]:=false;

i:=2;

while i<50000 do begin

if p[i] then

begin

j:=i*2;

while j<50000 do

begin {筛选法}

p[j]:=false;

inc(j,i);

end;

end;

inc(i);

end;

l:=0;

for i:=1 to 50000 do

if p[i] then begin

inc(l);pr[l]:=i;

end;

end;{getprime}

function prime(x:longint):boolean;

var i:integer;

begin

prime:=false;

for i:=1 to l do

if pr[i]>=x then break

else if x mod pr[i]=0 then exit;

prime:=true;

end;{prime}

二、图论算法

1.最小生成树

A.Prim算法:

procedure prim(v0:integer);

var

lowcost,closest:array[1..maxn] of integer; i,j,k,min:integer;

begin

for i:=1 to n do begin

lowcost:=cost[v0,i];

closest:=v0;

end;

for i:=1 to n-1 do begin

{寻找离生成树最近的未加入顶点k}

min:=maxlongint;

for j:=1 to n do

if (lowcost[j]0) then begin

min:=lowcost[j];

k:=j;

end;

lowcost[k]:=0; {将顶点k加入生成树}

{生成树中增加一条新的边k到closest[k]} {修正各点的lowcost和closest值}

for j:=1 to n do

if cost[k,j]

lowcost[j]:=cost[k,j];

closest[j]:=k;

end;

end;

end;{prim}

B.Kruskal算法:(贪心)

按权值递增顺序删去图中的边,若不形成回路则将此边加入最小生成树。

function find(v:integer):integer; {返回顶点v所在的集合}

var i:integer;

begin

i:=1;

while (i<=n) and (not v in vset) do inc(i);

if i<=n then find:=i else find:=0;

end;

procedure kruskal;

var

tot,i,j:integer;

begin

for i:=1 to n do vset:=;{初始化定义n个集合,第I个集合包含一个元素I}

p:=n-1; q:=1; tot:=0; {p为尚待加入的边数,q为边集指针}

sort;

{对所有边按权值递增排序,存于e中,e.v1与e.v2为边I所连接的两个顶点的序号,e.len为第I条边的长度}

while p>0 do begin

i:=find(e[q].v1);j:=find(e[q].v2);

if i<>j then begin

inc(tot,e[q].len);

vset:=vset+vset[j];vset[j]:=[];

dec(p);

end;

inc(q);

end;

writeln(tot);

end;

2.最短路径

A.标号法求解单源点最短路径:

var

a:array[1..maxn,1..maxn] of integer;

b:array[1..maxn] of integer; {b指顶点i到源点的最短路径}

mark:array[1..maxn] of boolean;

procedure bhf;

var

best,best_j:integer;

begin

fillchar(mark,sizeof(mark),false);

mark[1]:=true; b[1]:=0;{1为源点}

repeat

best:=0;

for i:=1 to n do

If mark then {对每一个已计算出最短路径的点}

for j:=1 to n do

if (not mark[j]) and (a[i,j]>0) then

if (best=0) or (b+a[i,j]

best:=b+a[i,j]; best_j:=j;

end;

if best>0 then begin

b[best_j]:=best;mark[best_j]:=true;

end;

until best=0;

end;{bhf}

B.Floyed算法求解所有顶点对之间的最短路径:

procedure floyed;

begin

for I:=1 to n do

for j:=1 to n do

if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I 到j的最短路径上j的前驱结点}

for k:=1 to n do {枚举中间结点}

for i:=1 to n do

for j:=1 to n do

if a[i,k]+a[j,k]

a[i,j]:=a[i,k]+a[k,j];

p[I,j]:=p[k,j];

end;

end;

C. Dijkstra 算法:

var

a:array[1..maxn,1..maxn] of integer;

b,pre:array[1..maxn] of integer; {pre指最短路径上I的前驱结点}

mark:array[1..maxn] of boolean;

procedure dijkstra(v0:integer);

begin

fillchar(mark,sizeof(mark),false);

for i:=1 to n do begin

d:=a[v0,i];

if d<>0 then pre:=v0 else pre:=0;

end;

mark[v0]:=true;

repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}

min:=maxint; u:=0; {u记录离1集合最近的结点}

for i:=1 to n do

if (not mark) and (d

u:=i; min:=d;

end;

if u<>0 then begin

mark[u]:=true;

for i:=1 to n do

if (not mark) and (a[u,i]+d[u]

d:=a[u,i]+d[u];

pre:=u;

end;

end;

until u=0;

end;

3.计算图的传递闭包

Procedure Longlink;

Var

T:array[1..maxn,1..maxn] of boolean;

Begin

Fillchar(t,sizeof(t),false);

For k:=1 to n do

For I:=1 to n do

For j:=1 to n do T[I,j]:=t[I,j] or (t[I,k] and t[k,j]); End;

4.无向图的连通分量

A.深度优先

procedure dfs ( now,color: integer);

begin

for i:=1 to n do

if a[now,i] and c=0 then begin {对结点I染色}

c:=color;

dfs(I,color);

end;

end;

B 宽度优先(种子染色法)

5.关键路径

几个定义:顶点1为源点,n为汇点。

a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;

b. 顶点事件最晚发生时间Vl[j], Vl [j] = min{ Vl[j] –w[I,j] },其中Vl(n) = Ve(n);

c. 边活动最早开始时间Ee, 若边I由表示,则Ee = Ve[j];

d. 边活动最晚开始时间El, 若边I由表示,则El = Vl[k] –w[j,k];

若Ee[j] = El[j] ,则活动j为关键活动,由关键活动组成的路径为关键路径。

求解方法:

a. 从源点起topsort,判断是否有回路并计算Ve;

b. 从汇点起topsort,求Vl;

c. 算Ee 和El;

6.拓扑排序

找入度为0的点,删去与其相连的所有边,不断重复这一过程。

例寻找一数列,其中任意连续p项之和为正,任意q 项之和为负,若不存在则输出NO.

7.回路问题

Euler回路(DFS)

定义:经过图的每条边仅一次的回路。(充要条件:图连同且无奇点)

Hamilton回路

定义:经过图的每个顶点仅一次的回路。

一笔画

充要条件:图连通且奇点个数为0个或2个。

9.判断图中是否有负权回路Bellman-ford 算法x,y,t分别表示第I条边的起点,终点和权。共n

个结点和m条边。

procedure bellman-ford

begin

for I:=0 to n-1 do d:=+infinitive;

d[0]:=0;

for I:=1 to n-1 do

for j:=1 to m do {枚举每一条边}

if d[x[j]]+t[j]

if d[x[j]]+t[j]

end;

10.第n最短路径问题

*第二最短路径:每举最短路径上的每条边,每次删除一条,然后求新图的最短路径,取这些路径中最短的一条即为第二最短路径。

*同理,第n最短路径可在求解第n-1最短路径的基础上求解。

三、背包问题

*部分背包问题可有贪心法求解:计算Pi/Wi 数据结构:

w:第i个背包的重量;

p:第i个背包的价值;

1.0-1背包:每个背包只能使用一次或有限次(可转化为一次):

A.求最多可放入的重量。

NOIP2001 装箱问题

有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30),每个物品有一个体积(正整数)。要求从n 个物品中,任取若千个装入箱内,使箱子的剩余空间为最小。

l 搜索方法

procedure search(k,v:integer); {搜索第k个物品,剩余空间为v}

var i,j:integer;

begin

if v

if v-(s[n]-s[k-1])>=best then exit; {s[n]为前n 个物品的重量和}

if k<=n then begin

if v>w[k] then search(k+1,v-w[k]);

search(k+1,v);

end;

end; l DP

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志,为布尔型。

实现:将最优化问题转化为判定性问题

f [I, j] = f [ i-1, j-w ] (w<=j<=v) 边界:f[0,0]:=true.

For I:=1 to n do

For j:=w to v do F[I,j]:=f[I-1,j-w];

优化:当前状态只与前一阶段状态有关,可降至一维。

F[0]:=true;

For I:=1 to n do begin

F1:=f;

For j:=w to v do

If f[j-w] then f1[j]:=true;

F:=f1;

End;

B.求可以放入的最大价值。

F[I,j] 为容量为I时取前j个背包所能获得的最大价值。

F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] }

C.求恰好装满的情况数。

DP:

Procedure update;

var j,k:integer;

begin

c:=a;

for j:=0 to n do

if a[j]>0 then

if j+now<=n then inc(c[j+now],a[j]);

a:=c;

end;

2.可重复背包

A求最多可放入的重量。

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志,为布尔型。

状态转移方程为

f[I,j] = f [ I-1, j – w*k ] (k=1.. j div w)

B.求可以放入的最大价值。

USACO 1.2 Score Inflation

进行一次竞赛,总时间T固定,有若干种可选择

的题目,每种题目可选入的数量不限,每种题目有一个ti(解答此题所需的时间)和一个si(解答此题所得的分数),现要选择若干题目,使解这些题的总时间在T以内的前提下,所得的总分最大,求最大的得分。

*易想到:

f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j])

其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。

*实现:

Begin

FillChar(f,SizeOf(f),0);

For i:=1 To M Do

For j:=1 To N Do

If i-problem[j].time>=0 Then

Begin

t:=problem[j].point+f[i-problem[j].time];

If t>f Then f:=t;

End;

Writeln(f[M]);

End.

C.求恰好装满的情况数。

Ahoi2001 Problem2

求自然数n本质不同的质数和的表达式的数目。

思路一,生成每个质数的系数的排列,在一一测试,这是通法。

procedure try(dep:integer);

var i,j:integer;

begin

cal; {此过程计算当前系数的计算结果,now 为结果}

if now>n then exit; {剪枝}

if dep=l+1 then begin {生成所有系数}

cal;

if now=n then inc(tot);

exit;

end;

for i:=0 to n div pr[dep] do begin

xs[dep]:=i;

try(dep+1);

xs[dep]:=0;

end;

end; 思路二,递归搜索效率较高

procedure try(dep,rest:integer);

var i,j,x:integer;

begin

if (rest<=0) or (dep=l+1) then begin

if rest=0 then inc(tot);

exit;

end;

for i:=0 to rest div pr[dep] do

try(dep+1,rest-pr[dep]*i);

end;

{main: try(1,n); }

思路三:可使用动态规划求解

USACO1.2 money system

V个物品,背包容量为n,求放法总数。

转移方程:

Procedure update;

var j,k:integer;

begin

c:=a;

for j:=0 to n do

if a[j]>0 then

for k:=1 to n div now do

if j+now*k<=n then inc(c[j+now*k],a[j]);

a:=c;

end;

{main}

begin

read(now); {读入第一个物品的重量}

i:=0; {a为背包容量为i时的放法总数}

while i<=n do begin

a:=1; inc(i,now); end; {定义第一个物品重的整数倍的重量a值为1,作为初值}

for i:=2 to v do

begin

read(now);

update; {动态更新}

end;

writeln(a[n]);

四、排序算法

1.快速排序:

procedure qsort(l,r:integer);

var i,j,mid:integer;

begin

i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数}

repeat

while a[i]

while a[j]>mid do dec(j);{在右半部分寻找比中间数小的数}

if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们}

t:=a[i]; a[i]:=a[j]; a[j]:=t;

inc(i);dec(j); {继续找}

end;

until i>j;

if l

if i

end;{sort}

B.插入排序:

思路:当前a[1]..a[i-1]已排好序了,现要插入a使a[1]..a有序。

procedure insert_sort;

var i,j:integer;

begin

for i:=2 to n do begin

a[0]:=a;

j:=i-1;

while a[0]

a[j+1]:=a[j];

j:=j-1;

end;

a[j+1]:=a[0];

end;

end;{inset_sort}

C.选择排序:

procedure sort;

var i,j,k:integer;

begin

for i:=1 to n-1 do

for j:=i+1 to n do

if a>a[j] then swap(a,a[j]);

end;

D. 冒泡排序procedure bubble_sort;

var i,j,k:integer;

begin

for i:=1 to n-1 do

for j:=n downto i+1 do

if a[j]

end;

E.堆排序:

procedure sift(i,m:integer);{调整以i为根的子树成为堆,m为结点总数}

var k:integer;

begin

a[0]:=a; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1}

while k<=m do begin

if (k

if a[0]

else k:=m+1;

end;

a:=a[0]; {将根放在合适的位置}

end;

procedure heapsort;

var

j:integer;

begin

for j:=n div 2 downto 1 do sift(j,n);

for j:=n downto 2 do begin

swap(a[1],a[j]);

sift(1,j-1);

end;

end;

F. 归并排序

{a为序列表,tmp为辅助数组}

procedure merge(var a:listtype; p,q,r:integer);

{将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r]}

var I,j,t:integer;

tmp:listtype;

begin

t:=p;i:=p;j:=q+1;{t为tmp指针,I,j分别为左右子序列的指针}

while (t<=r) do begin

if (i<=q){左序列有剩余} and ((j>r) or (a<=a[j])) {满足取左边序列当前元素的要求}

then begin

tmp[t]:=a; inc(i);

end

else begin

tmp[t]:=a[j];inc(j);

end;

inc(t);

end;

for i:=p to r do a:=tmp;

end;{merge}

procedure merge_sort(var a:listtype; p,r: integer); {合并排序a[p..r]}

var q:integer;

begin

if p<>r then begin

q:=(p+r-1) div 2;

merge_sort (a,p,q);

merge_sort (a,q+1,r);

merge (a,p,q,r);

end;

end;

{main}

begin

merge_sort(a,1,n);

end.

G.基数排序

思想:对每个元素按从低位到高位对每一位进行一次排序

五、高精度计算

高精度数的定义:

type

hp=array[1..maxlen] of integer;

1.高精度加法

procedure plus ( a,b:hp; var c:hp);

var i,len:integer;

begin

fillchar(c,sizeof(c),0);

if a[0]>b[0] then len:=a[0] else len:=b[0];

for i:=1 to len do begin

inc(c,a+b);

if c>10 then begin dec(c,10); inc(c[i+1]); end; {进位} end;

if c[len+1]>0 then inc(len);

c[0]:=len;

end;{plus}

2.高精度减法

procedure substract(a,b:hp;var c:hp);

var i,len:integer;

begin

fillchar(c,sizeof(c),0);

if a[0]>b[0] then len:=a[0] else len:=b[0];

for i:=1 to len do begin

inc(c,a-b);

if c<0 then begin inc(c,10);dec(c[i+1]); end;

while (len>1) and (c[len]=0) do dec(len);

c[0]:=len;

end;

3.高精度乘以低精度

procedure multiply(a:hp;b:longint;var c:hp);

var i,len:integer;

begin

fillchar(c,sizeof(c),0);

len:=a[0];

for i:=1 to len do begin

inc(c,a*b);

inc(c[i+1],(a*b) div 10);

c:=c mod 10;

end;

inc(len);

while (c[len]>=10) do begin {处理最高位的进位}

c[len+1]:=c[len] div 10;

c[len]:=c[len] mod 10;

inc(len);

end;

while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整len}

c[0]:=len;

end;{multiply}

4.高精度乘以高精度

procedure high_multiply(a,b:hp; var c:hp}

var i,j,len:integer;

begin

fillchar(c,sizeof(c),0);

for i:=1 to a[0] do

for j:=1 to b[0] do begin

inc(c[i+j-1],a*b[j]);

inc(c[i+j],c[i+j-1] div 10);

c[i+j-1]:=c[i+j-1] mod 10;

end;

len:=a[0]+b[0]+1;

while (len>1) and (c[len]=0) do dec(len);

c[0]:=len;

end;

5.高精度除以低精度

procedure devide(a:hp;b:longint; var c:hp; var d:longint);

{c:=a div b; d:= a mod b}

var i,len:integer;

begin

fillchar(c,sizeof(c),0);

len:=a[0]; d:=0;

for i:=len downto 1 do begin

d:=d*10+a;

c:=d div b;

d:=d mod b;

end;

while (len>1) and (c[len]=0) then dec(len);

c[0]:=len;

end;

6.高精度除以高精度

procedure high_devide(a,b:hp; var c,d:hp);

var

i,len:integer;

begin

fillchar(c,sizeof(c),0);

fillchar(d,sizeof(d),0);

len:=a[0];d[0]:=1;

for i:=len downto 1 do begin

multiply(d,10,d);

d[1]:=a;

while(compare(d,b)>=0) do {即d>=b}

begin

Subtract(d,b,d);

inc(c);

end;

end;

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

c.len:=len;

end;

六、树的遍历

1.已知前序中序求后序

procedure Solve(pre,mid:string);

var i:integer;

begin

if (pre='') or (mid='') then exit;

i:=pos(pre[1],mid);

solve(copy(pre,2,i),copy(mid,1,i-1));

solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length (mid)-i));

post:=post+pre[1]; {加上根,递归结束后post 即为后序遍历}

end;

2.已知中序后序求前序

procedure Solve(mid,post:string);

var i:integer;

begin

if (mid='') or (post='') then exit;

i:=pos(post[length(post)],mid);

pre:=pre+post[length(post)]; {加上根,递归结束后pre即为前序遍历}

solve(copy(mid,1,I-1),copy(post,1,I-1));

solve(copy(mid,I+1,length(mid)-I),copy(post,I,length( post)-i));

end;

3.已知前序后序求中序的一种

function ok(s1,s2:string):boolean;

var i,l:integer; p:boolean;

begin

ok:=true;

l:=length(s1);

for i:=1 to l do begin

p:=false;

for j:=1 to l do

if s1=s2[j] then p:=true;

if not p then begin ok:=false;exit;end;

end;

end;

procedure solve(pre,post:string);

var i:integer;

begin

if (pre='') or (post='') then exit;

i:=0;

repeat

inc(i);

until ok(copy(pre,2,i),copy(post,1,i));

solve(copy(pre,2,i),copy(post,1,i));

midstr:=midstr+pre[1];

solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,leng th(post)-i-1));

end;

七进制转换

1任意正整数进制间的互化

除n取余

2实数任意正整数进制间的互化

乘n取整

3负数进制:

设计一个程序,读入一个十进制数的基数和一个负进制数的基数,并将此十进制数转换为此负进制下的数:-R∈{-2,-3,-4, (20)

八全排列与组合的生成

1排列的生成:(1..n)

procedure solve(dep:integer);

var

i:integer;

begin

if dep=n+1 then begin writeln(s);exit; end;

for i:=1 to n do

if not used then begin

s:=s+chr(i+ord('0'));used:=true;

solve(dep+1);

s:=copy(s,1,length(s)-1); used:=false;

end;

end;

2组合的生成(1..n中选取k个数的所有方案) procedure solve(dep,pre:integer);

var

i:integer;

begin

if dep=k+1 then begin writeln(s);exit; end;

for i:=1 to n do

if (not used) and (i>pre) then begin

s:=s+chr(i+ord('0'));used:=true;

solve(dep+1,i);

s:=copy(s,1,length(s)-1); used:=false;

end;

end;

九.查找算法

1折半查找

function binsearch(k:keytype):integer;

var low,hig,mid:integer;

begin

low:=1;hig:=n;

mid:=(low+hig) div 2;

while (a[mid].key<>k) and (low<=hig) do begin

if a[mid].key>k then hig:=mid-1

else low:=mid+1;

mid:=(low+hig) div 2;

end;

if low>hig then mid:=0;

binsearch:=mid;

end;

2树形查找

二叉排序树:每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。

查找

function treesrh(k:keytype):pointer;

var q:pointer;

begin

q:=root;

while (q<>nil) and (q^.key<>k) do

if k

else q:=q^.right;

treesrh:=q;

end;

十、贪心

*会议问题

(1)n个活动每个活动有一个开始时间和一个结束时间,任一时刻仅一项活动进行,求满足活动数最多的情况。

解:按每项活动的结束时间进行排序,排在前面的优先满足。

(2)会议室空闲时间最少。

(3)每个客户有一个愿付的租金,求最大利润。(4)共R间会议室,第i个客户需使用i间会议室,

费用相同,求最大利润。

十一、回溯法框架

1. n皇后问题

procedure try(i:byte);

var j:byte;

begin

if i=n+1 then begin print;exit;end;

for j:=1 to n do

if a and b[j+i] and c[j-i] then begin

x:=j;

a[j]:=false; b[j+i]:=false; c[j-i]:=false;

try(i+1);

a[j]:=true; b[i+j]:=true; c[j-i]:=true;

end;

end;

2.Hanoi Tower h(n)=2*h(n-1)+1 h(1)=1

初始所有铜片都在a柱上

procedure hanoi(n,a,b,c:byte); {将第n块铜片从a 柱通过b柱移到c柱上}

begin

if n=0 then exit;

hanoi(n-1,a,c,b); {将上面的n-1块从a柱通过c柱移到b柱上}

write(n,’moved from’,a,’to’,c);

hanoi(n-1,b,a,c);{ 将b上的n-1块从b柱通过a 柱移到c柱上

end;

初始铜片分布在3个柱上,给定目标柱goal

h[1..3,0..n]存放三个柱的状态,now与nowp存最大的不到位的铜片的柱号和编号,h[I,0]存第I个柱上的个数。

Procedure move(k,goal:integer); {将最大不到位的k移到目标柱goal上}

Begin

If k=0 then exit;

For I:=1 to 3 do

For j:=1 to han[I,0] do

If h[I,j]=k then begin now:=I;nowp:=j; end; {找到k的位置}

If now<>goal then begin {若未移到目标}

Move(k-1,6-now-goal); {剩下的先移到没用的柱上}

Writeln(k moved from now to goal);

H[goal,h[goal,0]+1]:=h[now,nowp]; h[now,nowp]:=0;

Inc(h[goal,0]); dec(h[now,0]);

Move(k-1,goal); {剩下的移到目标上}

End;

十二、DFS框架

NOIP2001 数的划分

procedure work(dep,pre,s:longint); {入口为work(1,1,n)}

{dep为当前试放的第dep个数,pre为前一次试放的数,s为当前剩余可分的总数}

var j:longint;

begin

if dep=n then begin

if s>=pre then inc(r); exit;

end;

for j:=pre to s div 2 do work(dep+1,j,s-j); end;

类似:

procedure try(dep:integer);

var i:integer;

begin

if dep=k then begin

if tot>=a[dep-1] then inc(sum);

exit; end;

for i:=a[dep-1] to tot div 2 do begin

a[dep]:=i; dec(tot,i);

try(dep+1);

inc(tot,i);

end;

end;{try}

十三、BFS框架

IOI94 房间问题

head:=1; tail:=0;

while tail

inc(tail);

for k:=1 to n do

if k方向可扩展then begin

inc(head);

list[head].x:=list[tail].x+dx[k]; {扩展出新结点list[head]}

list[head].y:=list[tail].y+dy[k];

处理新结点list[head];

end;

end;

十五、数据结构相关算法

1.链表的定位函数loc(I:integer):pointer; {寻找链表中的第I个结点的指针}

procedure loc(L:linklist; I:integer):pointer;

var p:pointer;

j:integer;

begin

p:=L.head; j:=0;

if (I>=1) and (I<=L.len) then

while j

loc:=p;

end;

2.单链表的插入操作

procedure insert(L:linklist; I:integer; x:datatype);

var p,q:pointer;

begin

p:=loc(L,I);

new(q);

q^.data:=x;

q^.next:=p^.next;

p^.next:=q;

inc(L.len);

end;

3.单链表的删除操作

procedure delete(L:linklist; I:integer);

var p,q:pointer;

begin

p:=loc(L,I-1);

q:=p^.next;

p^.next:=q^.next;

dispose(q);

dec(L.len);

end;

4.双链表的插入操作(插入新结点q)

p:=loc(L,I);

new(q);

q^.data:=x;

q^.pre:=p;

q^.next:=p^.next;

p^.next:=q;

q^.next^.pre:=q; 5.双链表的删除操作

p:=loc(L,I); {p为要删除的结点} p^.pre^.next:=p^.next;

p^.next^.pre:=p^.pre;

dispose(p);

关键路径(最长路经):

var a,b:array [1..10,1..10] of integer;

n,last,out:integer;

q,c:array [1..10] of integer;

o:set of 1..10;

procedure init;

var i,j:integer;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

last:=0;

o:=[]; out:=0;

b:=a;

end;

procedure sort;

var i,j:integer;

p:boolean;

begin

while out<>n do begin

for i:=1 to n do

if not (i in o) then begin

p:=true;

for j:=1 to n do

if a[j,i]=1 then begin

p:=false;

break;

end;

if p then begin

inc(last);

q[last]:=i;

inc(out);

o:=o+;

fillchar(a,sizeof(a),0);

end;

end;

end;

end;

procedure work_1;

var i,j,t,k:integer;

begin

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

for i:=1 to n do begin

k:=0;

for j:=1 to i-1 do

if (a[q[j],q]>0) and (a[q[j],q]+c[q[j]]>k)

then k:=a[q[j],q]+c[q[j]];

c[q]:=k;

end;

end;

procedure work_2;

var i,j,k:integer;

begin

writeln(q[n]);

for i:=n-1 downto 1 do begin

k:=maxint;

for j:=i+1 to n do

if (a[q,q[j]]>0) and (c[q[j]]-a[q,q[j]]

if c[q]=k then writeln(q,' ');

c[q]:=k;

end;

end;

begin

init;

sort;

work_1;

work_2;

end.

拓扑排序:

var a:array [1..100,1..100] of 0..1;

n:integer;

p:set of 1..100;

procedure init;

var i,j,k:integer;

begin

fillchar(a,sizeof(a),0);

readln(n);

for i:=1 to n do begin

read(k);

while k<>0 do begin

a[i,k]:=1;

read(k);

end;

end;

p:=[];

end;

procedure search;

var i,j,t,sum,printed:integer;

begin

printed:=0;

while printed

for i:=1 to n do begin

sum:=0;

for j:=1 to n do sum:=sum+a[j,i];

if (sum=0) and not(i in p) then begin

write(i,' ');

p:=p+;

inc(printed);

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

end;

end;

end;

begin

init;

search;

end.

Pascal基础知识

一、初识Pascal语言 一、Pascal 语言概述 Pascal 语言是一种算法语言,它是瑞士苏黎世联邦工业大学的Niklaus Wirth教授于1968年设计完成的,1971年正式发表。1975年对Pascal 语言进行了修改,作为“标准PASCAL语言”。 Pascal 语言是一种结构化的程序设计语言,可以用来编写应用程序。它又是一种系统程序设计语言,可以用来编写顺序型的系统软件(如编译程序)。它的功能强、编译程序简单。 二、Pascal 语言的特点 Pascal语言有以下几个主要的特点: ⒈它是结构化的语言。Pascal语言提供了直接实现三种基本结构的语句以及定义“过程”和“函数”的功能。可以方便地书写出结构化程序。在编写程序时可以完全不使用GOTO语句和标号。这就易于保证程序的正确性和易读性。Pascal语言强调的是可靠性、易于验证性、概念的清晰性和实现的简化。在结构化这一点上,比其它(如 BASIC,FORTRAN77)更好一些。 ⒉有丰富的数据类型。Pascal提供了整数、实型、字符型、布尔型、枚举型、子界型、数组类型、集合类型、记录类型、和文件类型和指针类型。⒊能适用于数值运算和非数值运算领域。PASCAL的功能较强,能广泛应用于各种领域。PASCAL语言还可以用于辅助设计,实现计算机绘图功能。 ⒋ PASCAL程序的书写格式比较自由。PASCAL允许一行写多个语句,一个语句可以分写在多行上,这样就可以使PASCAL程序写得格式优美,便于阅读。 三、Pascal语言程序的基本结构 程序设计语言都有着一组自己的记号和规则。PASCAL语言必须采用其本身所规定的记号和规则来编写程序。下面我们首先来了解Pascal语言的程序基本结构。 Pascal语言的程序结构为: 程序首部 标号说明语句 常量定义语句 类型定义语句程序的说明部分 变量说明语句 函数和过程说明语句分程序 程序体程序的执行部分 先看一个简单的PASCAL程序: program exam1(input,output); var r,s,c:real; begin readln(r); c:=3.14*2*r; s:=3.14*r*r; writeln(c,s) end.

pascal 过程与函数教程

第十二课过程与函数 前面我们曾经学习了程序设计中的三种基本控制结构(顺序、分支、循环)。用它们可以组成任何程序。但在应用中,还经常用到子程序结构。 通常,在程序设计中,我们会发现一些程序段在程序的不同地方反复出现,此时可以将这些程序段作为相对独立的整体,用一个标识符给它起一个名字,凡是程序中出现该程序段的地方,只要简单地写上其标识符即可。这样的程序段,我们称之为子程序。 子程序的使用不仅缩短了程序,节省了内存空间及减少了程序的编译时间,而且有利于结构化程序设计。因为一个复杂的问题总可将其分解成若干个子问题来解决,如果子问题依然很复杂,还可以将它继续分解,直到每个子问题都是一个具有独立任务的模块。这样编制的程序结构清晰,逻辑关系明确,无论是编写、阅读、调试还是修改,都会带来极大的好处。在一个程序中可以只有主程序而没有子程序(本章以前都是如此),但不能没有主程序,也就是说不能单独执行子程序。pascal中子程序有两种形式:函数和过程。 一、函数 在此之前,我们曾经介绍并使用了pascal提供的各种标准函数,如ABS,SUCC等等,这些函数为我们编写程序提供了很大的方便。但这些函数只是常用的基本函数,编程时经常需要自定义一些函数。 (一)函数的说明 在pascal中,函数也遵循先说明后使用的规则,在程序中,函数的说明放在调用该函数的程序(主程序或其它子程序)的说明部分。函数的结构主程序的结构很相似。 函数定义的一般格式: function <函数名> (<形式参数表>):<类型>; {函数首部} 说明: ①函数由首部与函数体两部分组成。 ②函数首部以关键字function开头。 ③函数名是用户自定义的标识符。 ④函数的类型也就是函数值的类型,所求得的函数值通过函数名传回调用它的程序。可见,函数的作用一般是为了求得一个值。 ⑤形式参数简称形参,形参即函数的自变量。自变量的初值来源于函数调用。在函数中,形参一般格式如下: 变量名表1:类型标识符1;变量名表2:类型标识符2;…;变量名表n:类型标识符n 可见形参表相当于变量说明,对函数自变量进行说明,但应特别注意:此处只能使用类型标识符,而不能直接使用类型。 ⑥当缺省形参表(当然要同时省去一对括号)时,称为无参函数。 ⑦函数体与程序体基本相似,由说明部分和执行部分组成。 ⑧函数体中的说明部分用来对本函数使用的标号、常量、类型、变量、子程序加以说明,这些量只在本函数内有效。 ⑨函数体的执行部分由begin开头,end结束,中间有若干用分号隔开的语句,只是end后应跟分号,不能像程序那样用句号"."。 ⑩在函数体的执行部分,至少应该给函数名赋一次值,以使在函数执行结束后把函数值带回调用程序。 (二)函数的调用

汇编语言程序设计

汇编语言基础《汇编语言程序设计》第01章在线测试 A B C D 、微机中每个存储单元具有一个地址,其中存放一个____量。 A B C D 、设段地址为5788H,该字节的物理地址_____。 A B C D 、汇编语言源程序中,每个语句由项组成,不影响语句功能的是_____。 A B C D 、下列标号不合法的是_____。 A B C D

B、生成的代码序列短小 C、运行速度快 D、编程容易 E、便于移植 2、8086段寄存器有_______。 A、IP B、DS C、CS D、ES E、SS 3、使用MASM 6.x版本的“ML /Fl eg101.asm”命令,如果源程序eg101.asm没有语法错误,则将生成_________文件。 A、目标代码文件 B、可执行文件 C、列表文件 D、调试文件 E、库文件 4、汇编语言中,______可以作为有效的名字,如标号、变量名等。 A、0fffh B、var00 C、loop1 D、test E、add 5、汇编语言中,程序员不能将______作为用户标识符。 A、DS

正确错误、有效地址是指存储器操作数的物理地址。 正确错误、采用汇编语言书写的一个源程序文件,需要使用汇编程序,例如MASM 正确错误 按逻辑段组织程序,需要执行的指令应该在代码段中。 正确错误、使用简化段定义源程序格式,必须具有语句,且位于所有简化段定义语句之前。 正确错误 《汇编语言程序设计》第02章在线测试 A B C D

2、伪指令DW定义的是______量的变量。 A、字节 B、字 C、双字 D、4字 3、将变量var定义如下,“var db 26h, 4ah”,欲以字属性存取该变量值,应采用______var。 A、offset B、byte ptr C、word ptr D、seg 4、语句“xyz db ˊABˊ, ˊCDˊ, ˊEˊ,ˊFˊ”汇编后占用的存储空间是______个字节。 A、4 B、5 C、6 D、8 5、在伪指令语句“number dw 1234h”中的number 项称为______。 A、标号 B、操作符 C、名字 D、操作数 第二题、多项选择题(每题2分,5道题共10分) 1、如下________寻址方式的操作数来自主存储器。 A、立即数寻址 B、寄存器寻址 C、直接寻址 D、寄存器相对寻址 E、寄存器间接寻址 2、“mov [bx+10h],al”指令的两个操作数采用的寻址方式有_______。 A、寄存器间接 B、寄存器 C、寄存器相对 D、基址变址 E、立即数

【汇编语言程序设计】试题及答案合集

《汇编语言程序设计试题及答案》合集 汇编语言程序设计试题及答案 1.对于有符号的数来说,下列哪个值最大(D) A:0F8H B:11010011B C:82 D:123Q 2.下列有关汇编语言中标号的命名规则中,错误的是(D) A:通常由字母打头的字符、数字串组成 B:标号长度不能超过31个字符 C:?和$不能单独作为标号 D:.号不可位于标号首 3.8088/8086存储器分段,每个段不超过(D ) A.64K个字 B.32K个字节 C.1兆个字节 D.64K个字节 4.寻址指令MOV CX, [BX + DI + 20]使用的是哪一种寻址方式(B)A:寄存器寻址B:相对基址变址寻址 C:变址寻址D:基址变址寻址 5.若AX= - 15要得到AX=15应执行的指令是(A ) A.NEG AX B.NOT AX C.INC AX D.DEC AX 6.8086/8088系统执行传送指令MOV时( A) A.不影响标志位 B.影响DF方向标志 C.影响SF符号标志 D.影响CF进位标志 7.若要求一个操作数中的若干位维持不变,若干位置?1?,可以使用(B)A:NOT B:OR C:AND D:XOR 8.下列指令中段默认为堆栈段的是( C) A.MOV AX,[BX+SI+10] B.ADD AX,ES:[SI] C.SUB [BX],[BP][DI] D. MOV DX,[1000H] 9.关于8086/8088微机系列,下列说法哪个是正确的(D) A:一个存储单元由16个二进制位组成,简称字。

B:当存储一个字数据时,低字节放高地址位,高字节放低地址位。 C:在内存空间中,可以无限分配段,且段的大小不受限制。 D:段与段之间可以邻接,也可以重叠。 10.下列关于堆栈的说法,错误的是(D) A:以?先入后出?为原则。 B:栈区最高地址单元的前一个单元为栈底。 C:运行中SP寄存器动态跟踪栈顶位置。 D:压栈和弹出都是以字节为单位。 11.表示过程定义结束的伪指令是( A) A.ENDP B.ENDS C.END D.ENDM 12.BUF1 DB 3 DUP(0,2 DUP (1,2),3) COUNT EQU $-BUF1 符号COUNT等价的值是( B) A.6 B.18 C.16 D.9 13.下列标志位中,可以用来判断计算结果正负的是(B) A:PF B:SF C:DF D:OF 14.下列指令正确的是( CD) A. MOV [100H], [BX] B.MOV DS, ES C. ADD V[BX], CX D.MOV AX, 34H 15.下列哪个寄存器是属于指针寄存器(C) A:SI B:DX C:SP D:ES 二、填空题 (每小题4 分,共 20 分) 1.下列程序段求数组FLD的平均值,结果在AL中。请将程序填写完整(不考虑溢出) FLD DW 10, -20, 30, -60, -71, 80, 79, 56 _LEA SI,FLD______ MOV CX, 8 XOR AX, AX

pascal算法题

算法应用综合测试(二) (作答时间:3小时) 说明:1、作题前先在D盘新建一个文件夹,以自已的“学校+姓名”命名 2、各程序的源文件名、输入输出文件见题目 第一题杨辉三角(yh.pas) 【问题描述】 输出杨辉三角第n行。 【输入数据】 一个整数n,表示要输出杨辉三角的第n行。 【输出数据】 一行,杨辉三角的第n行,两个数之间用空格隔开。 【数据范围】 对于30%数据,0

某一天,tenshi看了一本趣味数学书,上面提到了亲和数:定义数对 (x,y) 为亲和数对当且仅仅当x、y为不同正整数,且x、y各自的所有非自身正因子之和等于另一个数。例如 (220,284) 和 (280,224) 都是亲和数对,因为: 220的所有非自身正因子之和为:1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 284的所有非自身正因子之和为:1 + 2 + 4 + 71 + 142 = 220 数对 (x,y ) 跟 (y,x) 被认为是同一数对,所以我们只考虑 x

汇编语言程序设计

汇编语言程序设计 一、选择题 (共72题) 1、 用于指针及变址寄存器的有()。 A、 AX,BX,CX,DX B、 SP,BP,IP C、 CS,DS,SS D、 PSW 考生答案:B 2、 完成把汇编语言源程序模块转换为目标模块的程序是()。 A、 编辑程序 B、 汇编程序 C、 连接程序 D、 调试程序 考生答案:B 3、 指令JMP FAR PTR DONE中的寻址方式属于()。 A、 段内转移直接寻址 B、 段内转移间接寻址 C、 段间转移直接寻址 D、 段间转移间接寻址 考生答案:C 4、 对于下列程序段: AGAIN:MOV AL,[SI]

MOV ES:[DI],AL INC SI INC DI LOOP AGAIN 也可用()指令完成同样的功能。 A、 REP MOVSB B、 REP LODSB C、 REP STOSB D、 REPE SCASB 考生答案:A 5、 在程序执行过程中,IP寄存器中始终保存的是()。 A、 上一条指令的首地址 B、 下一条指令的首地址 C、 正在执行指令的首地址 D、 需计算有效地址后才能确定地址 考生答案:B 6、 在汇编语言程序的开发过程中使用宏功能的顺序是()。 A、 宏定义,宏调用 B、 宏定义,宏展开 C、 宏定义,宏调用,宏展开 D、 宏定义,宏展开,宏调用 考生答案:C 7、 CPU要访问的某一存储单元的实际地址称()。 A、 段地址

偏移地址 C、 物理地址 D、 逻辑地址 考生答案:C 8、 AND、OR、XOR、NOT为四条逻辑运算指令,下面解释正确的是()。 A、 指令XOR AX,AX执行后,AX内容不变,但设置了标志位 B、 指令OR DX,1000H执行后,将DX最高位置1,其余各位置0 C、 指令AND AX,OFH执行后,分离出AL低四位 D、 NOT AX,执行后,将AX清0 考生答案:C 9、 完成对CL寄存器的内容乘以2的正确操作是()。 A、 ROL CL,1 B、 MUL 2 C、 SHL CL,1 D、 SHR CL,1 考生答案:C 10、 检查两个无符号数的关系,若要实现AL≥BL时分支去LOP1处,那么在“CMP A L,BL”指令后应跟的分支指令是()。 A、 JE LOP1 B、 JAE LOP1 C、 JC LOP1 D、 JGE LOP1 考生答案:B 11、 已知变量VAR为字型,则TYPEVAR=()。

PASCAL语言程序设计

目录 第一部分 PASCAL语言程序设计 (1) 第一章 PASCAL语言基础 (1) 第一节程序的组成与上机调试运行 (2) 第二节常量、变量与数据类型 (3) 第三节表达式与标准函数 (6) 第四节赋值语句、输入与输出语句 (9) 习题 (12) 第二章程序的三种基本结构 (15) 第一节顺序结构 (15) 第二节选择结构 (15) 第三节循环结构 (17) 习题 (20) 第三章数组 (22) 第一节一维数组 (22) 第二节二维数组及应用 (25) 习题 (26) 第四章字符与字符串操作 (29) 第一节字符和字符数组 (29) 第二节字符串变量 (29) 第三节字符串应用举例 (31) 习题 (33) 第五章函数与过程 (35) 第一节自定义函数 (35) 第二节自定义过程 (38) 第四节递归 (42) 第五节递归与回溯 (45) 习题 (50) 第一部分 PASCAL语言程序设计 第一章 PASCAL语言基础 Pascal语言是瑞士苏黎士工科大学的Niklans Wirth(沃思)1971年发表的,是为了纪念17世纪法国著名哲学和数学研究者Blaisc Pascal而将它命名为Pascal程序设计语言。Pascal语言是信息学奥赛中普遍使用的程序设计语言。

第一节程序的组成与上机调试运行 一、程序的组成 我们先看一道例题。 例1-1 输入两个整数a和b,计算a和b的和(a+b)。 【参考程序】 program a1(input,output); //程序首部 var a,b,c:integer; //程序说明部分,a,b,c被说明为整型变量 begin //程序执行部分,下面是程序的内容 write('a='); //在屏幕上输出一个字符串“a=”,输出完后不换行 read(a); //从键盘输入一个数值赋给变量a write('b='); //在屏幕上输出一个字符串“b=”,输出完后不换行 read(b); //从键盘输入一个数值赋给变量b c:=a+b; //计算a+b的和,并将这个和赋值给变量c writeln(a,'+',b,'=',c); //输出a+b=c的等式,输出完后换行 end. //程序结束 【样例输入】 a=10 b=30 【样例输出】 10+30=40 由上可以看出,一个Pascal程序由以下三部分组成: (1)由Program 引导的一行是Pascal程序的首部。 程序首部指出了源程序的名称,是由用户自己给出的,该例子称为a1。程序名后用括号括住的两个参数input与output,通常表示程序运行中的标准输入和输出文件,程序首部以分号结束。 (2)Pascal程序的第二部分是说明部分。 说明部分要求列出程序中引用的全部常量、变量、转移标号、类型、过程和函数的有关说明。若变量c在说明部分没有说明,后边的语句c:=a+b在执行时;翻译软件便能指出其错误并提醒用户加以改正,程序中每个语句都以分号表示结束。 (3)程序的第三个部分是用BEGIN和END括住的一串语句,称为程序的执行部分。有的书中将说明部分和执行部分合称为程序体。 二、PASCAL语言编辑软件的基本操作 下面我们以Free Pascal 1.10系统为例来学习一下Pascal语言编辑软件的使用。 1.Free Pascal的启动 在运行程序目录下(一般是c:\pp\bin\go32v2)运行启动程序fp.exe,即可启动系统。屏幕上出现如图1-1所示的集成环境。 图1-1 2.Free Pascal系统集成开发环境(IDE)简介 最顶上一行为主菜单,中间蓝色框内为编辑窗口,在编辑窗口内可以进行程序的编辑,最底下一行为提示行,显示出系统中常用命令的快捷键,如将当前编辑窗口中文件存盘的命令快捷键为F2,打开磁盘文件命令F3,等等。

汇编语言程序设计(第四版)第3章【课后答案】

汇编语言程序设计第四版 【课后习题答案】--囮裑為檤 第3章汇编语言程序格式 〔习题3.1〕伪指令语句与硬指令语句的本质区别是什么?伪指令有什么主要作用? 〔解答〕 伪指令语句与硬指令语句的本质区别是能不能产生CPU动作; 伪指令的作用是完成对如存储模式、主存变量、子程序、宏及段定义等很多不产生CPU动作的说明,并在程序执行前由汇编程序完成处理。 〔习题3.2〕什么是标识符,汇编程序中标识符怎样组成? 〔解答〕 为了某种需要,每种程序语言都规定了在程序里如何描述名字,程序语言的名字通常被称为标识符; 汇编语言中的标识符一般最多由31个字母、数字及规定的特殊符号(如-,$,?,@)组成,不能以数字开头。 〔习题3.3〕什么是保留字,汇编语言的保留字有哪些类型,并举例说明。 〔解答 保留字是在每种语言中规定了有特殊意义和功能的不允许再做其它用处的字符串;汇编语言的保留字主要有硬指令助记、伪指令助记符、运算符、寄存器名以及预定义符号等。汇编语言对大小写不敏感。如定义字节数和字符串的DB就是伪指令助记符。 〔习题3.4〕汇编语句有哪两种,每个语句由哪4个部分组成? 〔解答〕 汇编语句有执行性语句和说明性语句; 执行性语句由标号、硬指令助记符、操作数和注释四部分组成; 说明性语句由名字、伪指令助记符、参数和注释四部分组成 〔习题3.5〕汇编语言程序的开发有哪4个步骤,分别利用什么程序完成、产生什么输出文件。 〔解答〕 ⒈编辑文本编辑程序汇编语言源程序.asm ⒉汇编汇编程序目标模块文件.obj ⒊连接连接程序可执行文件.exe或.com

⒋调试调试程序应用程序 〔习题3.6〕区分下列概念: (1)变量和标号 (2)数值表达式和地址表达式 (3)符号常量和字符串常量 〔解答〕 (1)变量是在程序运行过程中,其值可以被改变的量;标号是由用户自定义的标识符,指向存储单元,表示其存储内容的逻辑地址。 (2)数值表达式一般是由运算符连接的各种常数所构成的表达式,地址表达式是由名字、标号以及利用各种的操作符形成的表达式。 (3)在程序中,为了使常量更便于使用和阅读,经常将一些常量用常量定义语句定义为符号常量,被一对双引号括起来的若干个字符组成的字符序列被称为字符串常量。 〔习题3.7〕假设myword是一个字变量,mybyte1和mybyte2是两个字节变量,指出下列语句中的错误原因。 (1)mov byte ptr [bx],1000 (2)mov bx,offset myword[si] (3)cmp mybyte1,mybyte2 (4)mov al,mybyte1+mybyte2 (5)sub al,myword (6)jnz myword 〔解答〕 (1)1000超出了一个字节范围 (2)寄存器的值只有程序执行时才能确定,而offset是汇编过程计算的偏移地址,故无法确定,改为lea bx,myword[si] (3)两个都是存储单元,指令不允许 (4)变量值只有执行时才确定,汇编过程不能计算 (5)字节量AL与字量myword,类型不匹配 (6)Jcc指令只有相对寻址方式,不支持间接寻址方式 〔习题3.8〕OPR1是一个常量,问下列语句中两个AND操作有什么区别? AND AL,OPR1 AND 0feh 〔解答〕

汇编语言程序设计

汇编语言程序设计 实验报告 实验名称上机过程及顺序结构与分支结构程序设计实验班级 学号 姓名 日期2017年10月26号 成绩 评阅人 软件学院

一、实验目的与意义 理解并熟练掌握汇编语言程序设计过程中的编辑、汇编、链接和调试等各个步骤,提高对汇编课程内容的理解和汇编语言的掌握,通过上机练习加深对课程内容的理解和掌握。通过汇编语言编制的程序上机调试、运行检验程序设计是否正确。熟悉和掌握编辑、汇编、连接和调试四个实用程序的使用方法,掌握调试程序中的几个常用命令的使用方法。熟悉其基本的指令操作,debug调试操作命令以及分支结构、顺序结构和循环结构的程序设计。 二、实验环境 操作系统:Microsoft Windows8 集成环境:Masm for Windows 上机地点:信息楼B405教室 三、实验的预习内容 预习的主要内容: 1. 使用DEBUG命令的方法; 2. 熟悉掌握从理论上定义数据的类型(即DB,DW,DD,); 3. 分支结构和顺序结构的步骤以及相关的指令; 4. 常用的标志位状态及相应的作用; 实验思路: 在对题目进行分析后,分析出解题方法,并做出与实验思路相对应的程序框图。依照程序框图的内容输入相对应的代码,最终在调试代码后,发现并解决一系列的汇编语言错误。进一步优化算法。实验之前必须了解十进制、十六进制和ASCII码之间的转换。预习查表法相关命令,掌握顺序程序的结构,从键盘输入数据的命令及显示到屏幕上的命令。 实验一: 题目1:将程序编辑、汇编、连接并通过集成环境中的debug调试,观察运行结果;用E命令修改指定地址的数据,再用G命令执行程序查看变化,用A 命令将加法指令修改成减法指令,再将其编译运行,查看寄存器值变化的异同。 题目2:分别用DB、DW和DD数据段9H,0FAH,41H,27H,编译链接之后生成exe文件,再用debug的r命令找到数据段地址,用d命令指定数据段地址,观察汇编后在机器内部对应的存储情况。 实验二: 先设置数据段地址和堆栈段地址;设置堆栈段指针;读取一个字符然后存储在AL中;用BX来存储AL中字符对应的数值;将BX中的值作为偏移地址;并在数据段中查找对应字符串;最终输出结果结束程序。 实验三: 先初始化数据段地址与堆栈段地址;设置堆栈段指针;然后将数据段中的data1放入AL中;读取数据段中的data2并判断data2是否大于0;然后读取数

pascal 基本算法

基本算法模块 对于NOIP,基础是相当重要的,在3个小时之内做完4道题,那么就要求我们有相当快的速度。特别是对于一些简单的、常用的算法模块,一定要要熟练掌握并灵活运用。由于NOIP是一个比较基础的比赛,因此基本算法的掌握尤为重要,所以要求能够把这些基本的模块快速、准确的移植到不同的程序中,才能在稳中取胜。 基本算法模块中最重要的是基本程序框架,也就是说,要养成适合于自己的程序风格,这样对于程序编写的速度与程序的准确度都有较大的提高。

模块目录 一、排序 1.选择排序 2.插入排序 3.冒泡排序 4.快速排序 5.堆排序 6.归并排序 7.线性时间排序二、高精度 1.高精度比较 2.高精度加法 3.高精度减法 4.单精度乘法 5.高精度乘法 6.单精度除法 7.高精度除法 8.进制转换 三、数论 1.欧几里德算法 2.扩展欧几里德 3.求最小公倍数 4.求解线形同余方程 5.素数的判断 6.素数的生成 四、排列组合 1.排列生成算法 2.组合生成算法 3.排列按序生成法 4.排列字典序生成法五、图论 1.图的读入 2.深度优先搜索 3.广度优先搜索 4.强连同分量 5.拓扑排序 6.最小生成树 7.最短路径 六、背包问题 1.装满背包 2.一维价值最大背包 3.二位价值最大背包

一、排序算法 var a:array[1..maxn]of longint;——排序对象 1.选择排序——Select_sort procedure select_sort; begin for i:=1to n-1do for j:=i+1to n do if a[i]>a[j]then begin temp:=a[i];a[i]:=a[j];a[j]:=temp;end; end; 2.插入排序——Insert_sort procedure insert_sort; begin for i:=2to n do begin key:=a[i];j:=i-1; while(key0)do begin a[j+1]:=a[j];dec(j);end; a[j+1]:=key; end; end; 3.冒泡排序——Bubble_sort procedure bubble_sort; begin for i:=1to n-1do for j:=n downto i+1do if a[j]x do dec(j);{找右边比他小的} if i<=j then{交换} begin temp:=a[i];a[i]:=a[j];a[j]:=temp;

新版汇编语言程序设计习题答案(钱晓捷主编)

新版汇编语言程序设计习题答案(钱晓捷主编) 第一章汇编语言基础知识 1.1、简述计算机系统的硬件组成及各部分作用 1.2、明确下列概念或符号: 主存和辅存,RAM和ROM,存储器地址和I/O端口,KB、MB、GB和TB 1.3、什么是汇编语言源程序、汇编程序、目标程序? 1.4、汇编语言与高级语言相比有什么优缺点? 1.5、将下列十六进制数转换为二进制和十进制表示 (1)FFH (2)0H (3)5EH (4)EFH (5)2EH (6)10H (7)1FH (8)ABH 1.6、将下列十进制数转换为BCD码表示 (1)12 (2)24 (3)68 (4)127 (5)128 (6)255 (7)1234 (8)2458 1.7、将下列BCD码转换为十进制数 (1)10010001 (2)10001001 (3)00110110 (4)10010000 (5)00001000 (6)10010111 (7)10000001 (8)00000010 1.8、将下列十进制数分别用8位二进制数的原码、反码和补码表示 (1)0 (2)-127 (3)127 (4)-57 (5)126 (6)-126 (7)-128 (8)68 1.9、完成下列二进制数的运算 (1)1011+1001 (2)1011-1001 (3)1011×1001 (4)10111000÷1001 (5)1011 ∧~1011 (8)1011 ⊕1001 1001(6)1011 ∨1001(7) 1.10 数码0~9、大写字母A~Z、小写字母a~z对应的ASCII码分别是多少?ASCII码为0dh、0ah对应的是什么字符? 1.11、计算机中有一个“01100001”编码,如果把它认为是无符号数,它是10进制什么数?如果认为它是BCD码,则表示什么数?又如果它是某个ASCII码,则代表哪个字符? 1.12、简述Intel 80x86系列微处理器在指令集方面的发展。 1.13、什么是DOS和ROM-BIOS? 1.14、简述PC机最低1MB主存空间的使用情况。 1.15、罗列8086CPU的8个8位和16位通用寄存器,并说明各自的作用。 1.16、什么是标志,它有什么用途?状态标志和控制标志有什么区别?画出标志寄存器FLAGS,说明各个标志的位置和含义。

Tarjan算法 Pascal语言描述

Tarjan算法Pascal语言描述 Tarjan算法Pascal语言描述 TonyShaw 那天做了个2-sat题,里面牵扯到求有向图的强连通分量,我这么弱,显然不会,于是从网上找求有向图的强连通分量的方法,有一个是DFS两遍,同时建原图与补图,算法名字是B???忘掉了,反正当时同时看见了Tarjan算法。鉴于我对于Tarjan的略微崇拜,于是想先学一下Tarjan。写这篇文章的原因在于,我在网上没有找到Pascal语言描述的程序,同时一些关于这个算法的解释不是很清楚,所以我想写一下,算是我对该算法理解的总结,也算是为其他要学习该算法的人提供点无用的参照吧。 算法思想:从一个点开始,进行深度优先遍历,同时记录到达该点的时间(dfn记录到达i 点的时间),和该点能直接或间接到达的点中的最早的时间(low记录这个值,其中low的 初始值等于dfn)。(如图。假设我们从1开始DFS,那么到达1的时间为1,到达2的时间为2,到达3的时间为3。同时,点1能直接或间接到达的点中,最小时间为1,点2能通过3间接到达点1,所以点2可到达最早的点时间为1,点3可以直接到达点1,故点3到达的最早的点的时间为1。)。对于每一个没有被遍历到的点A,如果从当前点有一条到未遍历点A的有向边,则遍历到A,同时将点A入栈,时间戳+1并用dfn[a]记录到达点A的时间,枚举从A发出的每一条边,如果该边指向的点没有被访问过,那么继续dfs,回溯后low[a]:=min(low[a],low[j])(其中j为A可以到达的点。)如果该点已经访问过并且该点仍在栈里,那么low[a]=min(low[a],dfn[j])。 解释:若点j没有被访问过,那么回溯后low[j]就是j能到达最早点,a能到达的最早点当然就是a本身能到达的最早点,或者a通过j间接到达的最早点。若点j已经被访问过,那么low[j]必然没有被回溯所更新。所以low[a]就等于a目前能到达的最小点或a直接到达点j 时点j的访问时间。注意:两个句子中的“或”其实指的是两者的最小值。那么如果我们回溯

PASCAL程序设计

第一章PASCAL程序设计基础 我们日常工作、学习和生活中,要做某件事,如果事先没有计划,只是想一步做一步,是达不到理想效果的。要很好地、高效率地完成某件事,必须事先有一个计划,第一步做什么,下一步做什么,最后一步做什么。即先考虑好做这件事的所有步骤,然后按部就班地完成它。在计算机系统中,能完成某项任务的一系列指令或语句就是程序。程序设计是设计、书写和调试程序的过程。 第一节程序设计语言及算法 一、程序设计语言 人们使用计算机,可以通过某种计算机语言与其交谈,用计算机语言描述所要完成的工作。为了完成某项特定任务用计算机语言编写的一组指令序列就称之为程序。编写程序和执行程序是利用计算机解决问题的主要方法和手段。程序设计语言是用来书写计算机程序的语言。程序设计语言经历了机器语言、汇编语言、高级语言到面向对象的程序设计语言等多个阶段。 1.机器语言 机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活、直接执行和速度快等特点。 用机器语言编写程序,编程人员要首先熟记所用计算机的全部指令代码和代码的涵义。手编程序时,程序员得自己处理每条指令和每一数据的存储分配和输入输出,还得记住编程过程中每步所使用的工作单元处在何种状态。这是一件十分繁琐的工作,编写程序花费的时间往往是实际运行时间的几十倍或几百倍。而且编出的程序全是些0和1的指令代码,直观性差,还容易出错。现在,除了计算机生产厂家的专业人员外,绝大多数程序员已经不再去学习机器语言了。 2.汇编语言 为了克服机器语言难读、难编、难记和易出错的缺点,人们就用与代码指令实际含义相近的英文缩写词、字母和数字等符号来取代指令代码(如用ADD表示运算符号“+”的机器代码),于是就产生了汇编语言。汇编语言是一种用助记符表示的仍然面向机器的计算机语言。汇编语言像机器指令一样,是硬件操作的控制信息,因而仍然是面向机器的语言,使用起来还是比较繁琐费时,通用性也差。汇编语言是低级语言。 3.高级语言 20世纪50年代后期,在对低级语言的改进过程中,又研制出一种既接近于自然语言,又接近数学语言的程序设计语言。使用这种语言编写程序快捷方便,便于修改和高度,大大提高了编程的效率,同时这种语言编写的程序不依赖具体的机器,能用性好,我们称之为高级语言。用高级语言,不必考虑机器的结构和特点,可以集中精力考虑解决问题的算法,因此,高级语言也称为算法语言。 4.面向对象的程序设计语言

新版汇编语言程序设计钱晓捷第1章习题答案

第1章汇编语言基础知识(全) 2010-10-18 19:32:40| 分类:答案集锦| 标签:|字号大中小订阅 第1章汇编语言基础知识 〔习题1.1〕简述计算机系统的硬件组成及各部分作用。 〔解答〕 CPU:包括运算器、控制器和寄存器组。运算器执行所有的算术和逻辑运算;控制器负责把指指令逐条从存储器中取出,经译码分析后向机器发出各种控制命令,并正确完成程序所要求的功能;寄存器组为 处理单元提供所需要的数据。 存储器:是计算机的记忆部件,它用来存放程序以及程序中所涉及的数据。 外部设备:实现人机交换和机间的通信。 〔习题1.2〕明确下列概念或符号: 主存和辅存,RAM和ROM,存储器地址和I/O端口,KB、MB、GB和TB 〔解答〕 主存又称内存是主存储器的简称,主存储器存放当前正在执行的程序和使用的数据,CPU可以直接存取,它由半导体存储器芯片构成其成本高、容量小、但速度快。辅存是辅助存储器的简称,辅存可用来长期保存大量程序和数据,CPU需要通过I/O接口访问,它由磁盘或光盘构成,其成本低、容量大,但速 度慢。 RAM是随机存取存储器的英语简写,由于CPU可以从RAM读信息,也可以向RAM写入信息,所以RAM也被称为读写存储器,RAM型半导体存储器可以按地址随机读写,但这类存储器在断电后不能保存信息;而ROM中的信息只能被读出,不能被修改,ROM型半导体通常只能被读出,但这类存储器断电 后能保存信息。 存储器由大量存储单元组成。为了区别每个单元,我们将它们编号,于是,每个存储单元就有了一个存储地址,I/O接口是由一组寄存器组成,为了区别它们,各个寄存器进行了编号,形成I/O地址,通常 称做I/O端口。 KB是千字节、MB是兆字节、GB是吉字节和TB是太字节,它们都是表示存储器存储单元的单位。 〔习题1.3〕什么是汇编语言源程序、汇编程序、目标程序? 〔解答〕 用汇编语言书写的程序就称为汇编语言源程序;完成汇编工作的程序就是汇编程序;由汇编程序编 译通过的程序就是目标程序。

PASCAL语法解释

我是在高一接触pascal语言,因为参加NOI的需要,顺理成章的要使用Turbo Pascal来写程序了。半年后,我开始想着如何编写Windows程序,又理所当然的找上Delphi。初见Delphi,除了begin,end 让我觉得倍感亲切外,Object Pascal里的增加的面向对象的语法却让我很是吃惊,当时的我可根本不懂什么叫面向过程,面向对象;最可恶的是,国内那些教育家们,除了会拿着清华的那本精简的不能再精简的pascal教材照本宣科外,似乎再也没有什么实质性的工作了,传说中的《Turbo Pascal大全》更是无处可寻,所以关于unit,interface这些Delphi里随处可见的关键字我也很不明白。所幸,其后不久,我得到一本名为《计算机反病毒技术》的书,里面统统都是用Turbo Pascal编写的源代码,通过它我迅速明白了早已存在于Turbo Pascal中unit,interface等关键字的含义和用法,又以Delphi中的Help文档为扶手,开始蹒跚学步了。 印象中,国内Delphi作家似乎更偏爱编写应用实例类的技术书籍,至于语法这种东西,没有几个人愿意多去涉及,即使书中必须谈及,也是寥寥数笔,匆匆带过,或者干脆与某本书类似。对Object Pascal语法讲解最好,最权威的恐怕就算《Delphi5开发人员指南》了,这本书至今也是备受推崇的。但与如今泛滥的C++书籍相比,Delphi仍然逊色许多,也难怪很多新手特别是从来没有接触过pascal语言的新手,在学习Object Pascal时会遇到不少困难。自己的感觉是:在从Turbo Pascal向Delphi过渡的过程中,由于没有正确的指引,走了很多弯路;由于没有正确的桥梁,必须要一步实现大跨越。所以,在这里,我提出自己曾经遇见的沟壑,路标性给出我自己的认识和总结,希望给入门的同学们一些帮助。我不打算详细介绍语法知识,并假设你已经有一点pascal语言和面向对象概念的基础。要想学习相关详细知识,我推荐各位一定要阅读《Delphi开发人员指南》和Delphi Help文档中的相关章节。 ●记录体和类 习惯了在一个Program模块内写完所有面向过程代码的我,有几天的时间一直未能彻底明白在非Unit模块中,非继承的自定义类的框架,语法是如何的,VCL源代码虽然经典,却过于繁杂,不能让我迅速掌握根本,我需要一个最简单又最能说明问题,完整的可运行的代码,苦于无处寻求答案,只好亲自动手,探索对应关系,终成其下两段代码。 program TP;{本代码在Turbo Pascal7.0下编译通过} type MyRecord=record {...} end; var MR:MyRecord; procedure Procedure1; begin {Procedure1Code} end; {===========main===========} begin {以这个begin为标志,主程序开始,其作用相当于C/C++中的main函数} Procedure1; end.

汇编语言程序设计

实验四程序设计 一、实验目的 学习数据传送指令和算术运算指令的用法;掌握数据定义伪指令的格式,会用DEBUG 中的D命令观察DB、DW、DD存储数据的格式;熟悉汇编语言的基本框架,掌握编写汇编语言程序的基本方法。 二、实验题 1、已知当前数据段中DADT1和DADT2开始分别存放若干字节数据,数据个数相同,编制程序检查两数据块中数据是否相同,若相同,则在屏幕上显示1,否则显示0。 【参考程序如下】 DSEG SEGMENT DATA1 DB 'ABCDEFG3' DATA2 DB 'ABCDEF3G' CNT DW 8 DSEG ENDS CSEG SEGMENT ASSUME CS:CSEG,DS:DSEG START:MOV AX,DSEG MOV DS,AX MOV DL,31H LEA SI,DATA1 LEA DI,DATA2 MOV CX,CNT DEC SI DEC DI AGAIN:INC SI INC DI MOV AL,[SI] CMP AL,[DI] LOOPZ AGAIN JZ DISP DEC DL DISP: MOV AH,2

INT 21H MOV AH,4CH INT 21H CSEG ENDS END START 阅读程序,理解循环程序结构及执行过程,并改成串指令实现。 2 编写程序,将00H~0FH共16个数写入内存3000H开始的连续16个存储单元中。 三、实验报告 写出程序清单,记录运行结果。 改写串指令实现: DSEG SEGMENT DATA1 DB'ABCDEFG3' DATA2 DB'ABCDEF3G' CNT DW8 DSEG ENDS CSEG SEGMENT ASSUME CS:CSEG,DS:DSEG START:MOV AX,DSEG MOV DS,AX MOV ES,AX MOV DL,31H LEA SI,DATA1 LEA DI,DATA2 MOV CX,CNT CLD

汇编语言程序设计

汇编语言程序设计 课程介绍 1.属于低级语言的程序设计 2.硬件类课程和操作系统先行课 3.软件开发的一个组成部分(加密解密、逆向工程、有害代码的分析防治) 4.高级语言程序设计的扩展(硬件资源的管理、驱动等) 5.对计算机专业:专业基础课、必修课 第一章汇编语言基础知识 §1.1计算机语言基本概念 一、机器语言:(0、1代码) 1.机器指令:是指挥计算机完成某一基本操作的命令,是由硬件电路设计决定的,也叫硬指令。由操作码和地址码组成。 2.指令系统:每台计算机所特有的、全部指令的集合构成该CPU的指令系统。 3.机器语言程序:机器指令的集合构成了机器语言,用机器语言编写的程序就是机器语言程序。 4.特点:计算机能直接识别,执行速度快,但难于记忆、识别和编写。 二、汇编语言: 1.汇编指令:用便于记忆、并能描述指令功能的符号表示的机器指令。 2.汇编程序:就是把汇编语言源程序翻译成机器语言程序的一种系统软件。 3.汇编语言:汇编指令、伪指令、宏指令和汇编程序一起组成了汇编语言。 4.特点:汇编指令与机器指令一一对应,相对机器语言易于理解、掌握。汇编语言直接面向机器,用汇编语言编制的程序简洁、快速。 三、高级语言:

1.高级语言:机器语言和汇编语言以外的程序设计语言统称高级语言。 2.特点:其特点是更加接近自然语言和惯用的数学表达形式,与计算机硬件结构无关,因而便于使用,便于交流和推广。高级语言编程效率高,但运行效率低。 3.高级语言需要使用编译程序和解释程序将源程序翻译成机器语言程序,然后交计算机执行。 §1.2数据表示与运算 一、位计数制: 1.位权表示法:每位的位权与该位的数值相乘后相加得到该数的数值。 2.十进制:逢十进一,用0、1、2、3、4、5、6、7、8、9十个数码表示。(D) 二进制:逢二进一,用0、1两个数码表示。(B) 八进制:逢八进一,用0、1、2、3、4、5、6、7八个数码表示。(Q) 十六进制:逢十六进一,用0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F十六个数码表示。(H) 二、不同数制之间的转化: 1.非十进制数转化为十进制: 1011100.1011B=1×26+0×25+1×24+1×23+1×22+0×21+0×20+1×2-1+0×2-2+1×2-3+1×2—4=92.6875D 1001.2Q=1×83+0×82+0×81+1×80+2×8-1 A031.2H=10×163+0×162+3×161+1×160+2×16-1=41009.125D 2.十进制转化为非十进制数: 十进制数转化位二进制数: 整数部分:除2取余,倒序排列得到的整数。 2 13 (1) 2 6 0

相关文档 最新文档