C语言程序的灵魂-算法.pptVIP

第2章 程序的灵魂—算法 程序通常包含的内容有： （1）数据的描述：指定数据??类型和组织形式（数据结构） （2）操作的描述：编程的操作步骤，也称算法（algorithm) 操作的目的：对数据进行加工处理，以便得到结果。 厨师做菜肴： （1）配料：制作菜肴所需的原料 （2）步骤：制作某项菜肴时将原料按规定的步骤加工成所需的菜肴。;程序设计者编程的步骤： （1）数据结构：程序设计中用到哪些数据及其类型。 （2）操作步骤：编程中对数据加工处理的方法和步骤，即算法。 计算机科学家沃思指出： 数据结构+算法=程序 确切的说，除上述要素外，还要采取结构化程序设计的方法和用何种语言来设施。 程序=数据结构+算法 +程序设计方法+语言工具及环境 ;数据结构： 反映各种类型数据的构造形式，是计算机加工处理的对象。 算法： 为解决某一特定问题而采取的确定的有限的步骤，它是程序设计的灵魂，解决做什么和怎么做。 程序设计方法： 根据数据类型和算法用计算机语言加以实现，程序中的操作语句实际上是算法的具体体现，不了解算法就谈不上程序设计。 语言工具和环境： 用计算机语言编制的程序需相应的编译系统和硬件环境加以实施。;2.1 算法的概念 日常生活中做任何事情都有其方法和步骤，这些方法、步骤就是算法，它要求合理、有序。如某人一天的作习时间就有个算法问题。不同的问题，有不同的方法和步骤，同一问题，不同的人可能有不同的方法和步骤，衡量方法步骤优劣的标准是： （1）思路：清晰、正确。 （2）过程：简单、明了、扼要。 （3）算法：合适 例如：计算1+2+3+4+5…+99+100 算法1：1+2=3、3+3=6、6+4=10、10+5=15、 15+6=21….4851+99=4950、4950+100 =5050;算法2：100+(1+99)+(2+98)+(3+97)+….+(48+52)+(49+51)+50 =100+49*100+50=5050 相对而言：算法2简洁明了、易算。 按数据的处理方式，计算机中的算法可分为： (1)数值运算：求数值的解，如求解方程的根，求函数的定积分。 (2)非数值运算：目前使用范围广泛，如办公自动化处理、图书情报检索等。;数值运算： 算法研究较深入、成熟，如数学程序库中的有关数学问题的求解，已编制成标准的子程序或汇编成册或以文件的形式存储在磁盘、磁带上供人们使用。 非数值运算： 算法一般没有固定的模式，由编程者自己编制，或参考已有类似的算法重新设计解决特定问题的专门算法。排序是非运算算法中研究较为深入的一种。 ;2.2 简单算法举例 例2.1：1×2×3×4×5 原始算法: S1:求1×2得结果2 S2:将2×3得结果6 S3:将6×4得结果24 S4:将24×5得结果120 上述方法虽正确,但较烦琐。 如果求1×2×3×4×5×6×….×99×100，用上述方法求解则要999个步骤。;解决此类问题的通用方法是： 设两个变量：p 存放被乘数和结果 I 存放乘数 S1：p=1 S2：i=2 S3：p×i→p S4：i+1→i S5：若i=5 返回s3 否则算法结束。 此算法较上面的算法具有通用性和灵活性。 ;例2.2 ：有50个学生，要求将他们中成绩在80分以上者打印出来。 设n i 表示第i个学生的学号，g i 表示第 i个学生的成绩，算法如下： S1：1→i S2：如果g i =80 则打印 n i 和g i ,否则不打印 S3：i+1 →i S4：如果i=50, 返回s2,否则算法结束。 其中：i 作下标,用来控制序号 ;例 2.3 ：判2000-2500年中每一年是否闰年 闰年的条件： (1) 能被4整除，但不能被100整除 (2)能被100整除又能被400整除 算法表示如下： 设y：被检查的年份 S1：2000→y S2：若y不能被4整除，则输出y“不是闰年”，然后转向s6 S3：若y能被4整除，不能被100整除，则输出y“是闰年”，然后转向s6 S4：若y能被100整除，又能被400整除，则输出y“是闰年”，然后转向s6 S5：输出y“不是闰年” S6：y+1→y S7：当y≤2500时，转s2继续执行，如果y2500,算法停止。;;例2.5 ：对一个大于或等于3的正整数，判断