分治演算法的基本框架是

⑴ 最通俗、簡單的分治演算法思想

分治演算法的基本思想是將一個計算復雜的問題分為規模較小，計算簡單的小問題求解 ，然後綜合各個小問題，而得到最終問題的答案。分治演算法的執行過程如下：
♦對於一個規模為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個為假幣！！

⑵ 分治法的基本思想

對於一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否或運則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。這種演算法設計策略叫譽團脊做分治法。

如果原問題可分割成k個子問題，1<k≤n ，且這些子問題都可解並可利用這些子問題的解求出原問題的解，那麼這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。

分治法所能解決的問題一般具有慶滲以下幾個特徵：

1、該問題的規模縮小到一定的程度就可以容易地解決

2、該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。

3、利用該問題分解出的子問題的解可以合並為該問題的解；

4、該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

⑶ 分治法指的是什麼呢

分治法指的是將原問題遞歸地分成若干個子問題，直到子問題滿足邊界條件，停止遞歸，將子問題逐個解決（一般是同種方法），將已經解決的子問題合並，最後，演算法會層層合並得到原問題的答案。

分治演算法步驟：

分：遞歸地將問題分解為各個的子問題（性質相同的，相互獨立的子問題）。

治：將這些規模更小的子問題逐個擊破。

合：將已解決的問題逐層合並，最終得出原問題的解。

分治法適用條件

1、問題的規模縮小到一定的規模就可以較容易地解決。

2、問題可以分解為若干個規模較小的模式相同的子問題，即該問題具有最優子結構性質。

3、合並問題分解出的子問題的解可以得到問題的解。

4、問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。

⑷ 分治法的步驟

