2014战德臣《大学计算机计算思维导论》大学计算机第7讲算法程序与计算系统之灵魂课件.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 过路的人！ 这儿埋葬着丢番图． 请计算下列数目， 便可知道他一生经过了多少个寒暑． 他一生的六分之一是幸福的童年， 十二分之一是无忧无虑的少年． 再过去七分之一的生命旅程， 他建立了幸福的家庭． 五年后儿子出生， 不料儿子竟先于父亲四年而终， 年龄不过父亲享年的一半， 晚年丧子老人真可怜， 悲痛之中度过了风烛残年． 请你算一算，丢番图活到多少岁， 才和死神见面？ * * * * * * * * 基本目标: 理解算法类问题求解框架 算法思想的精确表达--算法的数据结构设计(II) (4)小结? Research Center on Intelligent Computing for Enterprises Services, Harbin Institute of Technology 战德臣 哈尔滨工业大学 教授.博士生导师 教育部大学计算机课程教学指导委员会委员 算法思想的精确表达--算法的控制结构设计(I) 算法思想的精确表达--算法的控制结构设计(I) (1)算法设计包括什么? 算法的数据结构设计---问题或算法相关的数据之间的逻辑关系及存储关系的设计 算法的控制结构设计---算法的计算规则或计算步骤设计 如何构造和表达处理的规则，以便能够按规则逐步计算出结果? 如何将数学模型中的数据转为计算机可以存储和处理的数据？ 顺序结构：“执行A，然后执行B”，是按顺序执行一条条规则的一种结构 。 分支结构：“如果Q成立，那么执行A，否则执行B” ，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则的一种结构 。 循环结构：控制指令或规则的多次执行的一种结构---迭代(iteration) 循环结构又分为有界循环结构和条件循环结构。 有界循环： “执行A指令N次”，其中N是一个整数。 条件循环：某些时候称为无界循环，“重复执行A直到条件Q成立”或“当Q成立时反复执行A”，其中Q是条件。 算法与程序的基本控制结构 算法思想的精确表达--算法的控制结构设计(I) (2)怎样表达算法的步骤呢? 流程图的基本表示符号　 矩形框：表示一组顺序执行的规则或者程序语句。 菱形框：表示条件判断，并根据判断结果执行不同的分支。 圆形框：表示算法或程序的开始或结束。 箭头线：表示算法或程序的走向。 算法与程序构造的表达方法：程序流程图 算法思想的精确表达--算法的控制结构设计(I) (3)怎样绘制算法或程序流程图? 三种控制结构的流程图表示方法示意 开始 第1条规则或语句 第n条规则或语句 结束 顺序结构的流程图 开始 条件成 立否？ 是 否 条件成立时执行的规则或语句 结束 条件不成立时执行的规则或语句 分支结构的流程图 循环结构的流程图 初始化部分 开始 循环控制 条件成立？ 修改部分 需循环执行的规则或语句。　 即：循环体 结束 是 否 循 环 结 束 算法思想的精确表达--算法的控制结构设计(I) (4)不同结构的流程图示例? 算法与程序构造的表达方法：程序流程图 循环结构的两种情况的流程图表示方法示意 初始化部分 开始 循环控制 条件成立？ 修改部分 需循环执行的规则或语句 结束 是 否 循 环 结 束 有界循环结构的流程图 (循环次数确定) 初始化部分 开始 循环控制 条件成立？ 修改部分 需循环执行的规则或语句 结束 否 循 环 未 结 束 是 条件循环结构的流程图 (循环次数不确定) 算法与程序构造的表达方法：程序流程图 算法思想的精确表达--算法的控制结构设计(I) (4)不同结构的流程图示例? 欧几里德算法流程图 算法思想的精确表达--算法的控制结构设计(I) (5)算法流程图示例? 算法与程序构造的表达方法：程序流程图 步骤描述法，即用人们日常使用的语言和数学语言描述算法的步骤。 例如：sum=1+2+3+4+…+n求和问题的算法描述 Start of the algorithm(算法开始) (1)输入N的值； (2)设 i 的值为1；sum的值为0； (3)如果 i=N，则执行第(4)步，否则转到第(7)步执行； (4)计算 sum + i，并将结果赋给sum； (5)计算 i+1，并将结果赋给i; (6)返回到第3步继续执行； (7)输出sum的结果。 End of the algorithm(算法结束) 算法思想的精确表达--算法的控制结构设计(I) (6)自然语言表述算法有什么问题? 算法与程序构造的表达方法：步骤描述法 自然语言表示的算法容易出现二