1、C语言经典算法详解一 分而治之算法分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。下列通过实例加以说明。例：利用分而治之算法求一个整数数组中的最大值。#include /文件包含预处理命令，printf( )函数在其中声明 int Max(int a, int n); / 求a0,a1,.,an-1中的最大值 int main(void) int a8 = 9, 3, 8, 1, 10, 5,
2、 190, 180; int i; printf(数组a:); for (i=0; i an - 1) max2 = max1; else max2 = an-1; return max2; 练习：找出伪币 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。二 贪心算法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最
3、优解的近似解。贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后
4、将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优
5、解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。贪心算法特性贪心算法可解决的问题通常大部分都有如下的特性: （1） 有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合：比如不同面值的硬币。 （2） 随着算法的进行,将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。 （3） 有一个函数来检查一个候选对象的集合是否提供了问题的解答。
6、该函数不考虑此时的解决方法是否最优。 （4） 还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。 （5） 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 （6） 最后,目标函数给出解的值。 为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合
7、，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。 贪心算法的基本思路1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步 do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。例题分析背包问题有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但
8、不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： pi最大 约束条件是装入的物品总重量不超过背包容量：wi=M( M=150) （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占重量最小的物品装入是否能得到最优解？ （3）每次选取单位重量价值最大的物品，成为解本题的策略。 值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。 贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很
9、困难。 可惜的是，它需要证明后才能真正运用到题目的算法中。 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下： （1）贪心策略：选取价值最大者。 反例： W=30 物品：A B C 重量：28 12 12 价值：30 20 20 根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。 （2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。 （3）贪心策略：选取单位重量价值最大的物品。 反例： W=30 物品：A B C 重量：28 20 10 价值：28
10、20 10 根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。 【注意：如果物品可以分割为任意大小，那么策略3可得最优解】 对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。 但是，如果题目是如下所示，这个策略就也不行了。 W=40 物品：A B C 重量：25 20 15 价值：25 20 15 附：本题是个NP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。 备注：贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal
11、算法都是漂亮的贪心算法。 贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式 所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确） #include #include #include #include #include #define K 10#define N 10/*从小到大创建物品 k?void create(long array,int n,int k) int i,j; arr
12、ay0=1; for(i=1;in;i+) long t=0; for(j=0;ji;j+) t=t+arrayj; arrayi=t+rand() +1; */void create(long array,int n) int i; array0=1; for(i=1;in;i+) arrayi=2*i; void output(long array,int n) int i; for(i=0;i=0;i-) if(r=arrayi) r=r-arrayi; cankaoi=1; else cankaoi=0; int beibao1(long array,int cankao,long v
13、alue,int n)/*贪婪算法*/ int i; long value1=0; for(i=n-1;i=0;i-)/*先放大的物体，再考虑小的物体*/ if(value1+arrayi)=value)/*如果当前物体可以放入*/ cankaoi=1;/*1表示放入*/ value1+=arrayi;/*背包剩余容量减少*/ else cankaoi=0; if(value1=value) return 1; return 0;void main() long arrayN; int cankaoN=0; int cankao1N=0; int i; long value,value1=0;
14、 system(cls); srand( (unsigned)time( NULL ) ); create(array,N); output(array,N); printf(nInput the value of beibao:n); scanf(%ld,&value); beibao(array,cankao,value,N); for(i=0;iN;i+) if(cankaoi=1) value1+=arrayi; if(value=value1) printf(nWe have got a solution,that is:n); for(i=0;iN;i+) if(cankaoi=1
15、) if(i%5=0) printf(n); printf(%13ld,arrayi); else printf(nSorry.We have not got a solution.n); printf(nSecond method:n); if(beibao1(array,cankao1,value,N)=1) for(i=0;iN;i+) if(cankao1i=1) if(i%5=0) printf(n); printf(%13ld,arrayi); else printf(nSorry.We have not got a solution.n);练习：马的遍历问题。在88方格的棋盘上，
16、从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。三回朔算法在程序设计中,有这样一类问题:求一类解,或求全部解,或求最优解的问题(例如八皇后问题),不是根据某种确定的算法设计法则,而是利用试探和回朔的搜索技术求解. 回朔还是设计递归算法的重要方法,其求解过程实质:是一个先序遍历一棵状态树但是这棵树不是在遍历前预先建立的,而是隐含在遍历过程中.回朔算法的解题思路大体如下：假设问题的解为n元组（x1,x2,x3,x4,xn）,其中xi取值于集合Seti ，n元组的子组（x1,x2,x3,x4,xi）（in）为部分解，应满足一定的约束条件。对于已求得的部分解（x1,x2,x
17、3,x4,xi），再添加xi+1属于Seti+1之后仍满足约束条件，则可得到一个新的部分解（x1,x2,x3,x4,xi+1），继续添加xi+2属于Seti+2，并检查是否满足约束条件，直到添加到xn属于Setn为止。 如果对于所有取值与集合Seti 的xi+1 都不能得到新的满足约束条件的部分解（x1,x2,x3,x4,xi+1），则从当前子组中删去xi ，回朔到前一个部分解（x1,x2,x3,x4,xi-1），重新添加Seti 中未考察过的xi ，看其是否满足约束条件。如此反复进行，直到求到满足条件的问题的解，或者证明问题无解。例：迷宫问题，只能从一个空白位置走到另一个与它相邻的空白位置（
18、上，下，左，右），但不能重复路线。代码如下：#include#include#define W 80 /迷宫宽的最大值#define H 60 /迷宫高的最大值/迷宫单元格状态：VIA：已经过，BLOCK：阻塞（阴影），EMPTY:空typedef enumVIA,BLOCK,EMPTYMazeCellStatus;typedef struct int x,y; /迷宫单元格的坐标CellType;typedef struct CellType pathW*H; /经过路径 int length; /经过长度MazePathType; /迷宫路线类型、void OutSolution(Maze
19、PathType mazepath); /输出迷宫问题的解void TrySolution(MazeCellStatus mazeW,int w,int h, CellType exit,CellType cur,MazePathType mazePath); /试探求解下一位置void MazeSolution(MazeCellStatus mazeW,int w,int h, CellType entry,CellType exit); /迷宫问题void main() MazeCellStatus mazeHW= EMPTY,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,B
20、LOCK,BLOCK,BLOCK,BLOCK, EMPTY,BLOCK,EMPTY,EMPTY,BLOCK,EMPTY,EMPTY,EMPTY,BLOCK,BLOCK, EMPTY,EMPTY,EMPTY,BLOCK,BLOCK,EMPTY,BLOCK,EMPTY,EMPTY,BLOCK, EMPTY,BLOCK,BLOCK,EMPTY,EMPTY,EMPTY,BLOCK,BLOCK,EMPTY,BLOCK, EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BLOCK, EMPTY,BLOCK,BLOCK,BLOCK,BLOCK,BL
21、OCK,BLOCK,BLOCK,EMPTY,EMPTY, ; CellType entry=0,0; /入口位置 CellType exit=9,5; /出口位置 int h=6; /迷宫高 int w=10; /迷宫宽 MazeSolution(maze,w,h,entry,exit);void MazeSolution(MazeCellStatus mazeW,int w,int h, CellType entry,CellType exit) MazePathType mazePath; mazePath.length=0; /迷宫路线初始长度为0 mazePath.pathmazePa
22、th.length.x=entry.x; mazePath.pathmazePath.length.y=entry.y; mazePath.length+; /路径自增1 TrySolution(maze,w,h,exit,entry,mazePath);void TrySolution(MazeCellStatus mazeW,int w,int h, CellType exit,CellType cur,MazePathType mazePath) int i; int xshift4=0,0,-1,1; /相邻位置相对于当前位置x的坐标 int yshift4=-1,1,0,0; /相邻
23、位置相对于当前位置y的坐标 CellType adjCell; /当前位置的相邻位置 if(cur.x=exit.x&cur.y=exit.y) /已达到出口，输出解 OutSolution(mazePath); else for(i=0;i=0&adjCell.x=0&adjCell.y=h&(mazeadjCell.yadjCell.x=EMPTY) /相邻位置在迷宫内并且为空白，将相邻位置存于路径中 mazePath.pathmazePath.length.x=adjCell.x; mazePath.pathmazePath.length.y=adjCell.y; mazePath.le
24、ngth+; mazeadjCell.yadjCell.x=VIA; TrySolution(maze,w,h,exit,adjCell,mazePath); /对相邻位置进行递归 mazePath.length-; /从路径中去掉adjCell，路径长度将自减1 mazeadjCell.yadjCell.x=EMPTY; void OutSolution(MazePathType mazepath) static int num=0; int i; printf(第%d条路径：,+num); /num表示当前以求的解得个数 for(i=0;imazepath.length;i+) print
25、f(%d,%d) ,mazepath.pathi.x,mazepath.pathi.y); printf(n);练习：皇后问题求解：在n*n的棋盘上放置n个皇后，这些皇后中任意两个皇后不能在同一行，同一列，同一条对角线（包括主对角线和次对角线）上。如有解则输出所有合理的解。四穷举法穷举法是一种针对于密码的破译方法。这种方法很像数学上的“完全归纳法”并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试10000次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就
26、是说用我们破解任何一个密码也都只是一个时间问题。 当然如果破译一个有8位而且有可能拥有大小写字母、数字、以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算，其组合方法可能有几千万亿种组合。这样长的时间显然是不能接受的。其解决办法就是运用字典，所谓“字典”就是给密码锁定某个范围，比如英文单词以及生日的数字组合等，所有的英文单词不过10万个左右这样可以大大缩小密码范围，很大程度上缩短了破译时间。 基本思想：首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，直到全部情况通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部
27、情况验证结果均不符合题目的全部条件，则说明该题无答案。特点：算法简单，容易理解，但运算量大。通常可以解决“有几种组合”、“是否存在”、求解不定方程等类型的问题。用循环结构实现。例：一辆卡车违反交通规则，撞人逃跑了。现场三人目击，记下了车号特征：前两位数字相同，后两位数字相同，四位数恰好是一个整数的平方。求该车号。1 将车号假定为aabb，是个四位数，a,b的变化范围是1-92 四位数的范围是1000-9999，某整数的平方是四位数3 预估整数的范围：32的平方是1024，94的平方是8836main( ) int n,a,b ； for (n=32;n=94;n+) * n*n是个四位数 * for(a=1;a=9;a+) * a 的
