C++ 算法分治法个人笔记

一.导入

分治,顾明思议,就是分而治之,把一个大的问题分为若干个子问题,这些子问题遵循的处理方式就是互相独立且与原问题相同。 (那么就可以使用递归解决)

分(divide):使用递归先解决较小的问题

治(conquer): 然后从子问题的解构建出原问题的解

三个步骤:

1: 分解(Divide) : 将原问题分解为若干个规模较小,相互独立,与原问题解决问题相同形式的子问题.

2: 解决(Conquer): 若子问题的解容易解决就解决,否则递归让子问题变成更小的子问题

3: 合并(Combine): 将各个子问题的解合并为原问题的解。

二.源代码

#include 
   
    using namespace std;/************************************** 递归实现分治法*函数作用: 使用分治法在一个数组中找出指定的元素**函数参数: arr - 传入一个从小到大的有序的数组*		   begin - 传入一个区间检查开始的数组下标*		   rear -  传入一个区间检查结束的数组下标*          num - 传入需要查找的元素**函数返回值: 找到元素时返回它所在的数组下标,否则返回-2;****************************************/int divideRule(int* arr,int begin,int rear,int num) {	//如果传入开始的数组下标大于结束的数组下标时   //为什么不是>= ?	//因为在传入开始的数组下标等于结束的数组下标时	//middle 中间的数组下标 就等于这个开始的数组下标或者结束的数组下标	//如公式(检查开始的数组下标3 + 检查结束的数组下标3)/2 = 3;	//这个数组下标中的元素也需要判断	if (begin > rear) { 		return -2;	}		int  middle = 0;	//使用公式得出区间中间的数组下标    //比如: 检查开始的数组下标是0,	//检查结束的数组下标的是 6; (0+6)/2 = 3;	//得出的是比较中间的数组下标,不是绝对中间的	//检查开始的数组下标是1,	//检查结束的数组下标的是 4; (1+4)/2 = 2;	middle = (begin + rear) / 2;		if(arr[middle] == num){		//如果中间下标中的元素 == 需要查找的元素时		//就返回 middle 这个数组下标		return middle;	}	else if (arr[middle] < num) {		//如果中间下标中的元素 小于 需要查找的元素时		//就再次调用divideRule函数 (递归) 把查找区间缩小了		//把 begin 参数改为上一个的中间数组下标加一         //返回 它的结果返回到调用这个函数的地方		return divideRule(arr, middle + 1, rear, num);	}	else { //arr[middle] >num 的情况		//如果中间下标中的元素 大于 需要查找的元素时		//就再次调用divideRule函数 (递归) 把查找区间缩小了		//把 rear 参数改为上一个的中间数组下标减一        //返回 它的结果返回到调用这个函数的地方		return divideRule(arr, begin, middle - 1, num);	}}int main(void) {	int arrayTest[10] = { 10,17,23,32,35,38,43,56,62,64 };	int index = -1;  //找到元素时 ,把元素所在的下标保存在index 这个变量中	index = divideRule(arrayTest, 0, sizeof(arrayTest) / sizeof(arrayTest[0]), 21);	if (index < 0) {		cout << "这个数组中没有您需要查找的元素" << endl;	}	else {		cout << "您查找的元素在这个数组的" << index << "的位置上" << endl;	}	return  0;}