演算法案例開發

㈠ 搜索演算法的應用案例

(1)題目：黑白棋游戲
黑白棋游戲的棋盤由4×4方格陣列構成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一種放置方案都構成一個游戲狀態。在棋盤上擁有1條公共邊的2個方格稱為相鄰方格。一個方格最多可有4個相鄰方格。在玩黑白棋游戲時，每一步可將任何2個相鄰方格中棋子互換位置。對於給定的初始游戲狀態和目標游戲狀態，編程計算從初始游戲狀態變化到目標游戲狀態的最短著棋序列。
(2)分析
這題我們可以想到用深度優先搜索來做，但是如果下一步出現了以前的狀態怎麼辦？直接判斷時間復雜度的可能會有點大，這題的最優解法是用廣度優先搜索來做。我們就可以有初始狀態按照廣度優先搜索遍歷來擴展每一個點，這樣到達目標狀態的步數一定是最優的（步數的增加時單調的）。但問題是如果出現了重復的情況我們就必須要判重，但是樸素的判重是可以達到狀態數級別的，其實我們可以考慮用hash表來判重。
Hash表：思路是根據關鍵碼值進行直接訪問。也就是說把一個關鍵碼值映射到表中的一個位置來訪問記錄的過程。在Hash表中，一般插入，查找的時間復雜度可以在O（1）的時間復雜度內搞定。對於這一題我們可以用二進制值表示其hash值，最多2^16次方，所以我們開個2^16次方的表記錄這個狀態出現沒有，這樣可以在O（1）的時間復雜度內解決判重問題。
進一步考慮：從初始狀態到目標狀態，必定會產生很多無用的狀態，那還有什麼優化可以減少這時間復雜度？我們可以考慮把初始狀態和目標狀態一起擴展，這樣如果初始狀態的某個被擴展的點與目標狀態所擴展的點相同時，那這兩個點不用擴展下去，而兩個擴展的步數和也就是答案。
上面的想法是雙向廣度優先搜索：
就像圖二一樣，多擴展了很多不必要的狀態。
從上面一題可以看到我們用到了兩種優化方法，即Hash表優化和雙向廣搜優化。一般的廣度優先搜索用這兩個優化就足以解決。

㈡ 工資演算法是什麼呢

工資演算法及舉例如下。

1、正演算法：工資=月薪÷21.75×月計薪天數×(出勤天數比例)。

2、反演算法：工資＝月薪－月薪÷21.75x缺勤天數×(出勤天數比例）。

3、月計薪天數＝（月出勤天數＋法定節假日天數）。

4、出勤天數比例＝21.75÷(當月應出勤天數＋法定節假日天數）。

5、同樣舉上面的案例。

案例一：某員工月薪2175，7月份有23個工作日，員工缺勤1天，出勤是22天，本月月薪多少。

正演算法：2175÷21.75×22×(21.75÷23)=2080.4。

反演算法：2175—2175÷21.75×1×(21.75÷23)=2080.4。

案例二：某員工月薪2175元，5月份有21個工作日，5.1為法定節假日，員工缺勤1天，出勤是20天，本月月薪多少。

正演算法：2175÷21.75×(20+1)×(21.75÷(21+1))=2076.14。

反演算法：2175—2175÷21.75×1×(21.75÷(21+1))=2076.14。

㈢ 求經典的遞歸演算法以及案例（可用C#、PHP、JAVA其中一種語言來寫）!

我用C#來寫（注意，更多的請直接到我的個人博客，點擊， http://www.cnblogs.com/serviceboy/archive/2009/07/19/1526590.html，收看） 【例1】有甲、乙、丙、丁四人，從甲開始到丁，一個比一個大1歲，已知丁10歲，問甲幾歲？【分析】這是遞歸法的一道非常典型的題目——因為我們可以很顯然知道：假設要計算甲的年齡，那麼必須直到乙的年齡；同樣，算乙的必須直到丙的，算丙的必須知道丁的，因為丁已知，自然可以往前推算了。現在假設有一個數學模型（函數）可以計算出他們各自的年齡（方便期間我們給他們編號——甲＝1，乙＝2，丙＝3，丁＝4），那麼存在這一個F(X)函數，X表示某人的編號，其規律如下：F(1)=F(2)+1F(2)=F(3)+1F(3)=F(4)+1F(4)=10顯然，直到X=4的時候是一個終止值，其餘情況下都是返回F(X』)，F(X』』)……F(X』』……』)，且前者總是比後至大1，這也符合了X』和X總是呈現一定函數關系（設想一下，如果不是等差和等比，又怎麼可能在一個遞歸函數中進行計算？要知道，函數本身就是一個公式表示，既然是公式，那麼一定是一種函數關系Y=F(X)），此處顯然X和X』的關系是X=X』+1。根據規律式，我們可以寫出該遞歸函數：int AgeCal(int id)
{
if(id==4) return 10;
else
return (AgeCal(id+1)+1);
} 【例2】計算n！【分析】雖然這道題目不像例1一樣清晰明了告訴你使用「遞歸」法反推，但是我們有這樣一個常識——n！＝(n-1)!*n；(n-1)!=(n-2)!*(n-1)……n=0或1，返回1.顯然n與n-1，n-2也是線性的遞減數列（等差關系）。其規律如下：F(n)=F(n-1)*nF(n-1)=F(n-2)*(n-1)F(n-2)=F(n-3)*(n-2)……F(1)=1或者F(0)=1(防止別人直接輸入0)編寫其遞歸函數，如下：int Fac(int n)
{
if(n==1 || n==0)
{
return 1;
}
else
return Fac(n-1)*n;
} 【例3】求一組整數中的最大(小)值（整數是一個int[]數組，個數未知）。【分析】當數字只有兩個的時候，我們可以使用>和<直接比較；但是當數字超過2個的時候（假設3個），那麼我們可以使用一個預訂的函數（比如Max(1,2)和3進行比較），由於1，2兩個數比較的時候已經得到一個最大值，因此在回代到Max中又變成了兩個數的比較。這樣，我們可以發現一個規律：F(1,2,3,4……n)＝F(1,2,3,4……n-1)和n比較F(1,2,3,4……n-1)＝F(1,2,3,4……n-2)和n-1比較……F(1,2,3)=F(1,2)和3比較F(1,2)＝結果（並回代）相應的遞歸函數如下(C#)：Code
int Max(int[]numbers)
{
if(numbers.Length==2)
{
return (numbers[0]>numbers[1]?numbers[0]:numbers[1]);
}
else
{
int[]tempnumbers=new int[numbers.Length-1];
for(int i=0;i<numbers.Length-1;++i)
{
tempnumbers[i]=numbers[i];
}
return (Max(tempnumbers)>numbers[numbers.Length-1]? Max(tempnumbers): numbers[numbers.Length-1]
}
}