算法初步(基于C语言).ppt

第3章计算机算法初步,3.3递推与迭代法,3.2穷举法,3.1算法的概念,3.1算法的概念,利用计算机求解问题的一般过程（1）问题分析阶段（2）数据结构设计阶段（3）算法设计阶段（4）编码与调试阶段,算法描述在计算机科学的发展过程中，人们已经提出了很多种类的算法描述方法。一种是自然语言的描述方法。鉴于自然语言本身过于灵活且又缺乏严谨性，所以容易产生理解上的歧义。还有一种算法的图形描述方式流程图。它采用一些标准的图形符号描述算法的操作过程，从而避免了人们对非形式化语言的理解差异。,起止框,I/O框,处理框,判断框,调用框,连接框,有向边,常用流程图符号,例1：求解一元二次方程,问题分析假设一元二次方程可以书写成ax2+bx+c=0。可以看出，任何一个一元二次方程都由三个系数a、b、c惟一确定，所以，首先需要用户输入三个系数，然后再根据一元二次方程的求解规则计算最终的结果，并将结果显示输出。,算法描述,#include#includemain()inta,b,c,t;printf(“Inputa,b,c:”);scanf(“%d%d%d”,程序代码,3.2穷举法,概述穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。例如，从某个班中找出所有班干部，需要逐一对每个同学进行查看，判断是否是班干部。这种方法的基本思路就是一一列举每个可能性，逐个进行排查。因此，穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。,穷举法应用实例1：素数的判断所谓素数是指仅能被1和自身整除，且大于等于2的数值。判断一个给定的数值是否是素数是穷举法的典型实例。,例2：判断给定整数是否是素数。,问题分析为了检查一个整数是不是素数，可以采用穷举法。假设给定的整数用x表示，则判断过程就是确认x不能整除以2x-1之间的任何整数。这就需要一一列举出2x-1之间的每个整数进行排查。,算法描述,#includemain()intx,t;printf(“Enteraninteger:”);scanf(“%d”,程序代码,穷举法应用实例2：百钱买百鸡“百钱买百鸡”是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡5枚钱一只，母鸡3枚钱一只，而小鸡3只1枚钱。试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡。,例3：百钱买百鸡。,问题分析从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过100。通过对不同数量的公鸡、母鸡和小鸡进行组合，可以计算出购买这些鸡所用的花费，但这个题目要求找出那些花费正好100枚且鸡的总数也为100只的情况。因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一遍，找出那些符合题目要求的解。,算法描述,#include#includemain()intx,y,z;for(x=0;x=100/5;x+)for(y=0;y10)break;.,continue语句continue语句的形式：continue;只能用在循环里，作用是使最内层循环的循环体的一次执行结束，进入下一次循环。对while和do-while循环，随后动作应当是条件判断；对于for循环，随后动作是变量更新。,Break和continue语句引起的控制转移,计算c,c,break;.,计算c,c,continue;.,s,s,while(c)s,0,0,非0,非0,braek;.,计算c,c,continue;.,计算c,c,非0,非0,0,0,doswhile(c),e1,e2,break;,e3,s,for(e1;e2;e3)s,e1,e2,continue;,e3,s,#includemain()inti=2,m,n,gcd=1;scanf(%d%d”,方法：算法：、初始化（除数i=2最大公约数gcd=1）、输入m,n当除数i小于m,n时做如果能除尽则：最大公约数为i除数加、输出,#includemain()inti,m,n,gcd=