分而治之方法與軟體設計的模組化方法非常相似。為了解決乙個大的問題，可以：
1) 把它分成兩個或多個更小的問題；
2) 分別解決每個小問題；
3) 把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞迴地使用分而治之策略來解決。下列通過例項加以說明。
例：利用分而治之演算法求乙個整數陣列中的最大值。
#include //檔案包含預處理命令，printf( )函式在其中宣告
int max(int a, int n); // 求a[0],a[1],...,a[n-1]中的最大值
int main(void)
; int i;
printf("陣列a:");
for (i=0; i < n; i++)
printf("%d ", a[i]);
printf("\n最大值為%d .\n", max(a, 8));
return 0返回值0
}/* 用分而治之演算法求乙個整數陣列中的最大值 */
int max(int a, int n)
else
遞迴結束條件不成立，繼續遞迴
max1 = max(a, n - 1); /* 求a[0],a[1],...,a[n-1]的最大值max1 */
求max1和a[n-1]的最大值 */
if (max1 > a[n - 1])
max2 = max1;
else
max2 = a[n-1
return max2;
}}練習：[找出偽幣] 給你乙個裝有1 6個硬幣的袋子。1 6個硬幣中有乙個是偽造的，並且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。
貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的區域性最優解。貪心演算法不是對所有問題都能得到整體最優解，但對範圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。
貪心演算法(greedy algorithm)是一種對某些求最優解問題的更簡單、更迅速的設計技術。用貪婪法設計演算法的特點是一步一步地進行，常以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間，它採用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇就將所求問題簡化為乙個規模更小的子問題, 通過每一步貪心選擇,可得到問題的乙個最優解，雖然每一步上都要保證能獲得區域性最優解，但由此產生的全域性解有時不一定是最優的，所以貪婪法不要回溯。
貪心演算法是一種改進了的分級處理方法。其核心是根據題意選取一種量度標準。然後將這多個輸入排成這種量度標準所要求的順序，按這種順序一次輸入乙個量。
如果這個輸入和當前已構成在這種量度意義下的部分最佳解加在一起不能產生乙個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪演算法。
對於乙個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。因此，選擇能產生問題最優解的最優量度標準是使用貪婪演算法的核心。
一般情況下，要選出最優量度標準並不是一件容易的事，但對某問題能選擇出最優量度標準後，用貪婪演算法求解則特別有效。最優解可以通過一系列區域性最優的選擇即貪婪選擇來達到,根據當前狀態做出在當前看來是最好的選擇，即區域性最優解選擇，然後再去解做出這個選擇後產生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為乙個規模更小的子問題，最終可得到問題的乙個整體最優解。
貪心演算法特性
貪心演算法可解決的問題通常大部分都有如下的特性:
（1） 有乙個以最優方式來解決的問題。為了構造問題的解決方案,有乙個候選的物件的集合：比如不同面值的硬幣。
（2） 隨著演算法的進行,將積累起其它兩個集合：乙個包含已經被考慮過並被選出的候選物件,另乙個包含已經被考慮過但被丟棄的候選物件。
（3） 有乙個函式來檢查乙個候選物件的集合是否提供了問題的解答。該函式不考慮此時的解決方法是否最優。
（4） 還有乙個函式檢查是否乙個候選物件的集合是可行的,也即是否可能往該集合上新增更多的候選物件以獲得乙個解。和上乙個函式一樣,此時不考慮解決方法的最優性。
（5） 選擇函式可以指出哪乙個剩餘的候選物件最有希望構成問題的解。
（6） 最後,目標函式給出解的值。
為了解決問題,需要尋找乙個構成解的候選物件集合,它可以優化目標函式,貪婪演算法一步一步的進行。起初,演算法選出的候選物件的集合為空。接下來的每一步中,根據選擇函式,演算法從剩餘候選物件中選出最有希望構成解的物件。
如果集合中加上該物件後不可行，那麼該物件就被丟棄並不再考慮；否則就加到集合裡。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪演算法正確工作，那麼找到的第乙個解通常是最優的。
貪心演算法的基本思路
1.建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的區域性最優解。
4.把子問題的解區域性最優解合成原來解問題的乙個解。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的乙個解元素；
由所有解元素組合成問題的乙個可行解。
下面是乙個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。
例題分析
[揹包問題]有乙個揹包，揹包容量是m=150。有7個物品，物品不可以分割成任意大小。
要求盡可能讓裝入揹包中的物品總價值最大，但不能超過總容量。
物品 a b c d e f g
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30
分析：目標函式： ∑pi最大
約束條件是裝入的物品總重量不超過揹包容量：∑wi<=m( m=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入揹包，得到的結果是否最優？
（2）每次挑選所佔重量最小的物品裝入是否能得到最優解？
（3）每次選取單位重量價值最大的物品，成為解本題的策略。
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
（1）貪心策略：選取價值最大者。
反例：w=30
物品：a b c
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品a，接下來就無法再選取了，可是，選取b、c則更好。
（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
（3）貪心策略：選取單位重量價值最大的物品。
反例：w=30
物品：a b c
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程式無法依據現有策略作出判斷，如果選擇a，則答案錯誤。
【注意：如果物品可以分割為任意大小，那麼策略3可得最優解】
對於選取單位重量價值最大的物品這個策略，可以再加一條優化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。
但是，如果題目是如下所示，這個策略就也不行了。
w=40
物品：a b c
重量：25 20 15
價值：25 20 15
附：本題是個np問題，用貪心法並不一定可以求得最優解，以後了解了動態規劃演算法後本題就有了新的解法。
備註：貪心演算法當然也有正確的時候。求最小生成樹的prim演算法和kruskal演算法都是漂亮的貪心演算法。
貪心法的應用演算法有dijkstra的單源最短路徑和chvatal的貪心集合覆蓋啟發式
所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的物件是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的機率正確）
#include
#include
#include
#include
#include
#define k 10
#define n 10
/**從小到大建立物品 k?
void create(long array,int n,int k)}*/
void create(long array,int n)
}void output(long array,int n)
}void beibao(long array,int cankao,long value,int count)
{ int i;
long r=value;
for(i=count-1;i>=0;i--)
{if(r>=array[i])
C語言經典演算法100例
c語言經典演算法100例 31 60 程式31 題目 請輸入星期幾的第乙個字母來判斷一下是星期幾，如果第乙個字母一樣，則繼續 判斷第二個字母。1.程式分析 用情況語句比較好，如果第乙個字母一樣，則判斷用情況語句或if語句判斷第二個字母。2.程式源 include void main 程式32 題目 ...
C語言經典演算法100例
程式1 題目 有1 2 3 4個數字，能組成多少個互不相同且無重複數字的三位數？都是多少？1.程式分析 可填在百位 十位 個位的數字都是1 2 3 4。組成所有的排列後再去 掉不滿足條件的排列。2.程式源 main 程式2 題目 企業發放的獎金根據利潤提成。利潤 i 低於或等於10萬元時，獎金可提1...
經典濾波演算法及C語言程式
經典的濾波演算法 a 方法 根據經驗判斷，確定兩次取樣允許的最大偏差值 設為a 每次檢測到新值時判斷 如果本次值與上次值之差 a,則本次值有效 如果本次值與上次值之差 a,則本次值無效,放棄本次值,用上次值代替本次值 b 優點 能有效克服因偶然因素引起的脈衝干擾 c 缺點 無法抑制那種週期性的干擾 ...