遞歸演算法的偽代碼表示

① 按要求設計遞歸演算法。只需寫出偽代碼或畫流程圖，不需語言實現，但演算法必須完整清晰。

開始的程序控制語句的基礎練習，如開頭：

酒店與多個循環，分支控制結構，以確定如何在控制台輸出三角形，倒三角形，等邊三角形，等腰三角形練習，正方形，長方形，平行四邊形，菱形，另一個是大多形狀。和盡可能從用戶輸入的參數來完成圖形輸出程序的適應。

包裝 - 被轉移到不同凡響，搜索演算法學習練習，如：遞歸演算法，帕斯卡三角形，冒泡，快速插入排序演算法，如運動。

- 以後，你可以學習Swing桌面開發的基本知識。使用Swing良好的設計，進一步學習Java語言來實現各種設計模式，比如Swing是最常見的模式，觀察者模式，單例模式，工廠模式，抽象工廠模式，等等。以後有限公司返回了，你可以學到一些知識的J2EE，如JSP，Servlet的，以及一些常用的框架如Hibernate，Spring中，Struts中，TopLink的，ibitas，DWR等上。

這些只是Java的知識，要想J2EE，還要學習HTML，JS，XML，CSS，AJAX和一些常見的富客戶端框架庫，如原型，ExtJS的，JQuery的，等。許多

學習內容，要循序漸進，以達到良好的效果。否則你不會得到一半。需要注意的是學習的過程中必須採取一些好的經驗（設計模式是公認的獲得經驗）學習，所以能迅速提高。

② 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(2)遞歸演算法的偽代碼表示擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

③ 請使用偽代碼編寫演算法: 要求分別用循環結構和遞歸結構求解n!。 n!= 1 當n=0 n!=n*(n--1)! 當n>0

遞歸
int fun(n){
if(n==0) return 1;

return n*(fun(n-1));

}
循環
int fun(n){
int result = 1;

if (n==0) return result;

for(int i=1;i<=n;i++){
result *= i;

}

return result;

}

④ 01背包問題

演算法分析

對於背包問題，通常的處理方法是搜索。
用遞歸來完成搜索，演算法設計如下：
function Make( i {處理到第i件物品} , j{剩餘的空間為j}:integer) :integer;
初始時i=m , j=背包總容量
begin
if i:=0 then
Make:=0;
if j>=wi then (背包剩餘空間可以放下物品 i )
r1:=Make(i-1,j-wi)+v; (第i件物品放入所能得到的價值 )
r2:=Make(i-1,j)(第i件物品不放所能得到的價值 )
Make:=max{r1,r2}
end;
這個演算法的時間復雜度是O(2^n)，我們可以做一些簡單的優化。
由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜索中會重復計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重復計算的話，速度就會提高很多。這是簡單?quot;以空間換時間"。
我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。
同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那麼第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。
考慮用動態規劃的方法來解決，這里的：
階段是：在前N件物品中，選取若干件物品放入背包中；
狀態是：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值；
決策是：第N件物品放或者不放；
由此可以寫出動態轉移方程：
我們用f[i,j]表示在前 i 件物品中選擇若干件放在所剩空間為 j 的背包里所能獲得的最大價值
f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c的背包中」，此時能獲得的最大價值就是f[v-c]再加上通過放入第i件物品獲得的價值w。
這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]
演算法設計如下：
procere Make;
begin
for i:=0 to w do
f[0,i]:=0;
for i:=1 to m do
for j:=0 to w do begin
f[i,j]:=f[i-1,j];
if (j>=w) and (f[i-1,j-w]+v>f[i,j]) then
f[i,j]:=f[i-1,j-w]+v;
end;
writeln(f[m,wt]);
end;
由於是用了一個二重循環，這個演算法的時間復雜度是O（n*w)。而用搜索的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那麼它的時間復雜度是O（2^n)。看上去前者要快很多。但是，可以發現在搜索中計算過的結點在動態規劃中也全都要計算，而且這里算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。
事實上，由於我們定下的前提是：所有的結點都沒有重疊。也就是說，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整數，那末這個時候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n -1
此時n*w>2^n，動態規劃比搜索還要慢~~|||||||所以，其實背包的總容量W和重疊的結點的個數是有關的。
考慮能不能不計算那些多餘的結點……
優化時間復雜度
以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[0..V]的所有值。那麼，如果只用一個數組f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[v]呢？f[v]是由f[v]和f[v-c]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環中推f[v]時）能夠得到f[v]和f[v-c]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c]保存的是狀態f[v-c]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c]+w};
其中的f[v]=max{f[v],f[v-c]}一句恰就相當於我們的轉移方程f[v]=max{f[v],f[v-c]}，因為現在的f[v-c]就相當於原來的f[v-c]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[v]由f[v-c]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。
事實上，使用一維數組解01背包的程序在後面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程，以後的代碼中直接調用不加說明。
過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數cost、weight分別表明這件物品的費用和價值。
procere ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示常式序寫成v=V..0是為了在程序中體現每個狀態都按照方程求解了，避免不必要的思維復雜度。而這里既然已經抽象成看作黑箱的過程了，就可以加入優化。費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的。
有了這個過程以後，01背包問題的偽代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c,w);
初始化的細節問題

我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿背包」時的最優解，有的題目則並沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那麼此時只有容量為0的背包可能被價值為0的nothing「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼任何容量的背包都有一個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
這個小技巧完全可以推廣到其它類型的背包問題，後面也就不再對進行狀態轉移之前的初始化進行講解