❶ 分治演算法——漢諾塔問題
一、分治演算法概念
「分而治之」，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。
這個技巧是很多高效演算法的基礎，如排序演算法(快速排序，歸並排序)，傅立葉變換(快速傅立葉變換) 。
任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當n較大時，問題就不那麼容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。
二、分治法的設計思想
將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
三、分治策略
對於一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。這種演算法設計策略叫做分治法。
四、分治法實現步驟
①分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；②解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；③合並：將各個子問題的解合並為原問題的解。
它的一般的演算法設計模式如下： Divide-and-Conquer(P) 1. if |P|≤n0 2. then return(ADHOC(P)) 3. 將P分解為較小的子問題 P1 ,P2 ,…,Pk 4. for i←1 to k 5. do yi ← Divide-and-Conquer(Pi) 遞歸解決Pi 6. T ← MERGE(y1,y2,…,yk) 合並子問題 7. return(T)
五、可使用分治法求解的一些經典問題 （1）二分搜索
（2）大整數乘法
（3）Strassen矩陣乘法
（4）棋盤覆蓋
（5）合並排序
（6）快速排序
（7）線性時間選擇
（8）最接近點對問題
（9）循環賽日程表
（10）漢諾塔
❷ 程序員都應該精通的六種演算法，你會了嗎
對於一名優秀的程序員來說，面對一個項目的需求的時候，一定會在腦海里浮現出最適合解決這個問題的方法是什麼，選對了演算法，就會起到事半功倍的效果，反之，則可能會使程序運行效率低下，還容易出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格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問一共有多少種擺法。
回溯法是求解皇後問題最經典的方法。演算法的思想在於如果一個皇後選定了位置，那麼下一個皇後的位置便被限制住了，下一個皇後需要一直找直到找到安全位置，如果沒有找到，那麼便要回溯到上一個皇後，那麼上一個皇後的位置就要改變，這樣一直遞歸直到所有的情況都被舉出。
六、動態規劃演算法
動態規劃過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。
動態規劃演算法適用於當某階段狀態給定以後，在這階段以後的過程的發展不受這段以前各段狀態的影響，即無後效性的問題。
典型例子比如說背包問題，給定背包容量及物品重量和價值，要求背包裝的物品價值最大。
❸ 分治演算法幾個經典例子
分治法，字面意思是「分而治之」，就是把一個復雜的1問題分成兩個或多個相同或相似的子問題，再把子問題分成更小的子問題直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合並，這個思想是很多高效演算法的基礎。
圖二
大整數乘法
Strassen矩陣乘法
棋盤覆蓋
合並排序
快速排序
線性時間選擇
最接近點對問題
循環賽日程表
漢諾塔
❹ 分治演算法是什麼呢
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。
解題步驟
分治法解題的一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。
❺ 最通俗、簡單的分治演算法思想
分治演算法的基本思想是將一個計算復雜的問題分為規模較小，計算簡單的小問題求解 ，然後綜合各個小問題，而得到最終問題的答案。分治演算法的執行過程如下：
♦對於一個規模為N的問題，若該問題可以容易地解決（比如說規模N較小），則直接解決，否則執行下面的步驟。
♦將該分解為M個規模較小的子問題，這些子問題互相獨立，並且與原問題形式相同。
♦遞歸地解這些子問題。
♦然後，將各子問題的解合並得到原問題的解。
問：一個袋子里有30個硬幣，其中一枚是假幣，並且假幣和真幣一模一樣，肉眼很難分辨，目前只知道假幣比真幣重量輕一點。請問如何區分出假幣呢? 可以採用遞歸分治的思想來求解這個問題：
♦首先為每個銀幣編號，然後可以將所有的銀幣等分為兩分，放在天平的兩邊。這樣就將區分30個硬幣的問題，變為區別兩堆硬幣的問題。
♦因為假銀幣的分量較輕，因此天平較輕的一側中一定包含假銀幣。
♦再將較輕的一側中的硬銀幣等分為兩分，重復上述的做法。鄭念絕
♦直到剩下2枚高拆硬銀幣，可用天平直接找出假銀幣來。
運行結果
分治喊姿演算法求解假的銀幣問題!
請輸入硬幣的數量：13
請輸入每個硬幣的質量：
第1個：2
第2個：2
第3個：2
第4個：2
第5個：2
第6個：2
第7個：2
第8個：2
第9個：2
第10個：1
第11個：2
第12個：2
第13個：2
第10個為假幣！！