分治法在每一層遞歸上都有三個步驟：
分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
合並：將各個子問題的解合並為原問題的解。
它的一般的演算法設計模式如下：
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)
其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC(P)是該分治法中的基本子演算法，用於直接解小規模的問題P。因此，當P的規模不超過n0時直接用演算法ADHOC(P)求解。演算法MERGE(y1,y2,...,yk)是該分治法中的合並子演算法，用於將P的子問題P1 ,P2 ,...,Pk的相應的解y1,y2,...,yk合並為P的解。
根據分治法的分割原則，原問題應該分為多少個子問題才較適宜？
各個子問題的規模應該怎樣才為適當？
答: 但人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取 k = 2。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
出處：網路
實踐題目：
給定一個順序表，編寫一個求出其最大值和最小值的分治演算法。
分析：
由於順序表的結構沒有給出，作為演示分治法這里從簡順序表取一整形數組數組大小由用戶定義，數據隨機生成。我們知道如果數組大小為 1 則可以直接給出結果，如果大小為 2則一次比較即可得出結果，於是我們找到求解該問題的子問題即: 數組大小 <= 2。到此我們就可以進行分治運算了，只要求解的問題數組長度比 2 大就繼續分治，否則求解子問題的解並更新全局解
以下是代碼。
*/
/*** 編譯環境TC ***/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define M 40
/* 分治法獲取最優解 */
void PartionGet(int s,int e,int *meter,int *max,int *min){
/* 參數:
* s 當前分治段的開始下標
* e 當前分治段的結束下標
* meter 表的地址
* max 存儲當前搜索到的最大值
* min 存儲當前搜索到的最小值
*/
int i;
if(e-s <= 1){ /* 獲取局部解，並更新全局解 */
if(meter[s] > meter[e]){
if(meter[s] > *max)
*max = meter[s];
if(meter[e] < *min)
*min = meter[e];
}
else{
if(meter[e] > *max)
*max = meter[e];
if(meter[s] < *min)
*min = meter[s];
}
return ;
}
i = s + (e-s)/2; /* 不是子問題繼續分治,這里使用了二分，也可以是其它 */
PartionGet(s,i,meter,max,min);
PartionGet(i+1,e,meter,max,min);
}
int main(){
int i,meter[M];
int max = INT_MIN; /* 用最小值初始化 */
int min = INT_MAX; /* 用最大值初始化 */
printf(The array's element as followed: );
rand(); /* 初始化隨機數發生器 */
for(i = 0; i < M; i ++){ /* 隨機數據填充數組 */
meter[i] = rand()%10000;
if(!((i+1)%10)) /* 輸出表的隨機數據 */
printf(%-6d ,meter[i]);
else
printf(%-6d,meter[i]);
}
PartionGet(0,M - 1,meter,&max,&min); /* 分治法獲取最值 */
printf( Max : %d Min : %d ,max,min);
system(pause);
return 0;
}

⑸ 簡述分治法的基本思想

分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然後將各個子問題的解合並得到原問題的解。它的一般的演算法設計模式如下：
divide-and-conquer(P)
{
if(|P|<=n0)
adhoc(P);
divide
P
into
smaller
subinstances
P1,P2,...,Pk;
for(i=1;i<=k;i++)
yi=divide-and-conquer(Pi);
return
merge(y1,...,yk);
}
其中，|P|表示問題P的規模。n0為一閥值，表示當問題P的規模不超過n0時，問題已容易解出，不必再繼續分解。adhoc(P)是該分治法中的基本子演算法，用於直接解小規模的問題P。當P的規模不超過n0時，直接演算法adhoc(P)求解。演算法merge(y1,y2,...,yk)是該分治法中的合並子演算法，用於將P的子問題P1,P2,...,Pk的解y1,y2,...,yk合並為P的解。
根據分治法的分割原則，應把原問題分為多少個子問題才比較適宜？每個子問題是否規模相同或怎樣才為適當？這些問題很難給予肯定的回答。但人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規模大致相等的做法是出自一種平衡(banlancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
從分治法的一般設計模式可以看出，用它設計出的演算法一般是遞歸演算法。因此，分治法的計算效率通常可以用遞歸方程來進行分析。一個分治法將規模為n的問題分成m個規模為n/m的子問題，其中k(k<=m)個子問題需要求解。為方便起見，設分解閥值n0=1，且adhoc解規模為1的問題耗費1個單位時間。另外再設將原問題分解為k個問題以及用merge將k個子問題的解合並為原問題的解需用f(n)個單位時間。如果用T(n)表示該分治法divide-and-conquer(P)解規模為|P|=n的問題所需的計算時間，則有：
http://image211.poco.cn/mypoco/myphoto/20090409/00/_002.jpg
下面來討論如何解這個與分治法有密切關系的遞歸方程。通常可以用展開遞歸式的方法來解這類遞歸方程，反復代入求解得：
http://image211.poco.cn/mypoco/myphoto/20090409/00/_001.jpg
注意，遞歸方程及其解只給出n等於m的方冪時T(n)的值，但是如果T(n)足夠平滑，由n等於m的方冪時T(n)的值估計T(n)的增長速度。通常，可以假定T(n)單調上升。
另一個需要注意的問題是，在分析分治法的計算效率是，通常得到的是遞歸不等式：
http://image211.poco.cn/mypoco/myphoto/20090409/00/_000.jpg
在討論最壞情況下的計算時間復雜度，用等號(=)還是用小於等於號(<=)是沒有本質區別的。

⑹ 分治演算法是什麼呢

分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。

解題步驟

分治法解題的一般步驟：

（1）分解，將要解決的問題劃分成若干規模較小的同類問題；

（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；

（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。

⑺ 分治策略的基本思想

分治策略的基本思想如下：

分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。

當我們求解某些問題時，由於這些問題要處理的數據相當多，或求解過程相當復雜，使得直接求解法在時間上相當長，或者根本無法直接求出。

對於這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法後，再找到合適的方法，把它們組合成求整個問題的解法。

分治法解題的一般步驟（如圖1）：

（1）分解，將要解決的問題劃分成若干規模較小的同類問題；

（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；祥灶

（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。