計算機的算法具有可行性,有窮性、輸入\輸出、確定性。
計算機算法特點
1.有窮性。一個算法應包含有限的操作步驟,而不能是無限的。事實上“有窮性”往往指“在合理的范圍之內”。如果讓計算機執行一個歷時1000年才結束的算法,這雖然是有窮的,但超過了合理的限度,人們不把他視為有效算法。
2.確定性。算法中的每一個步驟都應當是確定的,而不應當是含糊的、模棱兩可的。算法中的每一個步驟應當不致被解釋成不同的含義,而應是十分明確的。也就是說,算法的含義應當是唯一的,而不應當產生“歧義性”。
3.有零個或多個輸入、所謂輸入是指在執行算法是需要從外界取得必要的信息。
4.有一個或多個輸出。算法的目的是為了求解,沒有輸出的算法是沒有意義的。
5.有效性。算法中的每一個步驟都應當能有效的執行。并得到確定的結果。
拓展資料:重要算法
A*搜尋算法
俗稱A星算法。這是一種在圖形平面上,有多個節點的路徑,求出最低通過成本的算法。常用于游戲中的NPC的移動計算,或線上游戲的BOT的移動計算上。該算法像Dijkstra算法一樣,可以找到一條最短路徑;也像BFS一樣,進行啟發式的搜索。
Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法,它是在分枝定界方法基礎上發展起來的,它使用啟發式方法估計k個最好的路徑,僅從這k個路徑出發向下搜索,即每一層只有滿意的結點會被保留,其它的結點則被永久拋棄,從而比分枝定界法能大大節省運行時間。束搜索于20世紀70年代中期首先被應用于人工智能領域,1976年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是并行地搜索幾個潛在的最優決策路徑以減少回溯,并快速地獲得一個解。
二分取中查找算法
一種在有序數組中查找某一特定元素的搜索算法。搜索過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜索過程結束;如果某一特定元素大于或者小于中間元素,則在數組大于或小于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。這種搜索算法每一次比較都使搜索范圍縮小一半。
Branch and bound
分支定界(branch and bound)算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同,分支定界算法采用廣度優先或最小耗費優先的方法搜索解空間樹,并且,在分支定界算法中,每一個活結點只有一次機會成為擴展結點。
數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗余度,達到增大數據密度,最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網絡帶寬的擴展。
Diffie–Hellman密鑰協商
Diffie–Hellman key exchange,簡稱“D–H”,是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在后續的通訊中作為對稱密鑰來加密通訊內容。
Dijkstra’s算法
迪科斯徹算法(Dijkstra)是由荷蘭計算機科學家艾茲格·迪科斯徹(Edsger Wybe Dijkstra)發明的。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說,如果圖中的頂點表示城市,而邊上的權重表示著城市間開車行經的距離,迪科斯徹算法可以用來找到兩個城市之間的最短路徑。
動態規劃
動態規劃是一種在數學和計算機科學中使用的,用于求解包含重疊子問題的最優化問題的方法。其基本思想是,將原問題分解為相似的子問題,在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎,被廣泛應用于計算機科學和工程領域。比較著名的應用實例有:求解最短路徑問題,背包問題,項目管理,網絡流優化等。這里也有一篇文章說得比較詳細。
歐幾里得算法
在數學中,輾轉相除法,又稱歐幾里得算法,是求最大公約數的算法。輾轉相除法首次出現于歐幾里得的《幾何原本》(第VII卷,命題i和ii)中,而在中國則可以追溯至東漢出現的《九章算術》。
最大期望(EM)算法
在統計計算中,最大期望(EM)算法是在概率(probabilistic)模型中尋找參數最大似然估計的算法,其中概率模型依賴于無法觀測的隱藏變量(Latent Variable)。最大期望經常用在機器學習和計算機視覺的數據聚類(Data Clustering)領域。最大期望算法經過兩個步驟交替進行計算,第一步是計算期望(E),利用對隱藏變量的現有估計值,計算其最大似然估計值;第二步是最大化(M),最大化在 E步上求得的最大似然值來計算參數的值。M步上找到的參數估計值被用于下一個 E步計算中,這個過程不斷交替進行。
快速傅里葉變換(FFT)
快速傅里葉變換(Fast Fourier Transform,FFT),是離散傅里葉變換的快速算法,也可用于計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用,如數字信號處理、計算大整數乘法、求解偏微分方程等等。
哈希函數
HashFunction是一種從任何一種數據中創建小的數字“指紋”的方法。該函數將數據打亂混合,重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字符串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中,不抑制沖突來區別數據,會使得數據庫記錄更難找到。
堆排序
Heapsort是指利用堆積樹(堆)這種數據結構所設計的一種排序算法。堆積樹是一個近似完全二叉樹的結構,并同時滿足堆積屬性:即子結點的鍵值或索引總是小于(或者大于)它的父結點。
歸并排序
Merge sort是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。
RANSAC算法
RANSAC是”RANdom SAmpleConsensus”的縮寫。該算法是用于從一組觀測數據中估計數學模型參數的迭代方法,由Fischler and Bolles在1981提出,它是一種非確定性算法,因為它只能以一定的概率得到合理的結果,隨著迭代次數的增加,這種概率是增加的。該算法的基本假設是觀測數據集中存在”inliers”(那些對模型參數估計起到支持作用的點)和”outliers”(不符合模型的點),并且這組觀測數據受到噪聲影響。RANSAC假設給定一組”inliers”數據就能夠得到最優的符合這組點的模型。
RSA加密演算法
這是一個公鑰加密算法,也是世界上第一個適合用來做簽名的算法。今天的RSA已經專利失效,其被廣泛地用于電子商務加密,大家都相信,只要密鑰足夠長,這個算法就會是安全的。
并查集Union-find
并查集是一種樹型的數據結構,用于處理一些不相交集合(Disjoint Sets)的合并及查詢問題。常常在使用中以森林來表示。
Viterbi algorithm
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。
參考資料:計算機算法計算機算法是對計算機上執行的計算過程的具體描述,或者說是以一步一步的方式來描述計算機如何將輸入轉化為所要求的輸出的過程。計算機算法具有以下五個特性:
1、有窮性:一個計算機算法應包含有限的操作步驟,而不能是無限的。事實上“有窮性”往往指“在合理的范圍之內”,超過了合理的限度,人們把他視為無效算法。
2、確定性:計算機算法中的每一個步驟都應當是確定的,而不應當是含糊的、模棱兩可的。也就是說,計算機算法的含義應當是唯一的,而不能當產生“歧義性”。
3.、有零個或多個輸入:計算機算法輸入是指在執行算法是需要從外界取得必要的信息。
4、有一個或多個輸出:計算機算法的目的是為了求解,沒有輸出的算法是沒有任何意義的。
5、有效性:計算機算法中的每一個步驟都應保證能有效的執行,并得到確定的結果。
擴展資料
一個計算機算法除了具備上述5個特性,還應具備以下4個條件:
1、計算機算法首先必須是正確的,即對于任意的一組輸入,包括合理的輸入與不合理的輸入,總能得到預期的輸出。
2、計算機算法必須是由一系列具體步驟組成的,并且每一步都能夠被計算機所理解和執行,而不是抽象和模糊的概念。
3、計算機算法的每一個步驟都有確定的執行順序,即上一步在哪里,下一步是什么,都必須明確。
4、無論一個計算機算法有多復雜,都必須在有限步驟之后終止運行,即步驟必須是有限的。在任何情況下,都不能陷入無限循環中。
參考資料來源:百度百科-計算機算法
這是我們計算機系算法設計課的實驗課程,下面是動態規劃內容:
實驗四:動態規劃
實驗目的:理解動態規劃的基本思想,理解動態規劃算法的兩個基本要素最優子結構性質和子問題的重疊性質。熟練掌握典型的動態規劃問題。掌握動態規劃思想分析問題的一般方法,對較簡單的問題能正確分析,設計出動態規劃算法,并能快速編程實現。
實驗內容:編程實現講過的例題:最長公共子序列問題、矩陣連乘問題、凸多邊形最優三角剖分問題、電路布線問題等。本實驗中的問題,設計出算法并編程實現。
習題
1.最長公共子序列
一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說,若給定序列X=
解答如下:
a)最長公共子序列的結構
若用窮舉搜索法,耗時太長,算法需要指數時間。
易證最長公共子序列問題也有最優子結構性質
設序列X=
i.若xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列;
ii.若xm≠yn且zk≠xm,則Z是Xm-1和Y的最長公共子序列;
iii.若xm≠yn且zk≠yn,則Z是X和Yn-1的最長公共子序列。
其中Xm-1=
最長公共子序列問題具有最優子結構性質。
b)子問題的遞歸結構
由最長公共子序列問題的最優子結構性質可知,要找出X=
由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如,在計算X和Y的最長公共子序列時,可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題,即計算Xm-1和Yn-1的最長公共子序列。
我們來建立子問題的最優值的遞歸關系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=
c)計算最優值
由于在所考慮的子問題空間中,總共只有θ(m*n)個不同的子問題,因此,用動態規劃算法自底向上地計算最優值能提高算法的效率。
計算最長公共子序列長度的動態規劃算法LCS_LENGTH(X,Y)以序列X=
程序如下:
#include
#include
int lcs_length(char x[], char y[]);
int main()
{
char x[100],y[100];
int len;
while(1)
{
scanf("%s%s",x,y);
if(x[0]=='0')//約定第一個字符串以‘0’開始表示結束
break;
len=lcs_length(x,y);
printf("%d\n",len);
}
}
int lcs_length(char x[], char y[])
{
int m,n,i,j,l[100][100];
m=strlen(x);
n=strlen(y);
for(i=0;i l[i][0]=0; for(j=0;j l[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(x[i-1]==y[j-1])//i,j從1開始,但字符串是從0開始 l[i][j]=l[i-1][j-1]+1; else if(l[i][j-1]>l[i-1][j]) l[i][j]=l[i][j-1]; else l[i][j]=l[i-1][j]; return l[m][n]; } 由于每個數組單元的計算耗費Ο(1)時間,算法lcs_length耗時Ο(mn)。 思考:空間能節約嗎? 2.計算矩陣連乘積 在科學計算中經常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數等于矩陣B的行數。若A是一個p×q的矩陣,B是一個q×r的矩陣,則其乘積C=AB是一個p×r的矩陣。由該公式知計算C=AB總共需要pqr次的數乘。其標準計算公式為: 現在的問題是,給定n個矩陣{A1,A2,…,An}。其中Ai與Ai+1是可乘的,i=1,2,…,n-1。要求計算出這n個矩陣的連乘積A1A2…An。 遞歸公式: 程序如下: #include int main() { int p[101],i,j,k,r,t,n; int m[101][101];//為了跟講解時保持一致數組從1開始 int s[101][101];//記錄從第i到第j個矩陣連乘的斷開位置 scanf("%d",&n); for(i=0;i<=n;i++) scanf("%d",&p[i]);//讀入p[i]的值(注意:p[0]到p[n]共n+1項) for(i=1;i<=n;i++)//初始化m[i][i]=0 m[i][i]=0; for(r=1;r for(i=1;i { j=i+r;//j為列 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//給m[i][j]賦初值 s[i][j]=i; for(k=i+1;k { t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t { m[i][j]=t;//m[i][j]取最小值 s[i][j]=k; } } } printf("%d",m[1][n]); } 3.凸多邊形的最優三角剖分 多邊形是平面上一條分段線性的閉曲線。也就是說,多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接頂點外沒有別的公共點,則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分:被包圍在多邊形內的所有點構成了多邊形的內部;多邊形本身構成多邊形的邊界;而平面上其余的點構成了多邊形的外部。當一個簡單多邊形及其內部構成一個閉凸集時,稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內部或邊界上。 通常,用多邊形頂點的逆時針序列來表示一個凸多邊形,即P= 若vi與vj是多邊形上不相鄰的兩個頂點,則線段vivj稱為多邊形的一條弦。弦將多邊形分割成凸的兩個子多邊形 凸多邊形最優三角剖分的問題是:給定一個凸多邊形P= 可以定義三角形上各種各樣的權函數W。例如:定義ω(△vivjvk)=|vivj|+|vivk|+|vkvj|,其中,|vivj|是點vi到vj的歐氏距離。相應于此權函數的最優三角剖分即為最小弦長三角剖分。(注意:解決此問題的算法必須適用于任意的權函數) 4.防衛導彈 一種新型的防衛導彈可截擊多個攻擊導彈。它可以向前飛行,也可以用很快的速度向下飛行,可以毫無損傷地截擊進攻導彈,但不可以向后或向上飛行。但有一個缺點,盡管它發射時可以達到任意高度,但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現對這種新型防衛導彈進行測試,在每一次測試中,發射一系列的測試導彈(這些導彈發射的間隔時間固定,飛行速度相同),該防衛導彈所能獲得的信息包括各進攻導彈的高度,以及它們發射次序。現要求編一程序,求在每次測試中,該防衛導彈最多能截擊的進攻導彈數量,一個導彈能被截擊應滿足下列兩個條件之一: a)它是該次測試中第一個被防衛導彈截擊的導彈; b)它是在上一次被截擊導彈的發射后發射,且高度不大于上一次被截擊導彈的高度的導彈。 輸入數據:第一行是一個整數n,以后的n各有一個整數表示導彈的高度。 輸出數據:截擊導彈的最大數目。 分析:定義l[i]為選擇截擊第i個導彈,從這個導彈開始最多能截擊的導彈數目。 由于選擇了第i枚導彈,所以下一個要截擊的導彈j的高度要小于等于它的高度,所以l[i]應該等于從i+1到n的每一個j,滿足h[j]<=h[i]的j中l[j]的最大值。 程序如下: #include int main() { int i,j,n,max,h[100],l[100]; scanf("%d",&n); for(i=0;i scanf("%d",&h[i]); l[n-1]=1; for(i=n-2;i>=0;i--) { max=0; for(j=i+1;j if(h[i]>h[j]&&max max=l[j]; l[i]=max+1; } printf("%d",l[0]); } 5.石子合并 在一個圓形操場的四周擺放著n堆石子(n<= 100),現要將石子有次序地合并成一堆。規定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數,記為該次合并的得分。編一程序,由文件讀入堆棧數n及每堆棧的石子數(<=20)。 選擇一種合并石子的方案,使得做n-1次合并,得分的總和最小; 輸入數據: 第一行為石子堆數n; 第二行為每堆的石子數,每兩個數之間用一個空格分隔。 輸出數據: 從第一至第n行為得分最小的合并方案。第n+1行是空行.從第n+2行到第2n+1行是得分最大合并方案。每種合并方案用n行表示,其中第i行(1<=i<=n)表示第i次合并前各堆的石子數(依順時針次序輸出,哪一堆先輸出均可)。要求將待合并的兩堆石子數以相應的負數表示。 Sample Input 4 4 5 9 4 Sample Output -4 5 9-4 -8-5 9 -13-9 22 4-5-9 4 4-14-4 -4-18 22 6.最小代價子母樹 設有一排數,共n個,例如:22 14 7 13 26 15 11。任意2個相鄰的數可以進行歸并,歸并的代價為該兩個數的和,經過不斷的歸并,最后歸為一堆,而全部歸并代價的和稱為總代價,給出一種歸并算法,使總代價為最小。 輸入、輸出數據格式與“石子合并”相同。 Sample Input 4 12 5 16 4 Sample Output -12-5 16 4 17-16-4 -17-20 37 7.商店購物 某商店中每種商品都有一個價格。例如,一朵花的價格是2 ICU(ICU是信息學競賽的貨幣的單位);一個花瓶的價格是5 ICU。為了吸引更多的顧客,商店提供了特殊優惠價。特殊優惠商品是把一種或幾種商品分成一組。并降價銷售。例如:3朵花的價格不是6而是5 ICU;2個花瓶加1朵花是10 ICU不是12 ICU。 編一個程序,計算某個顧客所購商品應付的費用。要充分利用優惠價以使顧客付款最小。請注意,你不能變更顧客所購商品的種類及數量,即使增加某些商品會使付款總數減小也不允許你作出任何變更。假定各種商品價格用優惠價如上所述,并且某顧客購買物品為:3朵花和2個花瓶。那么顧客應付款為14 ICU因為: 1朵花加2個花瓶優惠價:10 ICU 2朵花正常價:4 ICU 輸入數據:第一個文件INPUT.TXT描述顧客所購物品(放在購物筐中);第二個文件描述商店提供的優惠商品及價格(文件名為OFF ER.TXT)。兩個文件中都只用整數。 第一個文件INPUT.TXT的格式為:第一行是一個數字B(0≤B≤5),表示所購商品種類數。下面共B行,每行中含3個數C,K,P。 C代表商品的編碼(每種商品有一個唯一的編碼),1≤C≤999。K代表該種商品購買總數,1≤K≤5。P是該種商品的正常單價(每件商品的價格),1≤P≤999。請注意,購物筐中最多可放5*5=25件商品。 第二個文件OFFER.TXT的格式為:第一行是一個數字S(0≤S≤9 9),表示共有S種優惠。下面共S行,每一行描述一種優惠商品的組合中商品的種類。下面接著是幾個數字對(C,K),其中C代表商品編碼,1≤C≤9 99。K代表該種商品在此組合中的數量,1≤K≤5。本行最后一個數字P(1≤ P≤9999)代表此商品組合的優惠價。當然,優惠價要低于該組合中商品正常價之總和。 輸出數據:在輸出文件OUTPUT.TXT中寫一個數字(占一行),該數字表示顧客所購商品(輸入文件指明所購商品)應付的最低貨款。 8.旅游預算 一個旅行社需要估算乘汽車從某城市到另一城市的最小費用,沿路有若干加油站,每個加油站收費不一定相同。旅游預算有如下規則: 若油箱的油過半,不停車加油,除非油箱中的油不可支持到下一站;每次加油時都加滿;在一個加油站加油時,司機要花費2元買東西吃;司機不必為其他意外情況而準備額外的油;汽車開出時在起點加滿油箱;計算精確到分(1元=100分)。編寫程序估計實際行駛在某路線所需的最小費用。 輸入數據:從當前目錄下的文本文件“route.dat”讀入數據。按以下格式輸入若干旅行路線的情況: 第一行為起點到終點的距離(實數) 第二行為三個實數,后跟一個整數,每兩個數據間用一個空格隔開。其中第一個數為汽車油箱的容量(升),第二個數是每升汽油行駛的公里數,第三個數是在起點加滿油箱的費用,第四個數是加油站的數量。(〈=50)。接下去的每行包括兩個實數,每個數據之間用一個空格分隔,其中第一個數是該加油站離起點的距離,第二個數是該加油站每升汽油的價格(元/升)。加油站按它們與起點的距離升序排列。所有的輸入都有一定有解。 輸出數據:答案輸出到當前目錄下的文本文件“route.out”中。該文件包括兩行。第一行為一個實數和一個整數,實數為旅行的最小費用,以元為單位,精確到分,整數表示途中加油的站的N。第二行是N個整數,表示N個加油的站的編號,按升序排列。數據間用一個空格分隔,此外沒有多余的空格。 Sample Input 516.3 38.09 1 15.7 22.1 20.87 3 2 125.4 1.259 297.9 1.129 345.2 0.999 Sample Output 38.09 1 2 9.皇宮看守 太平王世子事件后,陸小鳳成了皇上特聘的御前一品侍衛。皇宮以午門為起點,直到后宮嬪妃們的寢宮,呈一棵樹的形狀;某些宮殿間可以互相望見。大內保衛森嚴,三步一崗,五步一哨,每個宮殿都要有人全天候看守,在不同的宮殿安排看守所需的費用不同。可是陸小鳳手上的經費不足,無論如何也沒法在每個宮殿都安置留守侍衛。 請你編程計算幫助陸小鳳布置侍衛,在看守全部宮殿的前提下,使得花費的經費最少。 輸入數據:輸入數據由文件名為intput.txt的文本文件提供。輸入文件中數據表示一棵樹,描述如下: 第1行 n,表示樹中結點的數目。 第2行至第n+1行,每行描述每個宮殿結點信息,依次為:該宮殿結點標號i(0 對于一個n(0< n<= 1500)個結點的樹,結點標號在1到n之間,且標號不重復。 輸出數據:輸出到output.txt文件中。輸出文件僅包含一個數,為所求的最少的經費。 如右圖的輸入數據示例: Sample Input 6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0 Sample Output 25 10.游戲室問題 有一個游戲室里有多個游戲室,并且這每個游戲室里還有多個游戲室,每個游戲室里面還有游戲室,依此類推。進入每個游戲室都可得到一定的快樂,每個游戲室的門票價格都大于等于0,都有一個快樂值,并且只有進入了一個游戲室,才可以進入它內部的游戲室,小明現在有n元錢,問最大能得到多少的快樂。 11.*基因問題 已知兩個基因序列如s:AGTAGT;t:ATTAG。現要你給序列中增加一些空格后,首先使得兩個序列的長度相等,其次兩個串對應符號匹配得到的值最大。基因只有四種分別用A、G、C、T表示,匹配中不允許兩個空格相對應,任意兩符號的匹配值由下表給出: A G C T〕 A 5-2-1-2-4 G-2 5-4-3-2 C-1-4 5-5-1 T-2-3-5 5-2 〕-4-2-1-2 提示:定義問題l[i][j]為取第一個序列的前i項,和第二個序列的前j項,這兩個序列加空格匹配的最大值。它的最優值與三個子問題有關,l[i-1][j-1]、l[i][j-1]、l[i-1][j]。 建立遞歸公式如下: 其中m[0][t[j]表示表中空格和t[j]匹配的對應值。 思考:本問題的初始化。 12.*田忌賽馬 田忌與齊王賽馬,雙方各有n匹馬參賽(n<=100),每場比賽賭注為1兩黃金,現已知齊王與田忌的每匹馬的速度,并且齊王肯定是按馬的速度從快到慢出場,現要你寫一個程序幫助田忌計算他最好的結果是贏多少兩黃金(輸用負數表示)。 分析:先排序,齊王的馬的速度放在數組a中,田忌的馬的速度放在數組b中。本問題應用的算法是動態規劃和貪心算法相結合解決的。從兩人的最弱的馬入手: 若田忌的馬快,就讓這兩匹馬比賽; 若田忌的馬慢,干脆就讓他對付齊王最快的馬; 若兩匹馬的速度相等,這時有兩種選擇方案,或者它倆比賽,或者對付齊王最快的馬。 定義子問題:l(i,j)為齊王的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽,田忌所獲得的最大收益。 則: 程序具體實現時,為了適合c數據從0開始,稍加變動,定義子問題:l(i,j)為齊王的從第i匹馬開始到第i+j匹馬共j+1匹馬與田忌的最快的j+1匹馬比賽,田忌所獲得的最大收益。初始化時:l[i][0]表示齊王的第i匹馬與田忌最快的馬比賽的結果。 程序如下: #include void readdata(); void init(); int n,a[100],b[100],l[100][100]; int main() { int i,j; readdata(); init(); for(i=n-2;i>=0;i--) for(j=1;j if(a[i+j] l[i][j]=l[i][j-1]+1; else if(a[i+j]>b[j]) l[i][j]=l[i+1][j-1]-1; else if(l[i+1][j-1]-1>l[i][j-1]) l[i][j]=l[i+1][j-1]-1; else l[i][j]=l[i][j-1]; printf("%d",l[0][n-1]); } void readdata() { int i; scanf("%d",&n); for(i=0;i scanf("%d",&a[i]); for(i=0;i scanf("%d",&b[i]); } void init() { int i; // qsort(a,n);//略 for(i=0;i { if(a[i] l[i][0]=1; else if(a[i]==b[0]) l[i][0]=0; else l[i][0]=-1; } }