摘录地址：
http://vib.hit.edu.cn/vibbbs/dispbbs.asp?boardID=25&ID=2357&page=89.树的遍历顺序转换
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;
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(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;
树形查找
二*排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。
查找
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;