ch2 程序的灵魂—算法讲解材料.pptVIP

C 语言 第二讲 主讲教师：谢本亮 CH2 程序设计的灵魂---算法 内容提要： ★ 算法及其算法的表示方法 ★ 结构化程序设计方法 ★ 程序、程序设计和程序设计语言 著名计算机科学家沃思（Nikilaus Wirth)提出： 数据结构+算法=程序 描述数据的类型、组织形式 描述对数据的操作步骤 §2.1 算法概念 做事情都有--方法、步骤（顺序）--决定事情成败 1.算法：计算机求解某一问题而采用的具体方法、步骤 2.两大类计算算法：数值运算算法 与 非数值运算算法 （求数值解、成熟） (事务管理、广泛） 3.算法的特性（P.21）：有穷性、确定性、有效性等 4.算法描述：描述算法的方法有多种 归纳为二大类：①文字 ②图形（符号） §2.2 算法的描述方法 常用的算法描述方法： ① 带序号的自然语言描述（例2.1-例2.5） 易懂却不直观，不严格 ③ N-S图（盒图）：特点：完全去掉了带简装箭头的流程线，算法的所有步骤都写在一个大矩形框（表示简单、符合结构化思想） A P T F A B P A P A 处理 判断 循环 伪代码：用介于自然语言与计算机语言之间的文字及符号来描述 （方便、易懂、便于向计算机语言过渡） ② 流程图：灵活、自由、形象、直观，可表示任何算法 输入/输出 处理 判断 连接点 流程线 起止 例1：计算 ，写出其算法。 自然语言描述： 1.0=S单元 2.1 =n单元 3.S+n =S 4.n+1 =n 5.判断 是，转3；否则转6 6.输出S的值 流程图描述： 0=S 输出S 开始 1=n S+n =S n+1 =n 结束 F T N-S图描述： 0=S 1=n S+n =S n+1 =n 输出S的值 伪代码描述： 0=S 1 =n If S+n =S n+1 =n print S 任何复杂的算法都是由这三种基本结构按一定规律组成 ① 顺序结构 A B B A 操作步骤按书写的顺序执行 a = 3; b = 4; c = a + b; ② 选择结构 A B P P T F A B if (x!=0) y=sin(x)/x; else y=1; §2.3 结构化程序设计方法 一、结构化程序的三种基本结构 1996年提出三种基本结构，用这三种基本结构作为表示一种良好算法的基本单元:顺序、选择、循环 顺序结构 选择结构 循环结构 根据条件P决定是否重复执行循环体中的操作 A P F T 当P为真 A 先判断，后执行 A P F T 直到P为真 A 先执行，后判断 sum=0; i=1; while(i=100) { sum+=i; i++; } sum=0; i=1; do { sum+=i; i++; }while(i=100); §2.3 结构化程序设计方法 二、三种基本结构的共同特点 ① 单入单出口 ② 结构内的每一部分都有机会被执行 ③ 不存在“死循环” 三、结构化程序设计的优点 用三种基本结构组成和程序是结构化程序 优点：易编、易读、易懂、易维护 强调程序设计风格和程序结构的规范化 核心思想：自顶向下，逐步细化，模块化设计，结构化编码 如：学校办公自动化系统 举例：张丘建《算经》是提出“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？（体会编程步骤） 1、分析：cocks + hens + chicks =100 5 * cocks + 3 * hens + chicks/3=100 其中：0≤ cocks ≤ 19 ,0≤ hens ≤ 33, 0≤ chicks ≤ 100 思想：依次取cocks的值域中的值，然后求其余两数，看是否合乎题意 算法描述： cocks=0 当cocks ≤ 19时 {找满足题意的 hens,chicks数 cocks加1 } cocks=0 当cocks ≤ 19时 { hens=0