《第2章C语言.ppt

第2章 程序的灵魂—算法 具体课程目标 列出解决问题的步骤 研究算法 绘制流程图 学会流程图中使用的符号 理解结构化程序设计 入门 计算机用来 进行计算. 解决问题. 程序 提供给计算机来解决问题的一套指令. 一个程序包含两方面的内容 １．对数据的描述 类型、数据的组织形式 ? 数据结构 ２．对操作的描述 操作步骤 ? 算法 认真考虑和设计： 数据结构和算法 什么是程序？ 沃思公式： 　数据结构＋算法＝程序 具体化： 程序＝ 算法＋数据结构＋程序设计方法＋语言工具和环境　 编程过程 问题解决 一个复杂的过程. 算法 解决问题所使用的一系列合乎逻辑的、简洁的步骤. 解决问题包含的步骤: 仔细研究问题. 搜集相关的资料. 处理相关的信息. 得到结果. 编程过程(举例) 检查一个数是奇数还是偶数的步骤: 读入这个数. 用2来除这个数. 如果余数是零,那么这个数是偶数. 否则这个数是奇数. 算法解决的问题是 　做什么和怎么做(计算机) 算法 解决问题所使用的一系列合乎逻辑的、简洁的步骤就称为“算法” 做任何事都有一定的次序和步骤 如：召开会议，报考大学，购物等 解决同一个问题可以有不同的方法和步骤，方法有有劣之分 采用简单的和运算步骤少的方法为优 计算机算法两大分类 数值运算算法 目的是求数值解，算法成熟 非数值运算算法 种类繁多，要求各异，难以规范 　 简单算法举例 例　2.1　求１×２×３×４×５ 原始方法： １×２,２×３,６×４,２４×５ 通用的方法: 设两个变量（被乘数p,乘数i） S1: 1=p S2: 2=i S3: p×i=p S4: i+1=i S5: 若i≤5,返回s3;否则输出结果结束 如果题目该为求1×3×5×7×9×11 ? S1: 1=p S2: 3=i S3: p×i=p S4: i+2=i S5: 若i≤11,返回s3;否则结束 用这种方法表示的算法具有通用性、灵活性 例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来．用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生的学号，g代表学生成绩 　gi代表第i个学生成绩．算法如下： S1: 1=i S2: 若gi≥80则打印ni和gi，否则不打印 S3: i+1=i S4: 若i≤50返回s2，否则算法结束 例 2.3 判断2000-2500年中的每一年是否闰年，将结果输出 闰年的条件： ①能被４整除，但不能被100整除的年份都是闰年，如1996,2004年是闰年； ②能被100整除，又能被400整除的年份是闰年，如1600,2000年是闰年。 不符合这两个条件的年份不是闰年。 设y为被测的年份，即有： S1: 2000=y S2: 若y不能被４整除则转到S5 S3: 若y能被４整除，不能被100整除，则输 出y “是闰年”，转S6 S4: 若y能被100整除，又能被400整除，则输出y “是闰年”， 转S6，（否则顺序执行） S5: 输出y“不是闰年” S6: y+1=y S7: 当y≤2500时转S2，否则算法结束 例2.5对一个大于等于３的正整数，判断它是否为素数． 素数：除了１和该数本身之外，不能被其他任何整数整除的数． 如：13 判断素数的方法：将一个大于等于３的正整数n作为被除数，将 ２到 n-1各个数轮流作为除数，如果都不能被整除，则n为素数． S1: 输入n的值 S2: ２=i　 S3: n被i整除，得余数r S4: 若r=0，表示n能被i整除，则n不是素数，算法结束；否则顺序执行到S5 S5: i+1=i S6: 若i≤n-1，返回S3；否则n是素数，算法结束 或S6:若i≤n/2或若i≤ 2.3算法的特性 一个算法应具有以下特点: 有穷性 确定性 有零个或多个输入 有一个或多个输出 有效性 程序设计人员必须会设计算法,并根据算法编 写程序 算法的表示方法 1.自然语言描述:用自然语言给出解决问题的详细步骤. 2.流程图：以图解的方式表明操作步骤，一般比较常用 流程图 以图解方式说明实现一个解决方案所需完成的一系列操作. 为了达到下列目的: 一目了然,比文字描述易懂. 程序可以很容易地查看和修改. 提供有效的程序文档. 解释程序和讨论解决方案变得容易. 流程图里常用的符号 流程图示例 连接符 在为复杂问题准备流程图时 流程图可能无法放在一页中 要将所有的图块直接连接起来比较困难 流程图可以被分割成若干部分. 连接符可以用于指定连接的位置. 在连接符中指定了一个唯一的数. 在图表断开的地方,一个箭头指示了那一点. 连接