呕心之作,一篇博客带你精通五大核心算法

目录

一、分治法

思想原理

具体步骤

例题1

算法结语

二、动态规划算法

思想原理

具体步骤

算法实现

算法结语

三、回溯算法

        算法思想

        基本步骤

        例题2

        算法实现

算法结语

四、贪心算法

        思想原理

基本步骤

例题3

算法实现

算法结语

五、分支定界法

        算法原理

算法步骤

例题

算法实现

算法结语

写在前面：

很多人在刷了很多题之后依然无法解决陌生题型或解题十分困难，有很大一部分原因是没有拥有核心算法思维。在此本人将自己的学习成果分享给大家，文章将由浅入深讲解五大核心算法原理以及应用，对于初级程序员，阅读此文，不论对解题或者开发都有很大帮助。本人代码功力可能稍浅，望诸君大牛多一分包容与理解。

一、分治法

思想原理

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

简单来讲，分治法就是把大问题化解成小问题。

下面通过一个生活中的例子来理解该思想

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

常规解决办法可能是每次拿出两枚硬币比重量，只到遇到两枚硬币重量不等时，重量更轻的那枚就是假币。这题这样比最多需要比8次。时间复杂度:O(n/2)

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

使用分治法此题需要比4次。时间复杂度:O(log2 n)  ，分治法的效率是可见的，如果基数加大效率提升将会大大提高。

具体步骤

两部分组成

分（divide）：递归解决较小的问题

治（conquer）：然后从子问题的解构建原问题的解

三个步骤

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

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

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

可用分治法解决的经典问题之一就是二分查找了

二分查找算法实现

#include <iostream>

using namespace std;

/*

功能:递归实现二分查找

参数:

@arr - 有序数组地址

@minSub - 查找范围的最小下标

@maxSub - 查找范围的最大下标

@num - 带查找数字

返回:找到则返回所在数组下标，找不到则返回-1

*/

int BinarySearch(int *arr, int minSub, int maxSub, int num)

{

if (minSub > maxSub) return -1;

int mid = (maxSub + minSub) / 2;

if (arr[mid] == num) return mid;

else if (arr[mid] < num) return BinarySearch(arr, mid + 1, maxSub, num);

else return  BinarySearch(arr, minSub, mid - 1, num);

}

int main()

{

int arr[] = { 1,9,11,22,69,99,100,111,999,8888 };

cout << "输入你要查找的数：" << endl;

int num;

cin >> num;

int index = BinarySearch(arr, 0, 9, num);

if (index == -1)

{

cout << "Not found!";

}

else

{

cout << "数的下标：" << index << ", 值：" << arr[index] << endl;

}

}

例题1

例题一：

如果机器人 一次可以上 1 级台阶，也可以一次上 2 级台阶。

求机器人走一个 n 级台阶总共有多少种走法。

分治法核心思想 ： 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的子问题

比如总共有 5 级台阶,求有多少种走法；由于机器人一次可以走两级台阶，也可以走一级台阶，所以我们可以分成两个情况：

1、 机器人最后一次走了两级台阶，问题变成了“走上一个 3 级台阶，有多少种走法？”

2、 机器人最后一步走了一级台阶，问题变成了“走一个 4 级台阶，有多少种走法？”

我们将求 n 级台阶的共有多少种走法用 f(n) 来表示，则

f(n) = f(n-1) + f(n-2);

由上可得 f(5) = f(4) + f(3);

f(4) = f(3) + f(2);

f(3)

算法实现

/*递归实现机器人台阶走法统计

参数:n - 台阶个数

返回: 上台阶总的走法 */

int WalkCout(int n)

{

if(n<0) return 0;

if(n==1) return 1; //一级台阶，一种走法

else if(n==2) return 2; //二级台阶，两种走法

else

{ //n 级台阶， n-1 个台阶走法 + n-2 个台阶的 走法

return WalkCout(n-1) + WalkCout(n-2);

}

}

算法结语

总体来讲，分治法思维较为简单，因为分解思维存在，常常需要使用递归、循环等，常见的使用分治法思维的问题有：合并排序、快速排序、汉诺塔问题、大整数乘法等。

二、动态规划算法

思想原理

问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

具体步骤

分析优化解的结构

递归地定义最优解的代价

自底向上地计算优化解的代价保存之，并获取构造最优解的信息

根据构造最优解的信息构造优化解

