經典演算法程序
A. 幾種經典排序演算法優劣比較的C++程序實現
一、低級排序演算法
1.選擇排序
（1）排序過程
給定一個數值集合，循環遍歷集合，每次遍歷從集合中選擇出最小或最大的放入集合的開頭或結尾的位置，下次循環從剩餘的元素集合中遍歷找出最小的並如上操作，最後直至所有原集合元素都遍歷完畢，排序結束。
（2）實現代碼
//選擇排序法
template
void Sort：：SelectSort（T* array， int size）
{
int minIndex；
for（int i = 0； i < size； i++）
{
minIndex = i；
for（int j = i + 1； j < size； j++）
{
if（array[minIndex] > array[j]）
{
minIndex = j；
}
}
if（minIndex ！= i）
{
Swap（array， i， minIndex）；
}
}
}
（3）分析總結
選擇排序時間復雜度比較高，達到了O（n^2），每次選擇都要遍歷一遍無序區間。選擇排序對一類重要的元素序列具有較好的效率，就是元素規模很大，而排序碼卻比較小的序列。另外要說明的是選擇排序是一種不穩定的排序方法。
2.冒泡排序
（1）排序過程
冒泡排序的過程形如其名，就是依次比較相鄰兩個元素，優先順序高（或大或小）的元素向後移動，直至到達序列末尾，無序區間就會相應地縮小。下一次再從無序區間進行冒泡操作，依此循環直至無序區間為1，排序結束。
（2）實現代碼
//冒泡排序法
template
void Sort：：BubbleSort（T* array， int size）
{
for（int i = 0； i < size； i++）
{
for（int j = 1； j < size - i； j++）
{
if（array[j] < array[j - 1]）
{
Swap（array， j， j - 1）；
}
}
}
}
（3）分析總結
冒泡排序的時間復雜度也比較高，達到O（n^2），每次遍歷無序區間都將優先順序高的元素移動到無序區間的末尾。冒泡排序是一種穩定的排序方式。
二、高級排序演算法
（1）排序過程
歸並排序的原理比較簡單，也是基於分治思想的。它將待排序的元素序列分成兩個長度相等的子序列，然後為每一個子序列排序，然後再將它們合並成一個序列。
（2）實現代碼
//歸並排序
template
void Sort：：MergeSort（T* array， int left， int right）
{
if（left < right）
{
int mid = （left + right） / 2；
MergeSort（array， left， mid）；
MergeSort（array， mid + 1， right）；
Merge（array， left， mid， right）；
}
}
//合並兩個已排好序的子鏈
template
void Sort：：Merge（T* array， int left， int mid， int right）
{
T* temp = new T[right - left + 1]；
int i = left， j = mid + 1， m = 0；
while（i <= mid && j <= right）
{
if（array[i] < array[j]）
{
temp[m++] = array[i++]；
}
else
{
temp[m++] = array[j++]；
}
}
while（i <= mid）
{
temp[m++] = array[i++]；
}
while（j <= right）
{
temp[m++] = array[j++]；
}
for（int n = left， m = 0； n <= right； n++， m++）
{
array[n] = temp[m]；
}
delete temp；
}
（3）分析總結
歸並排序最好、最差和平均時間復雜度都是O（nlogn），是一種穩定的排序演算法。
B. c語言求最小公倍數
1、首先介紹一下求最小公倍數的經典方法:
輾轉相除法
有兩整數a和b：
①a%b得余數c
②若c=0，則b即為兩數的最大公約數
③若c≠0，則a=b，b=c，再回去執行①
a*b除以最大公約數等於最小公倍數
2、因此原問題也化為最小公倍數和最大公約數一起求了。程序的演算法如下：
#include<stdio.h>
int lowest_common_multiple(int m,int n);
int main()
{
int m,n,c;
printf("請輸入m的值: ");
scanf("%d",&m);
printf("請輸入n的值: ");
scanf("%d",&n);
c=lowest_common_multiple( m, n);
printf("請輸出最小公倍數c的值: ");
printf("%d ",c);
return 0;
}
int lowest_common_multiple(int m,int n)
{
int remainder,m1,n1;
m1=m;
n1=n;
while (n != 0) {
remainder = m % n;
m = n;
n = remainder;
}
//printf("輸出最大公約數m: %d ", m); //此時的m為最大公約數
return m1*n1/m;
}
3、程序的輸出如下：
4、此題注釋的哪一個是輸出最大公約數的。
C. 程序員都應該精通的六種演算法，你會了嗎
對於一名優秀的程序員來說，面對一個項目的需求的時候，一定會在腦海里浮現出最適合解決這個問題的方法是什麼，選對了演算法，就會起到事半功倍的效果，反之，則可能會使程序運行效率低下，還容易出bug。因此，熟悉掌握常用的演算法，是對於一個優秀程序員最基本的要求。
那麼，常用的演算法都有哪些呢？一般來講，在我們日常工作中涉及到的演算法，通常分為以下幾個類型：分治、貪心、迭代、枚舉、回溯、動態規劃。下面我們來一一介紹這幾種演算法。
一、分治演算法
分治演算法，顧名思義，是將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
分治演算法一般分為三個部分：分解問題、解決問題、合並解。
分治演算法適用於那些問題的規模縮小到一定程度就可以解決、並且各子問題之間相互獨立，求出來的解可以合並為該問題的解的情況。
典型例子比如求解一個無序數組中的最大值，即可以採用分治演算法，示例如下：
def pidAndConquer(arr,leftIndex,rightIndex):
if(rightIndex==leftIndex+1 || rightIndex==leftIndex){
return Math.max(arr[leftIndex],arr[rightIndex]);
}
int mid=(leftIndex+rightIndex)/2;
int leftMax=pidAndConquer(arr,leftIndex,mid);
int rightMax=pidAndConquer(arr,mid,rightIndex);
return Math.max(leftMax,rightMax);
二、貪心演算法
貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。
貪心演算法的基本思路是把問題分成若干個子問題，然後對每個子問題求解，得到子問題的局部最優解，最後再把子問題的最優解合並成原問題的一個解。這里要注意一點就是貪心演算法得到的不一定是全局最優解。這一缺陷導致了貪心演算法的適用范圍較少，更大的用途在於平衡演算法效率和最終結果應用，類似於：反正就走這么多步，肯定給你一個值，至於是不是最優的，那我就管不了了。就好像去菜市場買幾樣菜，可以經過反復比價之後再買，或者是看到有賣的不管三七二十一先買了，總之最終結果是菜能買回來，但搞不好多花了幾塊錢。
典型例子比如部分背包問題：有n個物體，第i個物體的重量為Wi，價值為Vi，在總重量不超過C的情況下讓總價值盡量高。每一個物體可以只取走一部分，價值和重量按比例計算。
貪心策略就是，每次都先拿性價比高的，判斷不超過C。
三、迭代演算法
迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程。迭代演算法是用計算機解決問題的一種基本方法，它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令(或一定步驟)進行重復執行，在每次執行這組指令(或這些步驟)時，都從變數的原值推出它的一個新值。最終得到問題的結果。
迭代演算法適用於那些每步輸入參數變數一定，前值可以作為下一步輸入參數的問題。
典型例子比如說，用迭代演算法計算斐波那契數列。
四、枚舉演算法
枚舉演算法是我們在日常中使用到的最多的一個演算法，它的核心思想就是:枚舉所有的可能。枚舉法的本質就是從所有候選答案中去搜索正確地解。
枚舉演算法適用於候選答案數量一定的情況。
典型例子包括雞錢問題，有公雞5，母雞3，三小雞1，求m錢n雞的所有可能解。可以採用一個三重循環將所有情況枚舉出來。代碼如下：
五、回溯演算法
回溯演算法是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。
許多復雜的，規模較大的問題都可以使用回溯法，有「通用解題方法」的美稱。
典型例子是8皇後演算法。在8 8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問一共有多少種擺法。
回溯法是求解皇後問題最經典的方法。演算法的思想在於如果一個皇後選定了位置，那麼下一個皇後的位置便被限制住了，下一個皇後需要一直找直到找到安全位置，如果沒有找到，那麼便要回溯到上一個皇後，那麼上一個皇後的位置就要改變，這樣一直遞歸直到所有的情況都被舉出。
六、動態規劃演算法
動態規劃過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。
動態規劃演算法適用於當某階段狀態給定以後，在這階段以後的過程的發展不受這段以前各段狀態的影響，即無後效性的問題。
典型例子比如說背包問題，給定背包容量及物品重量和價值，要求背包裝的物品價值最大。