在韦氏辞典中算法定义为：A procedure for solving a mathematical problem in a finite number of steps,即“在有限步骤中解决数学问题的过程。”如果在计算机中，我们也可以把算法定义成：“为了解决某项工作或某个问题，所需要有限数量的机械式或重复性指令于计算步骤”。也可以将算法定义为规则的集合，是为了解决特定问题而规定的一系列操作。

不过我个人的想法认为算法是一种思维，编程语言是与计算机对话的工具，那算法就是与计算机对话的思维，给计算机下达准确且符合解决问题逻辑的命令。

常见算法介绍

1.分治法

如其名，分治法就是分而治之，我们可以用分治法来逐一拆解复杂的问题，核心思想就是将一个难以解决的大问题依照相同的概念分割成两个或者更多的子问题，以便各个击破。

举个例子，以人工的方式将散落在地上的稿纸从第1页整理并排序到第100页，可以有两种做法。一种是逐一拣起稿纸，并逐一按页码顺序插入到正确的位置。但是这样有个缺点，就是排序和整理的过程较为繁杂，而且比较浪费时间。另一种方法是采用分治法的原理，先将1页到10页的稿纸放一起，11页到20页的放一起，依次类推将91页到100页的稿纸放一起，也就是说将原先的100页分类为10个页码区间，然后分别对10堆页码进行处理，再将页码从小到大分组放在一起（和蜘蛛纸牌类似）。类似于归并排序，快速排序等都有应用。

再举一个具体的编程例子。


 
#include<stdio.h>
#define N 100010;
int n , q[N] ,tmp[N];
 
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
 
    int mid = (l + r)/2;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
 
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
 
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
 
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
 
int main()
{
    scanf("%d",&n);
    int i = 0; 
    for(i = 0; i < n; i++) scanf("%d",&q[i]);
    merge_sort(q ,0 ,n - 1);
    for(i = 0; i < n; i++) printf("%d ",q[i]);
    return 0;
}


这就是核心模板了看着抽象但其实一步一步拆开理解就简单了
步骤：
    1.确定分界点(把一组数分成两部分分别进行处理，这里也是这个归并排序的思想-分治思想)
    2.递归排序
    3.归并(把两个有序的数组合为一个)-这一步有难度
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return; 其中l是排序的左边界，r是排序的右边界，这是确保在数组q[]中 l - r区间内有数
 
    1.确定分界点
    int mid = (l + r)/2;
 
    2.递归排序
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
 
    3.归并
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
 
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
 
    这步是把tmp[]中的数传到q[]中
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

2.递归法

递归是一种很特殊的一种算法，分治发和递归法很相像，都是将一个复杂的算法问题进行分解，让规模越来越小，最终使子问题容易求解。简单来说，对程序设计人员的实现而言，”函数“（或称为子程序）不单纯只是能够被其他函数调用的程序，在一些程序设计语言中（如c语言，c++等）还提供了自己调用自己的功能，这就是所谓的”递归“。

递归的定义，可以这样来描述：假如一个程序或子程序是由自身所定义的或调用的，就称为递归。所以它至少定义两个条件，包括一个可以重复执行的递归过程与一个跳出执行过程的出口。

以一个简单的n！递归函数为例


#include<stdio.h>
int fact(int i)
{
    int sum;
    if(i == 0)
        return (1); 递归终止的条件，跳出递归过程的出口
    else
        sum = i * fact(i -1); sum = n * (n - 1),反复执行的递归过程
}
 
int main()
{
    int n ,cnt = 0;
    scanf("%d",&n);
    cnt = fact(n);
    printf("%d",cnt);
    return 0;
}

递归经常用在排序，深搜（dfs），排列型或组合型枚举。我认为不用着急，刚学算法的话（纯小白）就打基础，这只是个介绍。（ps：我也刚学还不太熟练，哈哈哈）

3.贪心法

又叫做贪婪算法，从某一起点开始，就是在每一个解决问题的步骤中使用贪心原则，即采用在当前状态下最优的的选择，不断的改进该解答，持续在每一个步骤中选择最佳的方法，并且逐渐逼近给定的目标，当达到某一步骤不能在继续前进的时候算法停止，以尽可能块的求解。

贪心法的中心思想虽然是把求解的问题分成若干个子问题，不过不能保证求得的最终解是最佳的，贪心法容易过早的做决定，只能满足某些约束条件可行解的范围，不过在有些问题中却能很好的利用。以下分别举两个例子说明可以使用的和不可以使用的情况。

1.找零钱问题：

假设有数目不限的面值为20,10,5,1的硬币,给出需要找零数，求出找零方案，要求：使用数目最少的硬币。

对于此类问题，贪心算法采取的方式是找钱时，总是选取可供找钱的硬币的最大值。比如，需要找钱数为25时，找钱方式为20+5，而不是10+10+5。


#include<stdio.h>
void getmoney(int m[],int k,int n){
    int i = 0;
    for(i = 0; i < k; i++)
    {
        while(n>=m[i])
        {
            printf("%d ",m[i]);
            n=n-m[i];
        }
    }
    printf("\n");
}
int main()
{
    int n;  // n是需要找零数  
    scanf("%d",&n);
    int money[]={20,10,5,1}; //money[]:存放可供找零的面值,降序排列。
    int k;   //k:可供找零的面值种类数,即m[]的长度;
    k=sizeof(money)/sizeof(int);
    getmoney(money,k,n);
    return 0;
}

2.不适合用贪心法的情况：

贪心法也适用于旅游某些景点的判断，假如我们要从点5走到点3，最短路径该怎么走？