动态规划特点

把原始问题划分成一系列子问题；

求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间

自底向上地计算。

整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）

现在请大家回头看一下例题一，上面的代码中存在很多重复的计算？

比如: f(5) = f(4) + f(3)

计算分成两个分支：

  f(4) = f(3)+f(2) = f(2) + f(1) + f(2);

f(3) = f(2) + f(1);

上面红色的部分就是重复计算的一部分！

下面使用动态规划与分治法实现

算法实现

#include <iostream>

#include<assert.h>

using namespace std;

/*

如果机器人 一次可以上 1 级台阶，也可以一次上 2 级台阶。

求机器人走一个 n 级台阶总共有多少种走法。

*/

//分治思想

int GetSteps(int steps)

{

assert(steps>0);

if (1 == steps) return 1;

if (2 == steps) return 2;

return GetSteps(steps - 1)+ GetSteps(steps - 2);

}

//动态规划思想

int GetSteps2(int steps)

{

assert(steps > 0);

int *values=new int[steps+1];

values[1] = 1;

values[2] = 2;

for (int i=3;i<=steps;i++)

{

values[i] = values[i - 1] + values[i - 2];

}

int n = values[steps];

delete values;

return n;

}

算法结语

动态规划和分治法思想较为相似，都涉及将问题化解为子问题求解，但动态规范强调的是重复，当你看到或意识到可分为多个相关子问题，子问题的解被重复使用时，就要考虑使用动态规划了。

三、回溯算法

算法思想

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

如果尝试求解的空间是一棵树：那么可以理解为

在问题的解空间中，按深度优先遍历策略，从根节点出发搜索解空间树。

算法搜索至解空间 的任意一个节点时，先判断该节点是否包含问题的解。如果确定不包含，跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续深度优先搜索。

回溯法解问题的所有解时，必须回溯到根节点，且根节点的所有子树都被搜索后才结束。

回溯法解问题的一个解时，只要搜索到问题的一个解就可结束。

基本步骤

1. 定义问题的解空间

2. 确定易于搜索的解空间结构

3. 以深度优先搜索的策略搜索解空间，并在搜索过程中尽可能避免无效搜索

例题2

例题2：

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以 从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。

如果一条路径经过了 矩阵的某一格，那么该路径不能再次进入该格子。

例如在下面的 3×4 的矩阵中包含一条字符串 “bfce”的路径（路径中的字母用下划线标出）。

但矩阵中不包含字符串“abfb”的路径，因为 字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子

1

这个问题相当经典，难度适中，建议先独立思考。

解题思路：

首先，在矩阵中任选一个格子作为路径的起点。

如果路径上的第 i 个字符不是待搜索的目标字 符 ch，那么这个格子不可能处在路径上的第 i 个位置。

如果路径上的第 i 个字符正好是 ch，那么往相邻的格子寻找路径上的第 i+1 个字符。除在矩阵边界上的格子之外，其他格子都有 4 个相邻的格子。

重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。

由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识 路径是否已经进入每个格子。

当矩阵中坐标为（row, col）的格子和路径字符串中相应的字符一 样时，从 4 个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符, 如果 4 个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字 符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。

算法实现 

#include <iostream>

#include<assert.h>

using namespace std;

/*

名企面试题： 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以 从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。

如果一条路径经过了 矩阵的某一格，那么该路径不能再次进入该格子。

例如在下面的 3×4 的矩阵中包含一条字符串 “bfce”的路径（路径中的字母用下划线标出）。

但矩阵中不包含字符串“abfb”的路径，因为 字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，

路径不能再次进入这个格子。

A B T G

C F C S

J D E H

*/

/*探测一个字符是否存在*/

bool isEqualSimpleStr(const char *matrix, int rows, int cols, int row, int col, int &strlength, const char * str,bool *visited);

/*

功能: 判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

参数:

@ 矩阵

@ 矩阵行数

@ 矩阵列数

@ 待查字符串

返回值：如果矩阵中存在 str 则返回 true ，否则返回 false

*/

bool IsHasStr(const char *matrix, int rows, int cols, const char *str)

{

if (matrix == nullptr || rows < 1 || cols < 1 || str == nullptr) return false;

int strLength = 0;

bool *visited = new bool[rows*cols];

memset(visited, 0, rows * cols);

for (int row=0;row<rows;row++)

for(int col=0;col<cols;col++)

{

if (isEqualSimpleStr( matrix, rows, cols, row, col, strLength,str,visited))

{

//delete [] visited;

return true;

}

}

delete [] visited;

return false;

}

