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