摘錄地址：
http://vib.hit.edu.cn/vibbbs/dispbbs.asp?boardID=25&ID=2357&page=89.樹的遍歷順序轉(zhuǎn)換??
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]; {加上根，遞歸結(jié)束后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)]; {加上根，遞歸結(jié)束后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;????
12.進制轉(zhuǎn)換??
A.整數(shù)任意正整數(shù)進制間的互化????
NOIP1996數(shù)制轉(zhuǎn)換??
設(shè)字符串A$的結(jié)構(gòu)為: A$='mp'??
其中m為數(shù)字串(長度< =20),而n,p均為1或2位的數(shù)字串(其中所表達的內(nèi)容在2-10之間)
程序要求:從鍵盤上讀入A$后(不用正確性檢查),將A$中的數(shù)字串m(n進制)以p進制的形式輸出.
例如:A$='48< 10 >8'?? 其意義為:將10進制數(shù)48,轉(zhuǎn)換為8進制數(shù)輸出.??
輸出結(jié)果:48< 10 >=60< 8 >????
B.實數(shù)任意正整數(shù)進制間的互化??
C.負(fù)數(shù)進制：?? NOIP2000?? 設(shè)計一個程序，讀入一個十進制數(shù)的基數(shù)和一個負(fù)進制數(shù)的基數(shù)，
并將此十進制數(shù)轉(zhuǎn)換為此負(fù) 進制下的數(shù)：-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個數(shù)的所有方案)??
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 遞推關(guān)系?? 計算字串序號模型?? USACO1.2.5 StringSobits??
長度為N (N< =31)的01串中1的個數(shù)小于等于L的串組成的集合中找出按大小排序后的第I個01串。
數(shù)字劃分模型
*NOIP2001數(shù)的劃分
將整數(shù)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：若分解出來的每個數(shù)均有一個上限m
d[ i, j] : = d [ i-k, j-1] (k=1..m)
15.算符優(yōu)先法求解表達式求值問題
const maxn=50;
var s1:array[1..maxn] of integer; {s1為數(shù)字棧}
????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(c);??
????while c< >';' do??
?????? case c of??
?????? '+','-':??
?????? begin??
?????????? while (t2 >0) and (s2[t2]< >'(') do calcu;??
?????????????? inc(t2);s2[t2]:=c;??
?????????????? read(c);??
?????? end ;??
?????? '*','/':??
?????? begin??
?????????? if (t2 >0) and ((s2[t2]='*') or (s2[t2]='/')) then calcu;??
?????????? inc(t2);s2[t2]:=c;??
?????????? read(c);??
?????? end;??
?????? '(':
?????? begin
?????????? inc(t2);
?????????? s2[t2]:=c;
?????????? read(c);
?????? end;??
?????? ')':??
?????? begin??
?????????? while s2[t2]< >
?????? '(' do calcu;??
?????????? dec(t2);
?????????? read(c);??
?????? end;??
?????? '0'..'9':??
?????? begin??
?????????? v:=0;??
?????????? repeat??
??????????????v:=10*v+ord(c)-ord('0');??
??????????????read(c);??
?????????? 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;????
樹形查找??
二*排序樹：每個結(jié)點的值都大于其左子樹任一結(jié)點的值而小于其右子樹任一結(jié)點的值。??
查找??
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;