算法是一系列解決問題的清晰指令，也就是說，能夠對一定規範的輸入，在有限時間內獲得所要求的輸出。算法常常含有重複的步驟和一些比較或邏輯判斷。如果一個算法有缺陷，或不適合於某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法設計的優劣可以用空間複雜度與時間複雜度來衡量。
基本介紹
- 中文名：套用算法設計
- 外文名：Application algorithm design
- 學科：計算機科學
- 套用：解決實際問題的方法
簡介,設計方法,1.遞推法,2.遞歸,3.回溯法,4.貪婪法,5.分治法,6.動態規劃法,7.疊代法,8.窮舉搜尋法,簡單對比,代碼實現,
簡介
算法設計的好壞很大程式上要看實現算法的時間複雜度。
算法的時間複雜度是指算法需要消耗的時間資源。一般來說，計算機算法是問題規模n的函式f(n)，算法執行的時間的增長率與f(n)的增長率正相關，稱作漸進時間複雜度（AsymptoticTimeComplexity）。時間複雜度用“O（數量級）”來表示，稱為“階”。常見的時間複雜度有：O（1）常數階；O（log2n）對數階；O（n）線性階；O（n2）平方階。
算法的空間複雜度是指算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。
設計方法
1.遞推法
遞推法是利用問題本身所具有的一種遞推關係求問題解的一種方法。設要求問題規模為N的解，當N=1時，解或為已知，或能非常方便地得到解。能採用遞推法構造算法的問題有重要的遞推性質，即當得到問題規模為i-1的解後，由問題的遞推性質，能從已求得的規模為1，2，…，i-1的一系列解，構造出問題規模為I的解。這樣，程式可從i=0或i=1出發，重複地，由已知至i-1規模的解，通過遞推，獲得規模為i的解，直至得到規模為N的解。
【問題】階乘計算
問題描述：編寫程式，對給定的n（n≦100），計算並輸出k的階乘k！（k=1，2，…，n）的全部有效數字。
由於要求的整數可能大大超出一般整數的位數，程式用一維數組存儲長整數，存儲長整數數組的每個元素只存儲長整數的一位數字。如有m位成整數N用數組a[]存儲：
N=a[m]×10m-1+a[m-1]×10m-2+…+a[2]×101+a[1]×100
並用a[0]存儲長整數N的位數m，即a[0]=m。按上述約定，數組的每個元素存儲k的階乘k！的一位數字，並從低位到高位依次存於數組的第二個元素、第三個元素……。例如，5！=120，在數組中的存儲形式為：
3021……
首元素3表示長整數是一個3位數，接著是低位到高位依次是0、2、1，表示成整數120。
計算階乘k！可採用對已求得的階乘(k-1)！連續累加k-1次後求得。例如，已知4！=24，計算5！，可對原來的24累加4次24後得到120。細節見下節程式。
2.遞歸
遞歸是設計和描述算法的一種有力的工具，由於它在複雜算法的描述中被經常採用，為此在進一步介紹其他算法設計方法之前先討論它。
能採用遞歸描述的算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。
【問題】編寫計算斐波那契（Fibonacci）數列的第n項函式fib（n）。
斐波那契數列為：0、1、1、2、3、……，即：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2)（當n>1時）。
寫成遞歸函式有：
intfib(intn){
if(n==0)return0;
if(n==1)return1;
if(n>1)returnfib(n-1)+fib(n-2);
}
遞歸算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較複雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函式fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍複雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。
在編寫遞歸函式時要注意，函式中的局部變數和參數知識局限於當前調用層，當遞推進入“簡單問題”層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列“簡單問題”層，它們各有自己的參數和局部變數。
由於遞歸引起一系列的函式調用，並且可能會有一系列的重複計算，遞歸算法的執行效率相對較低。當某個遞歸算法能較方便地轉換成遞推算法時，通常按遞推算法編寫程式。例如上例計算斐波那契數列的第n項的函式fib(n)應採用遞推算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。
【問題】組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5，r=3的所有組合為：（1）5、4、3（2）5、4、2（3）5、4、1
（4）5、3、2（5）5、3、1（6）5、2、1
（7）4、3、2（8）4、3、1（9）4、2、1
（10）3、2、1
分析所列的10個組合，可以採用這樣的遞歸思想來考慮求組合函式的算法。設函式為voidcomb(intm,intk)為找出從自然數1、2、……、m中任取k個數的所有組合。當組合的第一個數字選定時，其後的數字是從餘下的m-1個數中取k-1數的組合。這就將求m個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題。設函式引入工作數組a[]存放求出的組合的數字，約定函式將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出後，才將a[]中的一個組合輸出。第一個數可以是m、m-1、……、k，函式將確定組合的第一個數字放入數組後，有兩種可能的選擇，因還未去頂組合的其餘元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程式中的函式comb。
3.回溯法
回溯法也稱為試探法，該方法首先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。
【問題】組合問題
問題描述：找出從自然數1，2，…，n中任取r個數的所有組合。
採用回溯法找問題的解，將找到的組合以從小到大順序存於a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：
（1）a[i+1]>a[i]，後一個數字比前一個大；
（2）a[i]-i<=n-r+1。
按回溯法的思想，找解過程可以敘述如下：
首先放棄組合數個數為r的條件，候選組合從只有一個數字1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，並使其滿足上述條件（1），候選組合改為1，2。繼續這一過程，得到候選組合1，2，3。該候選解滿足包括問題規模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a[2]上的3調整為4，以及以後調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由於對5不能再作調整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調整為3，並向前試探，得到解1，3，4。重複上述向前試探和向後回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按上述思想寫成程式如下節。
4.貪婪法
貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
例如平時購物找錢時，為使找回的零錢的硬幣數最少，不考慮找零錢的所有各種發表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先儘量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這裡總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優的解應是3個5單位面值的硬幣。
5.分治法
任何一個可以用計算機求解的問題所需的計算時間都與其規模N有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。
分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
如果原問題可分割成k個子問題（1<k≤n），且這些子問題都可解，並可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反覆套用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時套用在算法設計之中，並由此產生許多高效算法。
分治法所能解決的問題一般具有以下幾個特徵：
（1）該問題的規模縮小到一定的程度就可以容易地解決；
（2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；
（3）利用該問題分解出的子問題的解可以合併為該問題的解；
（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
上述的第一條特徵是絕大多數問題都可以滿足的，因為問題的計算複雜性一般是隨著問題規模的增加而增加；第二條特徵是套用分治法的前提，它也是大多數問題可以滿足的，此特徵反映了遞歸思想的套用；第三條特徵是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮貪心法或動態規劃法。第四條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。
分治法在每一層遞歸上都有三個步驟：
（2）解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
（3）合併：將各個子問題的解合併為原問題的解。
6.動態規劃法
經常會遇到複雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地採用把大問題分解成子問題，並綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規模呈冪級數增加。
為了節約重複求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存於該數組中，這就是動態規劃法所採用的基本方法。以下先用實例說明動態規劃方法的使用。
7.疊代法
（1）選一個方程的近似根，賦給變數x0；
（2）將x0的值保存於變數x1，然後計算g(x1)，並將結果存於變數x0；
（3）當x0與x1的差的絕對值還小於指定的精度要求時，重複步驟（2）的計算。
若方程有根，並且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。上述算法用C程式的形式表示為：
程式如下：
【算法】疊代法求方程組的根
{for(i=0;i<n;i++)
x[i]=初始近似根;
do{
for(i=0;i<n;i++)
y[i]=x[i];
for(i=0;i<n;i++)
x[i]=gi(X);
for(delta=0.0,i=0;i<n;i++)
if(fabs(y[i]-x[i])>delta)delta=fabs(y[i]-x[i])；
}while(delta>Epsilon)；
for(i=0;i<n;i++)
printf(“變數x[%d]的近似根是%f”，I，x[i])；
printf(“\n”)；
}具體使用疊代法求根時應注意以下兩種可能發生的情況：
（1）如果方程無解，算法求出的近似根序列就不會收斂，疊代過程會變成死循環，因此在使用疊代算法前應先考察方程是否有解，並在程式中對疊代的次數給予限制；
（2）方程雖然有解，但疊代公式選擇不當，或疊代的初始近似根選擇不合理，也會導致疊代失敗。
8.窮舉搜尋法
窮舉搜尋法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從眾找出那些符合要求的候選解作為問題的解。
【問題】將A、B、C、D、E、F這六個變數排成如圖所示的三角形，這六個變數分別取[1，6]上的整數，且均不相同。求使三角形三條邊上的變數之和相等的全部解。如圖就是一個解。
程式引入變數a、b、c、d、e、f，並讓它們分別順序取1至6的整數，在它們互不相同的條件下，測試由它們排成的如圖所示的三角形三條邊上的變數之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當這些變數取盡所有的組合後，程式就可得到全部可能的解。
按窮舉法編寫的程式通常不能適應變化的情況。如問題改成有9個變數排成三角形，每條邊有4個變數的情況，程式的循環重數就要相應改變。
簡單對比
遞歸與遞推的區別
最好的例子是斐波那契數列:1123581321......
總結成公式就是F(n+1)=F(n)+F(n-1),F(0)=F(1)=1;
你可以用遞歸的方法寫這個函式:
intF(intn){
if(n<2)return1;
elsereturnF(n-1)+F(n-2);
}
但也可以用遞推的方式:
intF(intn){
if(n<2)return1;
intf0=1,f1=1,f;
for(inti=0;i<n-1;i++){
f=f0+f1;
f1=f;f0=f1;
}
}
顯然能用遞推的話就用遞推,一般肯定要比遞歸快,除非有的問題不用遞歸做不出來的.
線性規劃法在推導時往往是用遞歸的形式,但最後可以化為遞推
遞歸：n!=n*(n-1)!
遞推：n!=1*2*....*(n-1)*n;
不同點：
1，從程式上看，遞歸表現為自己調用自己，遞推則沒有這樣的形式。
2，遞歸是從問題的最終目標出發，逐漸將複雜問題化為簡單問題，最終求得問題
是逆向的。
遞推是從簡單問題出發，一步步的向前發展，最終求得問題。是正向的。
3，遞歸中，問題的n要求是計算之前就知道的，而遞推可以在計算中確定，
不要求計算前就知道n。
4，一般來說，遞推的效率高於遞歸（當然是遞推可以計算的情況下）能用遞推一定能有遞歸。
代碼實現
由於涉及的方法較多，在這裡只舉兩個最典型的例子作為參考：
1.回溯法
【程式】
#defineMAXN100
inta[MAXN];
voidcomb(intm,intr)
{inti,j;
i=0;
a[i]=1;
do{
if(a[i]-i<=m-r+1
{if(i==r-1)
{for(j=0;j<r;j++)
printf(“%4d”,a[j]);
printf(“\n”);
}
a[i]++;
continue;
}
else
{if(i==0)
return;
a[--i]++;
}
}while(1)
}
main()
{comb(5,3);
}
2.遞歸法
【程式】
#include<stdio.h>
#defineMAXN100
inta[MAXN];
voidcomb(intm,intk){
inti,j;
for(i=m;i>=k;i--){
a[k]=i;
if(k>1)
comb(i-1,k-1);
else{
for(j=a[0];j>0;j--)
printf(“%4d”,a[j]);
printf(“\n”);
}
}
}
voidmain(){
a[0]=3;
comb(5,3);
}
