pascal.txt

pascal基本算法及优化(如数论问题单纯背包问题等)

end;{sort}  
　

B.插入排序： 
procedure insert_sort(k,m:word); {k为当前要插入的数，m为插入位置的指针} 
var i:word; p:0..1; 
begin 
p:=0; 
for i:=m downto 1 do 
if k=a[i] then exit; 
repeat 
If k >a[m] then begin 
a[m+1]:=k; p:=1; 
end 
else begin 
a[m+1]:=a[m]; dec(m); 
end; 
until p=1; 
end;{insert_sort} 
l 主程序中为： 
a[0]:=0; 
for I:=1 to n do insert_sort(b[I],I-1); 

C.选择排序： 
procedure sort; 
var i,j,k:integer; 
begin 
for i:=1 to n-1 do begin 
k:=i; 
for j:=i+1 to n do 
if a[j]< a[k] then k:=j; {找出a[I]..a[n]中最小的数与a[I]作交换} 
if k< >i then begin 
a[0]:=a[k];a[k]:=a[i];a[i]:=a[0]; 
end; 
end; 
end; 

D. 冒泡排序 
procedure sort; 
var i,j,k:integer; 
begin 
for i:=n downto 1 do 
for j:=1 to i-1 do 
if a[j] >a[i] then begin 
a[0]:=a[i];a[i]:=a[j];a[j]:=a[0]; 
end; 
end; 

E.堆排序： 
procedure sift(i,m:integer);{调整以i为根的子树成为堆,m为结点总数} 
var k:integer; 
begin 
a[0]:=a[i]; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1} 
while k< =m do begin 
if (k< m) and (a[k]< a[k+1]) then inc(k);{找出a[k]与a[k+1]中较大值} 
if a[0]< a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end 
else k:=m+1; 
end; 
a[i]:=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[i]< =a[j])) {满足取左边序列当前元素的要求} 
then begin 
tmp[t]:=a[i]; inc(i); 
end 
else begin 
tmp[t]:=a[j];inc(j); 
end; 
inc(t); 
end; 
for i:=p to r do a[i]:=tmp[i]; 
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.基数排序 
思想：对每个元素按从低位到高位对每一位进行一次排序 


8.高精度计算 
A. 
B. 
C. 
D. 

9.树的遍历顺序转换 
A. 已知前序中序求后序 
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; 

B.已知中序后序求前序 
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; 

C.已知前序后序求中序 

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[i]=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,length(post)-i-1)); 
end; 

10.求图的弱连通子图(DFS) 
procedure dfs ( now,color: integer); 
begin 
for i:=1 to n do 
if a[now,i] and c[i]=0 then begin 
c[i]:=color; 
dfs(I,color); 
end; 
end; 


11.拓扑排序 
寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO. 


12.进制转换 
A.整数任意正整数进制间的互化 

NOIP1996数制转换 
设字符串A$的结构为: A$='mp' 
其中m为数字串(长度< =20),而n,p均为1或2位的数字串(其中所表达的内容在2-10之间) 
程序要求:从键盘上读入A$后(不用正确性检查),将A$中的数字串m(n进制)以p进制的形式输出. 
例如:A$='48< 10 >8' 
其意义为:将10进制数48,转换为8进制数输出. 
输出结果:48< 10 >=60< 8 > 

B.实数任意正整数进制间的互化 
C.负数进制： 
NOIP2000 
设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负 进制下的数：-R∈{-2，-3，-4,....-20} 

13.全排列与组合的生成 
排列的生成：（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[i] then begin 
s:=s+chr(i+ord('0'));used[i]:=true; 
solve(dep+1); 
s:=copy(s,1,length(s)-1); used[i]:=false; 
end; 
end; 
组合的生成(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[i]) and (i >pre) then begin 
s:=s+chr(i+ord('0'));used[i]:=true; 
solve(dep+1,i); 
s:=copy(s,1,length(s)-1); used[i]:=false; 
end; 
end; 

　

14 递推关系 
计算字串序号模型 
USACO1.2.5 StringSobits 
长度为N (N< =31)的01串中1的个数小于等于L的串组成的集合中找出按大小排序后的第I个01串。 


