第1章–算法介绍
常见算法介绍
分治法：将一个难以直接解决的大问题依照相同的概念分割成两个或者耕作的子问题，其实，任何一个可以用程序求解的问题所需的计算时间都与其规模有关，问题规模越小越容易直接求解。应用于快速排序法，递归算法，大整数乘法等
递归法：加入一个函数或子程序是由自身所定义或调用的，就成为递归。至少要定义两个条件，一个可以反复执行的递归过程与一个跳出执行过程的出口。尾递归：函数或子程序的最后一条语句为递归调用，因为每次调用后，再回到第一次调用的第一条语句就是return语句，所以不需要再进行任何运算工作。
下面以阶乘函数为例：/*输入一个正整数来求其阶乘*/ #include "stdio.h" int main(){ int res,i; printf("请输入一个正整数\n"); scanf("%d",&i); res = factorial(i); printf("%d的阶乘是%d",i,res); } int factorial(int i) { // int sum; if(i==0) /* 递归终止的条件， 跳出递归过程的出口*/ return(1); else return i*factorial(i-1); // sum = i * factorial(i-1); /* 反复执行的递归过程 */ // return sum; }上概述使用阶乘函数的范例来说明递归的运行方式，在系统中具体的实现递归时，则要用到堆栈的数据结构，所有的操作均在这个结构的顶端进行，具有”后进先出“的特性，下面时斐波那契数列问题的求解：
斐波那契数列的第0项是0，第一项是1，之后的各项的值是由其前面两项值相加的结果
/* 计算前n项斐波那契数列的递归程序 */ #include "stdio.h" #include "stdlib.h" int fib(int); /* fib()函数的原型声明 */ int fib(int n) { if(n==0) return 0; else if (n==1||n==2) return 1; else return (fib(n-1)+fib(n-2)); } int main(){ int i,n; printf("请输入要计算到第几项斐波那契数列："); scanf("%d",&n); for (i=0;i<=n;i++) /*计算前n项*/ printf("fib(%d)=%d\n",i,fib(i)); return 0; }贪心法（贪婪算法）：从某一起点开始，就是在每一个解决问题步骤中使用贪心原则，即采取当前状态下最有利或最优化的选择，不断地改进该解答，持续在每一步骤中选择最佳的方法，并且逐步逼近给定的目标，当达到某一步骤不能那个再继续前进时算法停止。
不一定能求得的最后解是最佳的，贪心法容易过早做决定，只能求满足某些约束条件可行解的范围，不过在某些问题中可以得到最佳解，经常用于求图的最小生成树（MST）、最短路径与或哈夫曼编码等动态规划法：如果一个问题答案与子问题相关，就能将大问题拆解成各个小问题，其中与分治法最大不同的地方是可以让每一个子问题的答案被存储起来，已从下次求解直接取用。这样的做法不但能减少再次计算的时间，并可将这些解组合成大问题的解答，故而使用动态规划可以解决重复计算的问题。
根据动态规划思想将斐波那契数列修改如下：#include "stdio.h" #include "stdlib.h" int fib(int); /* fib()函数的原型声明 */ int output[1000]={0}; //fibonacci的暂存区 int fib(int n) { int result; result=output[n]; if (result==0) { if(n==0) return 0; if(n==1) return 1; else return (fib(n-1)+fib(n-2)); output[n]=result; } } int main(){ int i,n; printf("请输入要计算到第几项斐波那契数列："); scanf("%d",&n); for (i=0;i<=n;i++) printf("fib(%d)=%d\n",i,fib(i)); return 0; }迭代法 ：无法使用公式一次求解，而需要使用迭代
例：循环计算计算1!~n!的阶乘程序#include "stdio.h" #include "stdlib.h" int main(){ int i,j,k,n,sum = 1; printf("请输入n="); scanf("%d",&n); printf("%d\n",n); for(i=0;i<=n;i++) /* 0~n的阶乘 */ { for(j=i;j>0;j--) sum*=j; printf("%d!=%3d\n",i,sum); sum=1; } return 0; }注意循环结构通常具备以下三个要点：
- 变量初始值
- 循环条件判断表达式
- 调整变量增减值
枚举法：列举所有可能。结果正确但是缺点是速度太慢。
例：找到1~500之间所有5的倍数(整数)
for(num=1;num<=500;num++) { if(num%5==0) printf("%d是5的倍数\n",num); }回溯法：也算是枚举法的一种，特点是在搜索过程中寻找问题的解，当发现不满足求解条件时，就回溯（返回），尝试别的路径，避免无效搜索
