1 分治思想
(Divide-and-Conquer)
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。
2 分治法解题的一般步骤
(1)分解( Divide ):,将要解决的问题划分成若干规模较小的同类问题;
(2)求解( Conquer):,当子问题划分得足够小时,用较简单的方法解决;
(3)合并(Combine):,按原问题的要求,将子问题的解逐层合并构成原问题的解。
通用框架:用递归的方式划分到一定程度
分解 → 直接或递归求解子问题 → 组合
在递归求解子问题时同样要注意理清递归关系、递归出口、参数设置等问题。
divide_and_conquer(data)
{
if(data数据量较小)直接处理data得到结果,或者有个结束的判断,因为这个是在递归;
else
{
A.将data分为多个部分data1,data2,.....datan
并分别递归调用divide_and_conquer处理各个部分!
B.合并data1,data2,....datan处理之后的结果!
}
}
3 实例1---归并排序
思想:分而治之
每个递归过程涉及三个步骤:
1、 分解:把待排序的n个元素的序列分解成两个子序列,每个子序列包括n/2个元素。
2、 治理:把每个子序列分别调用归并排序MergeSort,进行递归操作。
3、 合并:合并两个排好序的子序列,生成排序结果
归并排序的工作原理:
1、 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。
2、 设定两个指针,最初位置分别为两个已经排序序列的起始位置
3、 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一个位置
4、 重复步骤3直到某一指针达到序列尾
5、 将另一序列剩下的所有元素直接复制到合并序列尾
代码:
//我认为此题的关键时理解了temparray 这个数组,它是临时的存放每一次的排序结果
//分治还有个明显的特点是left和right的下标,也就是说有一个分的标志
void Merge(int* array, int* tempararay, int left, int middle, int right)
{
//左指针尾
int leftend = middle-1;
//右指针头
int rightstart = middle;
int tempIndex = left;
//数组合并后的length长度
int tempLength = right - left + 1;
//相当于排序,把临时的结果放入到tempararay中
while( (left <= leftend) && (rightstart <= right) )
{
if(array[left]<array[rightstart])
{
tempararay[tempIndex++] = array[left++];
}
else
{
tempararay[tempIndex++] = array[rightstart++];
}
}
//判断左序列是否结束
while(left <= leftend)
tempararay[tempIndex++] = array[left++];
while(rightstart <= right)
tempararay[tempIndex++] = array[rightstart++];
//交换临时排序的数据
for(int i=0; i<tempLength; i++)
{
array[right] = tempararay[right];
cout<<array[right]<<" ";
right--;
}
if(tempLength)
cout<<endl;
}
void MergeSort(int* array, int* temparray, int left, int right)
{
if(left < right)
{
//1、分解划分成前后两部分
int middle = (left+right)/2;
//2、对分解治理
MergeSort(array, temparray, left, middle);
//2、对分解治理
MergeSort(array, temparray, middle+1, right);
//3、合并
Merge(array, temparray, left, middle+1, right);
}
}
int main()
{
int a[] = {13,7,8,3,60,50,4};
int len = sizeof(a)/sizeof(int);
//需要申请一块临时的内存保存排序结果
int* b = new int[len];
MergeSort(a,b,0,len-1);
for(int i=0; i<len; i++)
{
cout<<a[i]<<",";
}
}
4 快速排序
分而治之
//一趟排序,每一次一趟之后,前半部分是小的,后半部分是大的
int Partition(int *array, int low, int high)
{
//*array = *(array+low);
int pivotKey = *(array+low);
while(low<high)
{
while(low<high && *(array+high)>pivotKey)
--high;
*(array+low) = *(array+high);
while(low<high && *(array+low)<pivotKey)
++low;
*(array+high) = *(array+low);
}
*(array+low) = pivotKey;
return low;
}
//再写分治法的代码:
void QSort(int *array, int low, int high)
{
if(low<high)
{
//1. 分解
int middle = Partition(array, low, high);
//2. 递归求解
QSort(array, low , middle-1);
QSort(array, middle+1, high);
//3. 合并:由于分解出的两个字序列是就地进行的,所以不需要再次合并
}
}
void BinarySort(int *array, int length, int data)
{
QSort(array,0,length-1);
}
5 循环赛日程
n个选手的比赛日程可以通过n/2个选手的比赛日程来确定,递归调用,直到剩下两个选手的时候,比赛日程就可以很容易的确定
先计算出一部分,然后另一部分赋值
/// <param name="index">起始选手编号</param>
/// <param name="num">选手的人数(因为是分治,所以每次砍半)</param>
void GameCal(int index, int num)
{
if( num == 2)
{
GameList[index-1,0] = index;
GameList[index-1,1] = index+1;
GameList[index,0] = index+1;
GameList[index,1] = index;
}
else
{
//分而递归
GameCal(index, num/2);
GameCal(index + num/2, num/2);
//合并
//将“左下角”填充到“右上角”
//控制横坐标
for(int i=index; i<index+num/2; i++)
{
//控制纵坐标
for(int j=num/2; j<num; j++)
{
GameList[i-1][j] = GameList[(i-1) + num/2][j - num/2];
}
}
//用于将“左上角”填充到“右下角”
//控制横
for(int i=index+num/2; i<index+num; i++)
{
//控制纵坐标
for(int j=num/2; j<num; j++)
{
//对角赋值
GameList[i - 1][j] = GameList[(i - 1) - num / 2][j - num / 2];
}
}
}
}
6 二分搜索法
int BinarySearch(int a[], int &x, int left, int right)
{
while(left < right)
{
int middle = (left + right)/2;
if(a[middle] == x) return middle;
if(a[middle] < x) right = middle - 1;
else left = middle + 1;
}
}
7 最近点对问题
1)蛮力法:
计算每两个之间的距离,然后比较,也就是计算(n-1)与n个元素之间的比较
2)分治法:
a. 找中线把n个元素分成左右两部分分别求得两边的最短距离,然后取两者中的最小者,计为len
b. 在中线两边分别取len的距离。记录该距离范围内点的个数,中线左边有L个元素,右边有R个元素。
c. 求左边元素到右边元素的距离看其是否小于之前记录的len,小则记录下来。
d. 此时的右边元素只取y值和左边元素y值距离小于1的(减少循环次数)。
e. 循环结束即可找到最小的距离
8 Strassen矩阵乘法
9 大整数乘法