以贪心算法来说，当然是先走到点1最近，再走到点2，再从点2走到点3，总距离为28，因为贪心法是每一步最短路径，而此时整体上看最短距离是点5直接到点3是20，所以说它有时候不能适用整体最优解。

4.动态规划法

动态规划法类似于分治法，用于研究多阶段决策过程的优化过程与求的一个问题的最优解（和贪心算法刚好相反，是求整个过程的最优解）。其主要做法是：如果一个问题答案与子问题相关，就能将大问题拆解成小问题，但是与分治法最大的不同是可以让每一个子问题的答案都被储存起来，以供下次求解时直接取用，这样的做法不但能减少再次使用的时间，并可将这些解组合成大问题的解答，因此动态规划可以解决重复计算的问题。

例如，前面斐波拉契数列采用的是类似分治法的递归法,如果改用动态规划法，那么以及算过的数据就不必重复计算了，也不会往下面递归。下面用斐波那契数列的第4项数Fib(4)，那么它的递归过程可以用下图表示。

从上图可知在递归调用了9次，而执行加法运算4次，Fib(1)和Fib(0)共执行了3次，重复计算影响了执行性能。可以用以下修改。


核心代码
int output[1000] = { 0 };
 
int fib(int n)
{
    int result = 0;
    result = output[n];
    if(result == 0)
    {
        if(n == 0)
            return 0;
        else if(n == 1)
            return 1;
        else 
            return(fib(n-1) + fib(n - 2));
        output[n] = result;;
    }
    return result;
}

5.迭代法

当无法使用公式一次求解，一些情况下可以使用迭代。简单来说就是运用一定次数的循环，多次运用公式知道求出结果。循环必须加入控制变量的起始值及递增或递减表达式，并且在编写循环过程时必须检查离开循环体的条件是否存在，如果条件不存在，就会让循环体一直执行而无法停止，导致“无限循环”。循环结构通常需要具备以下3个要件：

（1）变量初始值。

（2）循环条件判断表达式。

（3）调整变量的增减值。

下面以for循环求一个1！~ n！之和的阶乘程序表示（就是正常的循环结构）


#include <stdio.h>
int main()
{
    int i,j,n,sum=1;
    scanf("%d",&n);
    for(i=0;i<=n;i++){    /*0~n的阶乘*/ 
        for(j=i;j>0；j--) /* n!=n*(n-1)*（n-2)*...*1 */
            sum *=j；/*sum=sum*j*/
        printf("%d!=%3d\n",i,sum);
        sum=1;
    }
    return 0;
}

6.枚举法

枚举法（又称穷举法）是一种常见的数学方法，是我们在日常工作中使用比较多的一种算法，其核心思想就是列举所有的可能。根据问题要求，逐一列举问题的解答，或者为了便于解决问题,把问题分为不重复、不遗漏的有限种情况，逐一列举各种情况并加以解决，最终达到解决整个问题的目的。像枚举法这种分析问题、解决问题的方法，得到的结果总是正确的，缺点是速度太慢。

举个例子，1000一次减去1，2，3.......知道哪个数时，相减的结果是负数？


#include<stdio.h>
int main()
{
	int x = 0,num;
	scanf("%d",&num);//输入1000
	while(num >= 0)
	{
		num = num - x;
		x = x + 1;
	}
	printf("%d",x - 1);
	return 0;
}

7.回溯法

回溯法（Backtracking）也算是枚举法中的一种。对于某些问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，同时避免枚举不正确的数值。一旦发现不正确的数值，就不再递归到下一层，而是回溯到上一层，以节省时间，是一种走不通就退回再走的方式。它的特点主要是在搜索过程中寻找问题的解，当发现不满足求解条件时，就回溯（返回），尝试别的路径，避免无效搜索。适用于一些问题：全排列（dfs），汉诺塔等问题。

举例：全排列。给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。我们假设对于小写字母有 'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入格式


输入只有一行，是由一个不同的小写字母组成的字符串，已知字符串的长度在11到66之间。
例如：abc

输出格式


 输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：
输出：
    abc
    acb
    bac
    bca
    cab
    cba


#include<stdio.h>
#include<string.h>
char a[101],c[101];
int n,book[101];
void dfs(int step)
{
	int i = 0;
	if(step == n)
	{
		for(i = 0 ; i < n ; i ++)
			printf("%c",c[i]);
		printf("\n");
		return;
	} 
	for(i = 0 ; i < n ; i++){
		if(book[i] == 0){
			c[step] = a[i];
			book[i] = 1;
			dfs(step + 1);
			book[i] = 0;
		}
	}
	return ;
}
int main()
{
	scanf("%s",&a);
	n = strlen(a);
	dfs(0);
	return 0;
}

结语

大概的挑了几个经典的算法介绍，本章节只做非常粗浅的介绍，具体的算法和应用以及所合用的情况和题目会在后续补上。我也在学习算法基础后面会补充一些算法题的题集和详解。还是前面说的算法只是方便你去选择更有效的方法去得到结果，方便也是相对的，比如说同样的题不同的人倾向于运用不同的算法去解题，也有人选择暴力解法（根据题意直接写）。不过学习算法的最好方式永远是把算法实现出来。尽可能去系统的学习算法能快的适应学习算法的节奏。推荐《啊哈算法》和《图解算法（使用c语言）》。两个都比较好理解，适合入门用。B站上直接搜《啊哈算法》具有课程。《图解算法》对算法能力提升不大，但是定义和介绍挺全的，也是我写这篇文章的参考书。图书的图片放在末尾了，一般学校的图书馆里面都有的，可以去计算机类的书库找找。

还有就是希望得到大家的一键三连支持，大家一起努力吧。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/858843