第二章—算法—2010.pptVIP

填空题 1 .函数体以符号______开始，以符号______结束。 2 .一个完整的C程序至少要有一个______函数。 3. C程序是以______为基本单位，整个程序由______组成。 4. C源程序文件的扩展名是______，C目标文件的扩展名是______。;第 二 章 ;主要内容;（一）算法在程序中的地位 一个程序应包括的两个方面： （1）对数据的描述 在程序中要指定数据的类型和数据的组织形式，即数据的结构。 （2）对操作的描述 即操作步骤，也就是算法。 数据和操作的关系： 数据是操作的对象，操作的目的是对数据进行加工，以得到期望的结果。;著名计算机科学家沃斯（Nikiklaus Wirth）提出了一个公式： 数据结构 + 算法 = 程序 在设计程序时，还要考虑采用好的设计方法-------结构化程序设计方法。因此有： 程序 = 数据结构 + 算法 +程序设计方法+语言工具和环境 以上4个方面是一个程序设计人员应具备的知识。设计一个程序时要综合运用这几方面的知识。 本门课程重点讲述算法的设计。;上述四个方面中： 算法是灵魂； 数据结构是加工对象； 语言是工具； 编程需要采取合适的方法。 算法解决做什么和怎么做的问题。 程序中的按一定顺序列出的操作语句，就是算法的体现。 通过本门课，大家学会使用c语言的语法编写不太复杂的c程序。;（二）算法的概念;（三）简单算法举例;改进的方法（或通用的方法）： 先设两个变量p和i，p代表被乘数，i代表乘数。并且将每一步乘积直接放入被乘数变量p中。用循环算法求结果。 步骤1：令p=1 步骤2：令i=2 步骤3：使p×i,并将乘积放入p中。通常表示为 p × i = p 步骤4：使 i 的值加1，表示为 i+1= i 步骤5：如果i 不大于5，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。 想一想: 采用此方法求1 × 2×3×...×100，如何？ 简练！;先设两个变量p和i，p代表被乘数，i代表乘数。并且将每一步乘积直接放入被乘数变量p中。用循环算法求结果。 步骤1：令p=1 步骤2：令i=3 步骤3：使p × i,并将乘积放入p中。通常表示为p×i =p 步骤4：使 i 的值加2，表示为 i+ 2 = i 步骤5：如果i 不大于13，返回到步骤3继续向下执行；否 则算法结束。p中的值即最后结果。 想一想: 采用此方法求1 × 3×5×...×101，如何？ ;思考：求下式的值，怎么写算法？;例2：有两个数a,b，按大小顺序打印它们。 步骤1： 输入a,b的值； 步骤2： 如果a≥b,则先打印a，再打印b； 否则，先打 印b，再 打印a；算法结束。 ;例3：将2000-2500的闰年输出。 ; 步骤7：当y=2500时，转到S2继续执行；否则结束。;算法的5个特性： 有穷性 确定性 有零个或多个输入 有一个或多个输出 有效性;二、算法的表示;（一）用自然语言表示算法;（二） 用流程图表示算法;例1的算法用流程图来表示;例2的算法用流程图来表示;步骤1： y=2000 步骤2：如果y不能被4整除，输出“y不是闰年”，转到S6； 步骤3：如果y能被4整除，且不能被100整除，输出“y是闰年”，转到S6; 步骤4：如果y能被100，且能被400整除，输出“y是闰年”，转到S6; 步骤5：输出“y不是闰年”; 步骤6：y=y+1 步骤7：当y=2500时，转到S2继续执行；否则结束。 ;（三）三种基本结构;顺序结构： ;选择结构;循环结构（当型---while型）;循环结构（直到型---until型）;三种基本结构的共同点： 只有一个入口； 一个出口； 结构内每一部分都有机会被执行。 结构内不存在死循环。 如条件永远成立时，就成了死循环 已经证明，用上述三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。 由基本结构构成的算法属于结构化的算法 只要符合上述的四个特点的结构，都称为基本结构。;对例1算法的流程图的结构化分析;对例2算法的流程图的结构化分析;用基本结构的组合表示算法，从而去掉了流程线。避免了随意的跳转。 1973年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图。即N-S流程图，也称盒图。 三种基本结构的表示： ;前面的算法用N-S流程图来表示; y=2000; （五）用伪码表示算法; IF x is positive T