- 通用基础算法
这部分主要介绍一下8种主要的通用基础算法思想：枚举算法、递推算法、递归算法、分治算法、贪心算法、回溯算法、动态规划算法、模拟算法，附带也会拓展介绍一些其他通用基础算法思想：数值转换算法、高精度求解算法、排序算法、排列组会算法等。
-
- 枚举算法
枚举算法也叫穷举算法或者暴力算法，它的主要思想就是直接遍历所有解决问题的可能的方法，最终找到解决问题的方法。
小时候听过一个有趣的鸡兔问题，“鸡兔四十九，一百个爪子满地走，问有多少只鸡来多少只兔？”
设有i只鸡和j只兔，则由已知可得：
（1）
通过二元一次方程知识很容易解出：i=48，j=1。
这个问题通过枚举算法编程解决也很容易，以下是通过枚举算法解决鸡兔问题的C语言程序。
#include<stdio.h>
#define NUM 49 //鸡兔总共的只数
int main()
{
//声明并初始化变量i,j,n ==>鸡的只数，兔的只数，问题解的标记
int i=0,j=0,n=0;
//循环遍历求解i,j,n
for (i = 1; i <= NUM; i++) {
for (j = 1; j <= NUM; j++) {
//通过判断是否满足求解的约束条件进行求解
if (0 == (i + j) % 49 && 0 == (2 * i + 4 * j) % 100) {
n++;
printf("鸡兔问题的第%d组解为：鸡有%d只，兔有%d只。\n", n, i, j);
}
}
}
printf("鸡兔问题总共有%d组解。\n", n);
return 0;
}
以上程序编译运行后结果如下：
鸡兔问题的第1组解为：鸡有48只，兔有1只。
鸡兔问题总共有1组解。
由于鸡兔问题本质上是正整数的二元一次确定方程组问题，数学方法求解本身就很容易，通过枚举算法求解还不能显示出明显的优势。
再举一个稍微复杂一些的例子，就可以明显看出枚举算法的威力了。例如“百鸡问题”，今有鸡翁一，值钱伍；鸡母一，值钱三；鸡鶵三，值钱一。凡百钱买鸡百只，问鸡翁、母、鶵各几何？（南北朝时的数学著作《张丘建算经》下卷最后一题）
设鸡翁x，鸡母y，鸡雏z则由已知可得：
（2）
通过三元一次方程知识可以解出：x=4t/3-100，y=1=200-7t/3，z=t（t=75，78，81，84）。很明显这个问题相对来说就更难解决了，因为本质上百鸡问题是正整数的三元一次不定方程组问题，不定方程组求解自然要比确实方程组求解难了！以下是通过枚举算法解决百鸡问题的C语言程序。
#define NUM 100 //鸡翁鸡母鸡雏总共的只数
int main()
{
//声明并初始化变量x,y,z,n ==>鸡翁的只数，鸡母的只数，鸡雏的只数，问题解的标记
int x = 0, y = 0, z = 0,n=0;
//循环遍历求解i,j,n
for (x = 0; x <= NUM; x++) {
for (y = 0; y <= NUM; y++) {
for(z=0;z<=NUM;z++){
//通过判断是否满足求解的约束条件进行求解
if (NUM == (x + y + z)&& NUM == (5 * x + 3 * y + z/3) && 0==z%3) {
n++;
printf("百鸡问题的第%d组解为：鸡翁有%d只，鸡母有%d只，鸡雏有%d只。\n", n, x, y,z);
}
}
}
}
printf("百鸡问题总共有%d组解。\n", n);
return 0;
}
以上程序编译运行后结果如下：
百鸡问题的第1组解为：鸡翁有0只，鸡母有25只，鸡雏有75只。
百鸡问题的第2组解为：鸡翁有4只，鸡母有18只，鸡雏有78只。
百鸡问题的第3组解为：鸡翁有8只，鸡母有11只，鸡雏有81只。
百鸡问题的第4组解为：鸡翁有12只，鸡母有4只，鸡雏有84只。
百鸡问题总共有4组解。
通过以上两个例子可以看出，枚举算法可以用于求解确定方程组问题和不定方程组问题，但是对于求解百鸡问题这种更加复杂的不定方程组问题具有更明显的优势。
-
- 递推算法
递推算法，它的主要思想就是从已知初始条件出发，通过某种递推关系，逐步得到解决问题的中间结果和最终结果。根据递推出发推导的先后顺序，递推算法可分为顺推和逆推两种。数列问题特别适合用递推算法，这里以阶乘数列通项问题和斐波那契数列通项问题为例简单介绍递推算法。
阶乘数列通项问题：已知数列{f(n)}其首项f(1)=1,任意相邻两项之间满足f(n)=n * f(n-1)，求解阶乘数列第n项。以下是阶乘数列通项问题递推算法的C语言程序。
#include<stdio.h>
int main()
{
//声明并初始化变量第n项阶乘数列f，阶乘的阶数n
int n=0,f=1;
//输入要求解的阶乘的阶数n
printf("请输入要求解阶乘的阶数：");
scanf_s("%d", &n);
printf("\n");
//递推求解第n项阶乘数列f
for (int i = 1; i <= n; i++) {
f *= i;
}
printf("第%d项阶乘数列f=%d\n",n, f);
return 0;
}
以上程序编译运行后结果如下：
请输入要求解阶乘的阶数：10
第10项阶乘数列f=3628800
斐波那契数列通项问题：已知数列{f(n)}其首项f(1)=f(2)=1,任意相邻三项之间满足f(n+1)= f(n) + f(n-1)，求解斐波那契数列第n项。以下是斐波那契数列问题递推算法的C语言程序。
#include<stdio.h>
int main()
{
//声明并初始化变量第n项斐波那契数列f，斐波那契数列的阶数n
int n = 0, f1 =1,f2 = 1,f=f1+f2;
//输入要求解的斐波那契的阶数
printf("请输入要求解斐波那契数列的阶数：");
scanf_s("%d", &n);
printf("\n");
//递推求解第n项斐波那契数列f
if (1 == n) {
f = f1;
printf("第%d项斐波那契数列f=%d\n",n, f);
}
else if (2 == n) {
f = f2;
printf("第%d项斐波那契数列f=%d\n", n, f);
}
else {
for (int i = 3; i <= n; i++) {
f1 = f2;
f2 = f;
f = f1 + f2;
}
printf("第%d项斐波那契数列f=%d\n", n, f);
}
return 0;
}
以上程序编译运行后结果如下：
请输入要求解斐波那契数列的阶数：10
第10项斐波那契数列f=89
-
- 递归算法
递归算法的思想类似于分形或俄罗斯套娃，通过一层层递进调用自身、直到无法继续调用自身归返从而最终解决整个问题。网上有个解释递归有趣的说法：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。难怪L. Peter Deutsch大师说：To Iterate is Human, to Recurse, Divine。正如维基百科中所说，递归算法主要解决以下三类问题：
1、数据的定义是按递归定义的。如Fibonacci函数。
2、问题解法按递归算法实现。如Hanoi问题。
3、数据的结构形式是按递归定义的。如二叉树、广义表等。
递归算法解决问题常见的除了斐波那契数列问题和汉诺塔问题，还有分割平面问题，卡塔兰数问题，斯特林数问题、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解等。这里以斐波那契数列问题和汉诺塔问题为例稍作展示。
斐波那契数列通项问题：已知数列{f(n)}其首项f(1)=f(2)=1,任意相邻三项之间满足f(n+1)= f(n) + f(n-1)，求解斐波那契数列第n项。以下是斐波那契数列问题递归算法的C语言程序。
#include<stdio.h>
template<typename T>
T fibonacci(T n) {
if (1 == n || 2 == n) {
return 1;
}
else return fibonacci(n - 1) + fibonacci(n - 2);
}
int main()
{
//声明并初始化变量第n项斐波那契数列f，斐波那契数列的阶数n
unsigned long long n = 0, f =0;
//输入要求解的斐波那契的阶数
printf("请输入要求解斐波那契数列的阶数：");
scanf_s("%llu", &n);
printf("\n");
//递推求解第n项斐波那契数列f
f = fibonacci(n);
printf("第%d项斐波那契数列f=%llu\n", n, f);
return 0;
}
以上程序编译运行后结果如下：
请输入要求解斐波那契数列的阶数：10
第10项斐波那契数列f=55
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。问至少要挪动多少次圆盘才能完成游戏？设汉诺塔数列通项为f(n)：分析可知f(1)=1、f(2)=3,任意相邻两项之间满足f(n)= 2f(n-1)+1。以下是汉诺塔数列问题递归算法的C语言程序。
#include<stdio.h>
template<typename T>
T hanoi(T n) {
if (1 == n) {
return 1;
}
else{
return 2* hanoi(n - 1) + 1;
}
}
int main()
{
//声明并初始化变量第n项汉诺塔数列f，汉诺塔数列的阶数n
unsigned long long n = 0, f = 0;
//输入要求解的汉诺塔的阶数
printf("请输入要求解汉诺塔数列的阶数：");
scanf_s("%llu", &n);
printf("\n");
//递推求解第n项汉诺塔数列f
f = hanoi(n);
printf("第%d项汉诺塔数列f=%llu\n", n, f);
return 0;
}
以上程序编译运行后结果如下：
请输入要求解汉诺塔数列的阶数：64
第64项汉诺塔数列f=18446744073709551615