数字划分模型 
*NOIP2001数的划分 
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。 
d[0,0]:=1; 
for p:=1 to n do 
for i:=p to n do 
for j:=k downto 1 do inc(d[i,j],d[i-p,j-1]); 
writeln(d[n,k]); 

*变形1：考虑顺序 
d[ i, j] : = d [ i-k, j-1] (k=1..i) 
*变形2：若分解出来的每个数均有一个上限m 
d[ i, j] : = d [ i-k, j-1] (k=1..m) 


15.算符优先法求解表达式求值问题 
const maxn=50; 
var 
s1:array[1..maxn] of integer; {s1为数字栈} 
s2:array[1..maxn] of char; {s2为算符栈} 
t1,t2:integer; {栈顶指针} 

procedure calcu; 
var 
x1,x2,x:integer; 
p:char; 
begin 
p:=s2[t2]; dec(t2); 
x2:=s1[t1]; dec(t1); 
x1:=s1[t1]; dec(t1); 
case p of 
'+':x:=x1+x2; 
'-':x:=x1-x2; 
'*':x:=x1*x2; 
'/':x:=x1 div 2; 
end; 
inc(t1);s1[t1]:=x; 
end; 

procedure work; 
var c:char;v:integer; 
begin 
t1:=0;t2:=0; 
read&copy;; 
while c< >';' do 
case c of 
'+','-': begin 
while (t2 >0) and (s2[t2]< >'(') do calcu; 
inc(t2);s2[t2]:=c; 
read&copy;; 
end ; 
'*','/':begin 
if (t2 >0) and ((s2[t2]='*') or (s2[t2]='/')) then calcu; 
inc(t2);s2[t2]:=c; 
read&copy;; 
end; 
'(':begin inc(t2); s2[t2]:=c; read&copy;; end; 
')':begin 
while s2[t2]< >'(' do calcu; 
dec(t2); read&copy;; 
end; 
'0'..'9':begin 
v:=0; 
repeat 
v:=10*v+ord&copy;-ord('0'); 
read&copy;; 
until (c< '0') or (c >'9'); 
inc(t1); s1[t1]:=v; 
end; 
end; 
while t2 >0 do calcu; 
writeln(s1[t1]); 
end;

16.查找算法 
折半查找 
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;  
树形查找 
二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。 
查找 
function treesrh(k:keytype):pointer; 
var q:pointer; 
begin 
q:=root; 
while (q< >nil) and (q^.key< >k) do 
if k< q^.key then q:=q^.left 
else q:=q^.right; 
treesrh:=q; 
end; 


17．KMP算法 

18．贪心 
*会议问题 
（1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。 
解：按每项活动的结束时间进行排序，排在前面的优先满足。 

（2）会议室空闲时间最少。 

（3）每个客户有一个愿付的租金，求最大利润。 

（4）共R间会议室，第i个客户需使用i间会议室，费用相同，求最大利润。 

附录1 常用技巧 
1.带权中位数 
我国蒙古大草原上有N（N是不大于100的自然数）个牧民定居点P1（X1，Y1）、P2（X2，Y2）、 …Pn（Xn，Yn），相应地有关权重为Wi，现在要求你在大草原上找一点P（Xp，Yp），使P点到任 一点Pi的距离Di与Wi之积之和为最小。 　　 
　　 即求 D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值 　　 
结论：对x与y两个方向分别求解带权中位数，转化为一维。 
设最佳点p为点k，则点k满足： 
令W为点k到其余各点的带权距离之和，则 
sigema( i=1 to k-1) Wi*Di < = W/2 
sigema( i=k+1 to n) Wi*Di < = W/2 
同时满足上述两式的点k即为带权中位数。 

2．求一序列中连续子序列的最大和 
begin 
maxsum:=-maxlongint; 
sum:=0; 
for i:=1 to n do begin 
inc(sum,data[i]); 
if sum >maxsum then maxsum:=sum; 
if sum< 0 then sum:=0; 
end; 
writeln(maxsum); 
end;  
 
 

posted on 2005-05-19 11