分治算法小結（附例題詳解）
我的了解：
分治算法我的了解就是看人下菜碟，我們要解決的問題就好像一群人構成的集體，要我們解決這個問題，那我們就要滿足這群人裡面每個人不同的需求，也就是寫出解決的代碼，把每個人都解決了，這個群體也就解決了；
例題一：歸并排序；
注意：
歸并排序的重點在合并的時候要将已經排過數不在進行排序，否則會進行多次重複的比較，浪費時間
代碼
#include<iostream>
#include<vector>
using namespace std;
void sortnum(vector<int>& num, int start, int end)
{
int mid = -1;
vector<int> temp;
int i = start;
int j = 0;
mid = (start + end) / 2;
j = mid + 1;
int nb = 0;
while (i <= mid && j<= end)
{
if (num[j] < num[i])
{
nb = num[j];
temp.push_back(num[j]);
j++;
}
else
{
nb = num[i];
temp.push_back(num[i]);
i++;
}
}
while (i<=mid)
{
temp.push_back(num[i]);
i++;
}
while (j <= end)
{
nb = num[j];
temp.push_back(num[j]);
j++;
}
int k = start;
int l = 0;;
for (; k <= end; k++)
{
num[k] = temp[l];
l++;
}
}
void dividenum(vector<int>& arr, int frist, int end) {
int mid=-100;
if (end>frist)
{
mid = (frist + end) / 2;
dividenum(arr, frist, mid);
dividenum(arr, mid + 1, end);
sortnum(arr, frist, end);
}
}
int main()
{
vector<int> num;
cout << "輸入要排序的數組,輸入-1結束：" << endl;
int nu = -1;
cin >> nu;
while (nu != -1)
{
num.push_back(nu);
cin >> nu;
}
dividenum(num, 0, num.size() - 1);
//sortnum(num, 0, num.size - 1);
int i = 0;
while (i<num.size()-1)
{
cout << num[i] << " ";
i++;
}
}
例題2 快速插入排序：
#include<iostream>
#include<vector>
using namespace std;
void quitsort(vector<int>& num, int start, int end)
{
int temp = 0;
temp=num[start];
vector<int> num2,num3;
num3.push_back(temp);
int i = 0;
int count = 0;
if (end > start)
{
for (i = start + 1; i <= end; i++)
{
if (num[i] < temp)
{
num2.push_back(num[i]);
count = count + 1;
}
else
{
num3.push_back(num[i]);
}
}
//for (int j = 0; j < num2.size(); j++)
//{
// cout << num2[j];
//}
cout << "\n";
//for (i = 0; i < num3.size(); i++)
//{
// cout << num3[i];
//}
cout << "\n";
int mid = 0;
if (count != 0)
{
mid = start + count - 1;
}
else
{
mid = start ;
}
int k = 0;
if (num2.size() != 0)
{
for (i = start; i <= mid; i++)
{
num[i] = num2[k];
k++;
}
}
k = 0;
if(num3.size()!=0)
{
if (count != 0)
{
for (i = mid + 1; i <= end; i++)
{
num[i] = num3[k];
k++;
}
}
else
{
for (i = mid; i <= end; i++)
{
num[i] = num3[k];
k++;
}
}
}
if (mid > -1)
{
quitsort(num, start, mid);
quitsort(num, mid + 1, end);
}
}
//for (i = start; i <=end; i++)
//{
// cout << num[i] << " ";
//}
//int k = start;
//for (; k <= end; k++)
//{
// num2.push_back(num[k]);
//}
/*for (i = start; i <= end; i++)
{
num[i] = num2[i];
}*/
//quitsort(num, start, mid);
//quitsort(num,mid+1)
}
int main()
{
vector<int> num;
cout << "輸入要排序的數組，輸入-1結束：" << endl;
int n = -1;
cin >> n;
while (n!=- 1)
{
num.push_back(n);
cin >> n;
}
quitsort(num, 0, num.size() - 1);
cout << "排序後的結果為：\n";
for (int i = 0; i < num.size(); i++)
{
cout << num[i]<<" ";
}
}
例題3四叉樹問題：
四叉樹編碼的基本思想是：首先将把一副圖像或栅格地圖（ ,k>1,不足則補網）等分成四個一級字塊，順序為左上，右上，左下，右下；然後逐塊檢查其中所有格網屬性值（或灰階值），若相同，則該字塊不再分；若不同，則将該子塊進一步分成四個二級子塊；如此遞歸地分割，直到每個子塊的屬性或灰階均相等為止。
如下圖：
規則：
1：圖像所有像素為黑色，無論大小是多少，壓縮結果全為b;
2:圖像所有像素為白色，無論大小，壓縮結果為w;
3圖像的像素不都是相同顔色，整個圖像的壓縮結果為先把圖像一分為4，然後對4個小圖像進行壓縮，整個的圖像壓縮結果為x,如：下圖a的左上角4個小圖像壓縮結果為：xwwwwb.
下圖的構成的樹是對上圖進行的壓縮結果；
是以圖a的壓縮結果為：
xxwww bxwxw bbbww xxxww bbbww wwbb
我們要解決的就是将壓縮後的圖檔進行上下翻轉；
說明：
可能曉得圖像可以直接解壓然後翻轉，但是像素特别大的圖像是不可能在規定時間内直接解壓完成的。
輸入
xbwxwbbwb
輸出
xxbwwbbbw
代碼：
#include<iostream>
using namespace std;
string change(string::iterator& it)
{
char head = *it;
it++;
if (head == 'b' || head == 'w')
{
return string (1, head);
}
string upleft = change(it);
string upright = change(it);
string lowleft = change(it);
string lowrigiht = change(it);
return string("x") + lowleft + lowrigiht + upleft + upright;
}
int main()
{
string s="xbwxwbbwb";
string::iterator it;
it = s.begin();
string a;
a = change(it);
cout << a << endl;
}
/*
這題結構很簡單，但是有着很深的遞歸結構
注意一點：在本題中疊代器的使用很重要，疊代器的作用類似于指針，
對于疊代器：
定義：疊代器是一種檢查容器内元素并周遊元素的資料類型。
疊代器提供對一個容器中的對象的通路方法，并且定義了容器中對象的範圍
*/
例題3切割籬笆
在一段高度不相同的籬笆木闆中切割出面積最大的長方形，籬笆的寬度都為1；
不允許斜向切割。
此題是中等難度的分治問題，關鍵的地方都在代碼注釋裡寫了；
輸入
木闆數量：7
木闆高度：1 4 4 4 4 1 1
輸出
最大面積： 16
代碼：
#include<iostream>
#include <algorithm>
using namespace std;
/*
本題分為三個子問題：
1 當最大面積在左邊時如何求解；
2 當最大面積在右邊時如何求解；
3 當最大面積在中間時如何求解；
注意：當第三種情況時，可以将闆向兩邊一格一格延伸，每次的
延伸方向總是向着高度更高的木闆延伸，每次計算出來的面積和目前最大面積進行對比較，
這樣可以減少計算量。
*/
int height[100];
int slove( int frist, int end)
{
//第一個遞歸出口，隻剩下一塊闆；
if (frist == end)
{
return height[frist];
}
int mid = (frist + end) / 2;
int permax = 0;//記錄目前最大的面積；
//第二種情況的解決，不斷調用自身求解最大面積
permax = max(slove(frist, mid), slove(mid + 1, end));
//解決第三個問題，橫跨中間時面積的解
int left = 0;
int right = 0;
left = mid;
right = mid + 1;
int hei = min(height[left], height[right]);
permax = max(hei * 2,permax);
while (frist<left || end>right)
{
if (frist<left && right == end || height[left-1]>height[right+1])
{
left--;
hei = min(height[left],hei);
}
else
{
right++;
hei = min(height[right], hei);
}
permax =max(permax,hei * (right - left + 1));
}
return permax;
}
int main()
{
cout << "輸入木闆數量" << endl;
int n = 0;
cin >> n;
cout << "輸入木闆高度:" << endl;
int i = 0;
for (i = 0; i < n; i++)
{
cin >> height[i];
}
int permax = 0;
permax=slove(0, n - 1);
cout << permax;
}
/*
分治算法小結：
1：要了解子問題的概念，分治中的子問題是把原問題分解成多個不同性質的子問題，
和窮舉遞歸時不同；
2在設計遞歸函數是，要先找好遞歸的出口，将所有可能的遞歸出口想全面，
我的方法是先遞歸到最小單元，将可能遇到的情況和解決的函數寫好，在去想遞進和回溯的過程。
因為遞進和回溯涉及到的是過程，也就是參數的傳遞和值得共享，而真正解決問題的是遞歸出口的
代碼，有時候可能我們知道解題的方法和思路，但是在設計遞歸函數的時候總是會思路混亂。
是以就将整個遞歸函數分開看，一個是傳遞參數和共享的值部分，另一個是遞歸出口部分。
*/