bool isEqualSimpleStr(const char *matrix, int rows, int cols, int row, int col, int &strlength, const char * str, bool *visited)

{

if (str[strlength] == '\0') return true;//如果找到了字符串的结尾 则代表矩阵中存在该字符串路径

bool isEqual = false;

if (row>=0&&row<rows && col>=0&&col<cols

&& visited[row*cols+col]==false

&& matrix[row*cols+col]==str[strlength])

{

strlength++;

visited[row*cols + col] == true;

isEqual = isEqualSimpleStr(matrix, rows, cols, row, col - 1, strlength, str, visited)

|| isEqualSimpleStr(matrix, rows, cols, row, col + 1, strlength, str, visited)

|| isEqualSimpleStr(matrix, rows, cols, row - 1, col, strlength, str, visited)

|| isEqualSimpleStr(matrix, rows, cols, row + 1, col, strlength, str, visited);

if (!isEqual) //如果没找到

{

strlength--;

visited[row*cols + col] == false;

}

}

return isEqual;

}

int main()

{

const char* matrix =

"ABTG"

"CFCS"

"JDEH";

const char* str = "BFCE";

bool isExist = IsHasStr((const char*)matrix, 3, 4, str);

if (isExist)

cout << "matrix中存在 " << str << " 字符串的路径" << endl;

else

cout << "matrix中不存在 " << str << " 字符串的路径" << endl;

}

算法结语

回溯算法常常用在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。

四、贪心算法

思想原理

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 [1]  。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择（百度百科）

基本步骤

 建立数学模型来描述问题

 把求解的问题分成若干个子问题

 对每一子问题求解，得到子问题的局部最优解

 把子问题对应的局部最优解合成原来整个问题的一个近似最优解

例题3

假设 1元、2元、5元、10元、50元、100元的纸币分别有c0，c1，c2，c3，c4，c5，c6张

现在要用这些钱来支付K元，至少要用多少张纸币？

这是一个贪心算法最最经典例题，用贪心算法思想每次都找最好的结果，显然每次都要选面值最大的纸币

算法实现

#include<iostream>

using namespace std;

/*

假设 1元、2元、5元、10元、50元、100元的纸币分别有c0，c1，c2，c3，c4，c5，c6张

现在要用这些钱来支付K元，至少要用多少张纸币

*/

int money_Type_Count[6][2] = { {1,20},{2,5},{5,10},{10,2},{50,2},{100,3} };

/*

功能:获取支付这些钱需要纸币的张数

参数： @金额

返回值：返回需要纸币的张数，如果找不开返回-1

*/

int getPaperNums(int Money)

{

int num = 0;

for (int i=5;i>=0;i--)

{

int tmp = Money / money_Type_Count[i][0];

tmp = tmp > money_Type_Count[i][1] ? money_Type_Count[i][1] : tmp;

cout << "给你 " << money_Type_Count[i][0] << " 的纸币" << tmp << " 张" << endl;

num += tmp;

Money -= tmp * money_Type_Count[i][0];

}

if (Money > 0) return -1;

return num;

}

int main()

{

int money;

cout << "请输入金额:" << endl;;

cin >> money;

int num = getPaperNums(money);

if (num == -1)

{

cout << "抱歉，你的钱不够" << endl;

}

else

{

cout << "一共给了 " << num << " 张纸币" << endl;

}

}

算法结语

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

五、分支定界法

算法原理

分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。(百度百科)

分支定界 (branch and bound) 算法是一种在问题的解空间上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用 广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

算法步骤

1 ．产生当前扩展结点的所有孩子结点；

2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；

3 ．将其余的孩子结点加入活结点表；

4 ．从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

例题

布线问题：

如图所示，印刷电路板将布线区域划分成n*m个方格。精确的电路布线问题要求确定连接方格a的中点到b的中点的布线方案。在布线时，电路只能沿直线或直角布线，如图1所示。为了避免线路相交，已经布线的方格做了封锁标记（如图1中阴影部分），其他线路不允许穿过被封锁的方格。

2

解题思路：

题目的要求是找到最短的布线方案，从图的情况看，可以用贪婪算法解决问题，也就是从a开始朝着b的方向垂直布线即可。实际上，贪婪算法策略是行不通的。因为已布线的放个没有规律的所以直观上说只能用搜索方法去找问题的解。

