演算法導論分治法_什麼是分治演算法

① 演算法導論，分治法求最大子數組，求一個c語言代碼

這題的思想是書上的（《演算法導論》），代碼當然也是按照書上偽碼寫出的；
#include<stdio.h>

intFind_Max_Crossing_SubArray(intA[],intlow,intmid,inthigh)
{
intleft_sum=-0xff;
intsum=0;
for(inti=mid;i>=low;i--)
{
sum+=A[i];
if(sum>left_sum)
{
left_sum=sum;
}
}
intright_sum=-0xff;
sum=0;
for(intj=mid+1;j<=high;j++)
{
sum+=A[j];
if(sum>right_sum)
{
right_sum=sum;
}
}
returnleft_sum+right_sum;
}

intFind_Maximum_SubArray(intA[],intlow,inthigh)
{
intleft_sum,right_sum,cross_sum;
if(high==low)
{
returnA[low];
}
else
{
intmid=(low+high)/2;
left_sum=Find_Maximum_SubArray(A,low,mid);
right_sum=Find_Maximum_SubArray(A,mid+1,high);
cross_sum=Find_Max_Crossing_SubArray(A,low,mid,high);
if(left_sum>=right_sum&&left_sum>=cross_sum)
{
returnleft_sum;
}
elseif(right_sum>=left_sum&&right_sum>=cross_sum)
{
returnright_sum;
}
else
{
returncross_sum;
}
}
}
intmain()
{
intA[100];
intn;
printf("Pleaseinputthenumberofnumbers:");
scanf("%d",&n);
for(inti=0;i<n;i++)
{
scanf("%d",&A[i]);
}
printf("最大子序列的和為：%d",Find_Maximum_SubArray(A,0,n-1));
return0;
}

② 分治演算法——漢諾塔問題

一、分治演算法概念
「分而治之」，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。

這個技巧是很多高效演算法的基礎，如排序演算法(快速排序，歸並排序)，傅立葉變換(快速傅立葉變換) 。

任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於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）漢諾塔

③ 什麼是分治演算法

分治法就是將一個復雜的問題分成多個相對簡單的獨立問題進行求解，並且綜合所有簡單問題的解可以組成這個復雜問題的解。
例如快速排序演算法就是一個分治法的例子。即將一個大的無序序列排序成有序序列，等於將兩個無序的子序列排序成有序，且兩個子序列之間滿足一個序列的元素普遍大於另一個序列中的元素。

④ 分治演算法的基本思想

當我們求解某些問題時，由於這些問題要處理的數據相當多，或求解過程相當復雜，使得直接求解法在時間上相當長，或者根本無法直接求出。對於這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法後，再找到合適的方法，把它們組合成求整個問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。

⑤ 利用分治演算法求解、

對於這種已知不合格硬幣比正常銀幣偏重（或偏輕）的問題，可以用分治法。以下演算法可以用數學歸納法證明：假設有3枚硬幣，則稱一次，如果a邊重則是a，……，平衡則是c。同理如果有N塊硬幣，我們可以把它分成三堆，稱一次後，這樣問題規模縮小至n/3。重復以上操作，直至稱出。需要次數為log3 n。這是典型的分治法，如果想了解更多，可參考《演算法導論》謝謝採納我的答案

⑥ 誰能告訴我《演算法導論》最大子數組的遞歸過程是怎樣的詳細的步驟

使用的方法是分治法。主要思想是：遞歸的將數組分成兩部分，假設劃分的地方在第k個元素，則最大子數組的位置必然在以下三種情況之中：
1、在前半部分
2、在後半部分
3、跨越了第k個元素
遞歸的計算出這三個部分的最大子數組，然後比較大小，就能得到最大子數組。

⑦ 分治法找兩數組的中值

這個就在教科書上阿。參考演算法導論
很長的哦：
C#的，這個是計算第K個數的，令K=n/2就行了

using System;
using System.Collections;
using NUnit.Framework;
using Algorithm.Test;

