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©;
while c< >'';'' do
case c of
''+'',''-'': begin
while (t2 >0) and (s2[t2]< >''('') do calcu;
inc(t2);s2[t2]:=c;
read©;
end ;
''*'',''/'':begin
if (t2 >0) and ((s2[t2]=''*'') or (s2[t2]=''/'')) then calcu;
inc(t2);s2[t2]:=c;
read©;
end;
''('':begin inc(t2); s2[t2]:=c; read©; end;
'')'':begin
while s2[t2]< >''('' do calcu;
dec(t2); read©;
end;
''0''..''