根据布线方法的要求，除边界或已布线处，每个结点分支扩充的方向有4个：上、下、左、右，也就是说，一个结点扩充后最多产生4个活结点。

搜索以a为第一个结点，以后不断扩充新的活结点，直到b结束（当然反之也可以）。反过来从b到a，按序号8-7-6-5-4-3-2-1就可以找到最短的布线方案。从图3中也可以发现最短的布线方案是不唯一的。且由此可以看出，此问题适合用分支限界搜索。

算法实现 

注：代码有内存泄露，本人已注意到这点，为了很好地展示算法逻辑，并没有处理。

/*

布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。

精确的电路布线问题要求确定连接方格a的中点到b的中点的布线方案。

在布线时，电路只能沿直线或直角布线，

所示。为了避免线路相交，已经布线的方格做了封锁标记（如图1中阴影部分）

，其他线路不允许穿过被封锁的方格。

*/

#include <iostream>

#include <queue>

#include <list>

using namespace std;

typedef struct _Pos

{

int x, y;

struct _Pos* parent;

}Pos;

int Move[4][2] = { 0,1,0,-1,-1,0,1,0 };

queue<Pos*> bound;

void inBound(int x,int y,int rows,int cols, Pos * cur,bool *visited,int *map);

Pos *Findpath(int *map,Pos start, Pos end,int rows,int cols)

{

Pos *tmp = new Pos;

tmp->x = start.x;

tmp->y = start.y;

tmp->parent = NULL;

if (tmp->x == end.x && tmp->y == end.y &&tmp->y == end.y)

return tmp;

bool *visited = new bool[rows*cols];

memset(visited, 0, rows*cols);

visited[tmp->x*rows + tmp->y] = true;

inBound(tmp->x, tmp->y, rows, cols,tmp,visited,map);

while (!bound.empty())

{

Pos * cur = bound.front();

if (cur->x == end.x && cur->y == end.y)

return cur;

bound.pop();

inBound(cur->x, cur->y, rows, cols, cur,visited,map);

}

return NULL;//代表没有路径

}

void inBound(int x, int y, int rows, int cols,Pos*cur,bool *visited, int *map)

{

for (int i = 0; i < 4; i++)

{

Pos *tmp = new Pos;

tmp->x = x + Move[i][0];

tmp->y = y + Move[i][1];

tmp->parent = cur;

if (tmp->x >= 0 && tmp->x < rows && tmp->y >= 0

&& tmp->y < cols && !visited[tmp->x*rows + tmp->y]

&& map[tmp->x*rows + tmp->y]!=1)

{

bound.push(tmp);

visited[tmp->x*rows + tmp->y] = true;

}

else

delete tmp;

}

}

list<Pos *> getPath(int *map, Pos start, Pos end, int rows, int cols)

{

list<Pos*> tmp;

Pos * result = Findpath(map, start, end, rows, cols);

while (result!=NULL && result->parent!=NULL)

{

tmp.push_front(result);

result = result->parent;

}

return tmp;

}

int main()

{

int map[6][6] =

{0,0,1,0,0,0,

0,0,1,0,0,0,

0,0,0,0,0,0,

1,1,1,0,0,0,

0,0,0,0,0,0 };

Pos start = { 1,1,0 };

Pos end = { 4,4,0 };

list<Pos*> path = getPath(&map[0][0], start,end,6, 6);

cout << "路径为:" << endl;

for (list<Pos*>::const_iterator it=path.begin();it!=path.end();it++)

{

cout << "(" << (*it)->x << "," << (*it)->y << ")" << endl;

}

system("pause");

}

3

则代表了路径

4

算法结语

算法按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。

从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法还有  最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个 耗费或收益。 假

如要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小

耗费的活结点；假如要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活

结点表中具有最大收益的活结点。

博文结语

五大核心算法对于面试、解题、开发过程中的作用是巨大的，然而这种思维影响往往是很直观体现。本文旨在抛砖引玉。程序员大牛们势必掌握更多算法思维，核心算法早已烂熟于心，因此在常规开发和创新开发上效率往往很高。如果此文对你有所帮助，请一键三连支持一下吧！博主与将你共同进步！

https://blog.csdn.net/weixin_40582034/article/details/119287571?utm_source=app&app_version=4.8.1