namespace Algorithm.Select
{
/// <summary>
/// Kth_Samllest_Selection 的摘要說明。
/// </summary>
public class Kth_Samllest_Selection
{
ArrayList m_al;
ArrayList m_MedianAl;
ArrayList m_S1;
ArrayList m_S2;

int m_K;
public Kth_Samllest_Selection(ArrayList al,int K)
{
m_al = al;
m_K = K;
m_MedianAl = new ArrayList(al.Count/5+1);
m_S1 = new ArrayList(al.Count/2);
m_S2 = new ArrayList(al.Count/2);
}
/// <summary>
/// 執行操作
/// </summary>
/// <returns>第K個數的大小</returns>
public int Do()
{

if(m_al.Count<=5)
{
m_al.Sort();
return ((ComparableObject)m_al[m_K-1]).Value;
}
while(m_al.Count%5!=0)
{
m_al.Add(new ComparableObject(int.MaxValue));
}
int k = m_al.Count/5;
for(int i=0;i<k;i++)
{
int start = i*5;
int num1 = ((ComparableObject)m_al[start]).Value;
int num2 = ((ComparableObject)m_al[start+1]).Value;
int num3 = ((ComparableObject)m_al[start+2]).Value;
int num4 = ((ComparableObject)m_al[start+3]).Value;
int num5 = ((ComparableObject)m_al[start+4]).Value;

MakeMedianNumMiddle(ref num1,ref num2,ref num3,ref num4,ref num5);

((ComparableObject)m_al[start]).Value = num1;
((ComparableObject)m_al[start+1]).Value= num2;
((ComparableObject)m_al[start+2]).Value= num3;
((ComparableObject)m_al[start+3]).Value= num4;
((ComparableObject)m_al[start+4]).Value= num5;
m_MedianAl.Add((ComparableObject)num3);

//m_MedianAl.Add((MakeMedianNumMiddle(ref (ComparableObject)m_al[start],ref (ComparableObject)m_al[start+1],ref (ComparableObject)m_al[start+2],ref (ComparableObject)m_al[start+3],ref (ComparableObject)m_al[start+4]))[2]);

}
Kth_Samllest_Selection selector = new Kth_Samllest_Selection(m_MedianAl,m_MedianAl.Count/2);
int tmp = selector.Do();
m_MedianAl.Clear();
m_MedianAl = null;
for(int i=0;i<m_al.Count/5;i++)
{
int start = i*5;
if(((ComparableObject)m_al[start+2]).Value <tmp)
{
m_S1.Add((ComparableObject)m_al[start+0]);
m_S1.Add(m_al[start+1]);
m_S1.Add(m_al[start+2]);
if(((ComparableObject)m_al[start+3]).Value<tmp)
{
m_S1.Add(m_al[start+3]);
}
else
{
m_S2.Add(m_al[start+3]);
}
if(((ComparableObject)m_al[start+4]).Value<tmp)
{
m_S1.Add(m_al[start+4]);
}
else
{
m_S2.Add(m_al[start+4]);
}

}
else
{
m_S2.Add(m_al[start+2]);
m_S2.Add(m_al[start+3]);
m_S2.Add(m_al[start+4]);
if(((ComparableObject)m_al[start]).Value>tmp)
{
m_S2.Add(m_al[start]);
}
else
{
m_S1.Add(m_al[start+0]);
}
if(((ComparableObject)m_al[start+1]).Value>tmp)
{
m_S2.Add(m_al[start+1]);
}
else
{
m_S1.Add(m_al[start+1]);
}

}
}

///System.Threading.Thread.Sleep(5);
if(m_S1.Count+1==m_K)
{
return tmp;
}
else if(m_K<=m_S1.Count)
{

Kth_Samllest_Selection selector1 = new Kth_Samllest_Selection(m_S1,m_K);
m_S2.Clear();
m_S2 = null;
int ret = selector1.Do();
selector1 = null;
return ret;
}
else
{

Kth_Samllest_Selection selector2 = new Kth_Samllest_Selection(m_S2,m_K-m_S1.Count);
m_S1.Clear();
m_S1 = null;
int ret = selector2.Do();
selector2 = null;
return ret;
}
}
//最多比較6次可以在5個數中找到中位數
public void MakeMedianNumMiddle(ref int num1,ref int num2,ref int num3,ref int num4,ref int num5)
{
//-------------------------------------------------------------------
if(num2.CompareTo(num1)<0)//num1 存放小數
{
Exchange(ref num1,ref num2);
}
if(num4.CompareTo(num3)<0)//num3 存放小數
{
Exchange(ref num3,ref num4);
}
// 1 3 5
// / /
// 2 4
//---------------------------------------------------------------------
if(num3.CompareTo(num1)<0)//num1 存放小數
{
Exchange(ref num1,ref num3);
Exchange(ref num2,ref num4);
}
//--------------------before here compare three times
//--------------------after here compare at most four times
// 1 5
// / \
// 2 3
// /
// 4
//---------------------------------------------------------------------
if(num2.CompareTo(num5)<0)
{
#region compare two times 12354
// 1
// / \
// 2 3
// / \
// 5 4
//--------------------------------------------------------------------

if(num2.CompareTo(num3)<0)
{
#region compare once 15234
// 1
// /
// 2
// / \
// 5 3
// \
// 4
//--------------------------------------------------------------------
if(num5.CompareTo(num3)<0)
{
// 1
// |
// 2
// |
// 5
// |
// 3
// |
// 4
Exchange(ref num3,ref num5);
}
else
{
// 1
// \
// 2
// \
// 3
// / \
// 5 4
//--------------------------------------------------------------------
}
#endregion
}
else
{
#region compare once 15234
// 1
// /
// 3
// / \
// 4 2
// \
// 5
//--------------------------------------------------------------------

if(num2.CompareTo(num4)<0)
{
// 1
// \
// 3
// \
// 2
// / \
// 4 5
//--------------------------------------------------------------------
Exchange(ref num3,ref num2);
}
else
{
// 1
// \
// 3
// \
// 4
// \
// 2
// \
// 5
//--------------------------------------------------------------------
Exchange(ref num3,ref num4);
Exchange(ref num4,ref num2);
}
#endregion
}
#endregion
}
else
{
#region compare two times 15432
// 5 1
// \ / \
// 2 3
// /
// 4
//--------------------------------------------------------------------

if(num5.CompareTo(num3)<0)
{
#region compare once 12345
// 5 1
// |\/|
// 2 3
// |
// 4
//--------------------------------------------------------------------
if(num2.CompareTo(num3)<0)
{
// 5 1
// | /
// 2
// \
// 3
// |
// 4
//--------------------------------------------------------------------
Exchange(ref num3,ref num2);
Exchange(ref num2,ref num5);
}
else
{
// 5 1
// \|
// 3
// /|
// 2 4
//--------------------------------------------------------------------
Exchange(ref num2,ref num5);

}
#endregion
}
else
{
#region compare once 13245
// 1
// |
// 3
// / \
// 4 5
// \
// 2
if(num4.CompareTo(num5)<0)
{
// 1
// |
// 3
// |
// 4
// |
// 5
// |
// 2
Exchange(ref num3,ref num4);
Exchange(ref num2,ref num4);
}
else
{
// 1
// |
// 3
// |
// 5
// / \
// 4 2
//
//
Exchange(ref num3,ref num5);
Exchange(ref num5,ref num2);
}
#endregion
}
#endregion

}
}
private void Exchange(ref int obj1,ref int obj2)
{
int tmp = obj2;
obj2 = obj1;
obj1 =tmp;
}

}
#region Unit Test
[TestFixture]
[Category("Select")]
public class TestKth_Samllest_Selection
{
ArrayList m_array1;

public TestKth_Samllest_Selection()
{
m_array1 = null;

}
[TestFixtureSetUp]
public void Init()
{
m_array1 = new ArrayList(2000001);
for(int i=0;i<2000000;++i)
{
m_array1.Add(new ComparableObject(new System.Random().Next(2000000)));
}

// for(int i=0;i<25;++i)
// {
// m_array1.Add(new ComparableObject(i+1));
// }
// m_array1.Add(new ComparableObject(1));
// m_array1.Add(new ComparableObject(20));
// m_array1.Add(new ComparableObject(3));
// m_array1.Add(new ComparableObject(14));
// m_array1.Add(new ComparableObject(25));
// m_array1.Add(new ComparableObject(6));
// m_array1.Add(new ComparableObject(10));
// m_array1.Add(new ComparableObject(8));
// m_array1.Add(new ComparableObject(9));
// m_array1.Add(new ComparableObject(7));
// m_array1.Add(new ComparableObject(11));
// m_array1.Add(new ComparableObject(12));
// m_array1.Add(new ComparableObject(24));
// m_array1.Add(new ComparableObject(4));
// m_array1.Add(new ComparableObject(15));
// m_array1.Add(new ComparableObject(16));
// m_array1.Add(new ComparableObject(17));
// m_array1.Add(new ComparableObject(18));
// m_array1.Add(new ComparableObject(19));
// m_array1.Add(new ComparableObject(2));
// m_array1.Add(new ComparableObject(21));
// m_array1.Add(new ComparableObject(22));
// m_array1.Add(new ComparableObject(23));
// m_array1.Add(new ComparableObject(13));
// m_array1.Add(new ComparableObject(5));
// for(int i=0;i<10000;++i)
// {
// m_array1.Add(new ComparableObject(new System.Random().Next(100,1000)));
// }
}
[Test]
public void test()
{
long tmp = DateTime.Now.Ticks;
Kth_Samllest_Selection selector = new Kth_Samllest_Selection(m_array1,1000000);
Console.WriteLine(selector.Do());
Console.WriteLine((DateTime.Now.Ticks-tmp)/6000000.0);
//ArrayList ret = selector.MakeMedianNumMiddle(new ComparableObject(5),
// new ComparableObject(4),
// new ComparableObject(2),
// new ComparableObject(3),
// new ComparableObject(1));
//foreach(ComparableObject item in ret)
//{
// Console.WriteLine(item);
//}
Console.ReadLine();

}
public static void Main()
{
TestKth_Samllest_Selection tester = new TestKth_Samllest_Selection();
tester.Init();
tester.test();
}
}
#endregion
}

⑧ 分治法是什麼

分治法可以通俗的解釋為:把一片領土分解，分解為若干塊小部分，然後一塊塊地佔領征服，被分解的可以是不同的政治派別或是其他什麼，然後讓他們彼此異化。

分治法的精髓：

分--將問題分解為規模更小的子問題。

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

合--將已解決的子問題合並，最終得出"母"問題的解。

任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於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)
其中|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;
}

⑩ 演算法導論初中生看不看得懂

看過《演算法藝術與信息學競賽》（劉汝佳、黃亮著）沒？
到這個水平（汗～這個好像不太實際，真的很難）就ok了。
《演算法導論》理論性比較強，就是數據結構+常用演算法。如果忽略裡面的證明之類，還是可以看看的。
建議你先學習搜索、動態規劃、分治法、貪心法之類的演算法，再看《演算法藝術與信息學競賽》里的題目。

電子書下載到http://www.chinaitlab.com/

導航:首頁 > 源碼編譯 > 演算法導論分治法

演算法導論分治法

與演算法導論分治法相關的資料