[摘錄]一些基本算法2

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;????

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;

posted on 2006-05-24 13:15 見酒就暈 閱讀(244) 評論(0)  編輯  收藏 所屬分類: 算法