C语言经典算法详解

a6432943 贡献于2012-08-15

作者 微软用户  创建于2012-02-02 06:21:00   修改者微软用户  修改于2012-02-03 07:05:00字数8733

文档摘要:一分而治之算法分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题,可以:1)把它分成两个或多个更小的问题;2)分别解决每个小问题;3)把各小问题的解答组合起来,即可得到原问题的解答。小问题通常与原问题相似,可以递归地使用分而治之策略来解决。
关键词:

一 分而治之算法 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题,可以: 1) 把它分成两个或多个更小的问题; 2) 分别解决每个小问题; 3) 把各小问题的解答组合起来,即可得到原问题的解答。小问题通常与原问题相似,可以递归地使用分而治之策略来解决。下列通过实例加以说明。 例:利用分而治之算法求一个整数数组中的最大值。 #include //文件包含预处理命令,printf( )函数在其中声明 int Max(int a[], int n); // 求a[0],a[1],...,a[n-1]中的最大值 int main(void) { int a[8] = {9, 3, 8, 1, 10, 5, 190, 180}; int i; printf("数组a:"); for (i=0; i < n; i++) printf("%d ", a[i]); printf("\n最大值为%d .\n", Max(a, 8)); return 0; // 返回值0 } /* 用分而治之算法求一个整数数组中的最大值 */ int Max(int a[], int n) { int max1, max2; if (n == 1) { // 递归结束条件成立,结束递归 return a[0]; } else { // 递归结束条件不成立,继续递归 max1 = Max(a, n - 1); /* 求a[0],a[1],...,a[n-1]的最大值max1 */ /* 求max1和a[n-1]的最大值 */ if (max1 > a[n - 1]) max2 = max1; else max2 = a[n-1]; return max2; } } 练习:[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的,并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。 二 贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。 贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题,往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的,但实际上,用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解,而是次优解。因此,选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下,要选出最优量度标准并不是一件容易的事,但对某问题能选择出最优量度标准后,用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择,即局部最优解选择,然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题,最终可得到问题的一个整体最优解。 贪心算法特性 贪心算法可解决的问题通常大部分都有如下的特性: (1) 有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合:比如不同面值的硬币。 (2) 随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。 (3) 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 (4) 还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。 (5) 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 (6) 最后,目标函数给出解的值。 为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行,那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合,并检查该集合是否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。 贪心算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解,得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步 do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。 例题分析 [背包问题]有一个背包,背包容量是M=150。有7个物品,物品不可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。   物品 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)每次选取单位重量价值最大的物品,成为解本题的策略。   值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。   贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。 可惜的是,它需要证明后才能真正运用到题目的算法中。 一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 对于例题中的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 20 10   根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。 【注意:如果物品可以分割为任意大小,那么策略3可得最优解】 对于选取单位重量价值最大的物品这个策略,可以再加一条优化的规则:对于单位重量价值一样的,则优先选择重量小的!这样,上面的反例就解决了。 但是,如果题目是如下所示,这个策略就也不行了。 W=40 物品:A B C 重量:25 20 15 价值:25 20 15 附:本题是个NP问题,用贪心法并不一定可以求得最优解,以后了解了动态规划算法后本题就有了新的解法。 备注: 贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。 贪心法的应用算法有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; array[0]=1; for(i=1;i=0;i--) { if(r>=array[i]) { r=r-array[i]; cankao[i]=1; } else cankao[i]=0; } } int beibao1(long array[],int cankao[],long value,int n) {/*贪婪算法*/ int i; long value1=0; for(i=n-1;i>=0;i--)/*先放大的物体,再考虑小的物体*/ if((value1+array[i])<=value)/*如果当前物体可以放入*/ { cankao[i]=1;/*1表示放入*/ value1+=array[i];/*背包剩余容量减少*/ } else cankao[i]=0; if(value1==value) return 1; return 0; } void main() { long array[N]; int cankao[N]={0}; int cankao1[N]={0}; int i; long value,value1=0; 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;i #include #define W 80 //迷宫宽的最大值 #define H 60 //迷宫高的最大值 //迷宫单元格状态:VIA:已经过,BLOCK:阻塞(阴影),EMPTY:空 typedef enum{VIA,BLOCK,EMPTY}MazeCellStatus; typedef struct { int x,y; //迷宫单元格的坐标 }CellType; typedef struct { CellType path[W*H]; //经过路径 int length; //经过长度 }MazePathType; //迷宫路线类型、 void OutSolution(MazePathType mazepath); //输出迷宫问题的解 void TrySolution(MazeCellStatus maze[][W],int w,int h, CellType exit,CellType cur,MazePathType mazePath); //试探求解下一位置 void MazeSolution(MazeCellStatus maze[][W],int w,int h, CellType entry,CellType exit); //迷宫问题 void main() { MazeCellStatus maze[H][W]={ {EMPTY,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,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,BLOCK,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 maze[][W],int w,int h, CellType entry,CellType exit) { MazePathType mazePath; mazePath.length=0; //迷宫路线初始长度为0 mazePath.path[mazePath.length].x=entry.x; mazePath.path[mazePath.length].y=entry.y; mazePath.length++; //路径自增1 TrySolution(maze,w,h,exit,entry,mazePath); } void TrySolution(MazeCellStatus maze[][W],int w,int h, CellType exit,CellType cur,MazePathType mazePath) { int i; int xshift[4]={0,0,-1,1}; //相邻位置相对于当前位置x的坐标 int yshift[4]={-1,1,0,0}; //相邻位置相对于当前位置y的坐标 CellType adjCell; //当前位置的相邻位置 if(cur.x==exit.x&&cur.y==exit.y) { //已达到出口,输出解 OutSolution(mazePath); } else { for(i=0;i<4;i++) { adjCell.x=cur.x + xshift[i]; //求相邻位置的x坐标 adjCell.y=cur.y + yshift[i]; //求相邻位置的y坐标 if(adjCell.x>=0&&adjCell.x<=w&&adjCell.y>=0&&adjCell.y<=h&&(maze[adjCell.y][adjCell.x]==EMPTY)) { //相邻位置在迷宫内并且为空白,将相邻位置存于路径中 mazePath.path[mazePath.length].x=adjCell.x; mazePath.path[mazePath.length].y=adjCell.y; mazePath.length++; maze[adjCell.y][adjCell.x]=VIA; TrySolution(maze,w,h,exit,adjCell,mazePath); //对相邻位置进行递归 mazePath.length--; //从路径中去掉adjCell,路径长度将自减1 maze[adjCell.y][adjCell.x]=EMPTY; } } } } void OutSolution(MazePathType mazepath) { static int num=0; int i; printf("第%d条路径:",++num); //num表示当前以求的解得个数 for(i=0;i

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档