C/C++五大常规算法分治算法c/c++m045867846的博客-

分治法

一个装有 16 枚硬币的袋子，16 枚硬币中有一个是伪造的，伪造的硬币和普通硬币从表面上看不出有任何差别，但是那 个伪造的硬币比真的硬币要轻。现有给你一台天平，请你在尽可能最短的时间内找出那枚伪造的硬币。

常规思维：

每次从待比较的硬币中取两枚进行计较，如果天平平衡（相等）就继续取剩下的硬币进行比较

继续以上过程，直到找到硬币。

强者思维:
我们先将 16 枚硬币分为左右两个部分，各为 8 个硬币，分别称重，必然会有一半轻一半重，而我们要的就是轻的那组,重 的舍去。接下来我们继续对轻的进行五五分，直至每组剩下一枚或者两枚硬币，这时我们的问题自然就解决了，下面用一 张图进行更好的理解。
第一次检测:

第二次检测:

第三次检测:

第四次检测:

分治法——见名思义，即分而治之，从而得到我们想要的最终结果。分治法的思想是将一个规模为 N 的问题分解为 k 个较 小的子问题，这些子问题遵循的处理方式就是互相独立且与原问题相同。

两部分组成

分（divide）：递归解决较小的问题
治（conquer）：然后从子问题的解构建原问题的解

三个步骤

1、分解（Divide）：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2、解决（Conquer）：若子问题规模较小而容易被解决则直接解决，否则递归地解各个子问题；

3、合并（Combine）：将各个子问题的解合并为原问题的解。

参考:

#include <stdlib.h> #include <stdio.h> /************************************* * 递归实现二分查找 * 参数: * arr    - 有序数组地址arr * minSub - 查找范围的最小下表minSub * maxSub - 查找范围的最大下表maxSub * num    - 查找的数字 * * 返回: 找到则返回所在的数组下标, 找不到则返回 -1 *  *************************************/ int BinarySearch(int *arr,int minSub,int maxSub,int num) { if (minSub > maxSub) { return -1; /* 找不到num时直接返回 */ } int mid = (minSub + maxSub) / 2; if (num < arr[mid]) { return BinarySearch(arr, minSub, mid - 1, num); } else if (num > arr[mid]) { return BinarySearch(arr, mid + 1, maxSub, num); } else if(num == arr[mid]) { return mid; } } int main() { int arr[] = { 5,7,11,15,19,21,25,26,28,61,99 }; int index = BinarySearch(arr, 0, 10, 26); printf("26在数组下标:%dn", index); system("pause"); return 0; } 

这里画图理解一下

假设查找: 18

运行环境: vs2019
运行结果:

结语:

学到的知识要, 多复习, 多总结, 多敲. 需要时间的积累, 才能引起质的改变. 自己写不出来的永远是别人的.

一下我的技巧: 代数法把具体的数字带进去, 看看能能能找到规律(掌握思想).
还有就是画图, 也很重要. 用笔画出来, 把数代进去, 方法虽然笨, 但真的很实用, 好记忆不如烂笔头!!!

我是小白, C/C++功力…, 你懂得, 写的文章可能不是很好. 如果存在问题, 欢迎大神给予评判指正.
错了不可怕, 可怕的是找不出bug, 谁没错过!!!

最近学操作系统我认为, 学什么都要成本(时间), 即使它是免费的, 我个人认为要挑来学, 挑重点来学, 而不是从头到尾, 除非考试考研.

今日是: 2020年5月9日, (由于疫情的原因)在家里整天坐在电脑前, 眼神逐渐从大到小, 视力也有所大大的下降 ,中午期待打篮球. 写博客,也可自己加强记忆，就当写写日记吧!!!

希望给个赞: 反正你又不亏, 顺便而已