DJ8--算法与程序设计-v1资料课件.ppt

标准流程图符号含义 符号名称 符 号 功 能 起止框 表示算法的开始和结束 输入/输出框 ? 表示算法的输入/输出操作，框内填写需输入或输出的各项 处理框 ? 表示算法中的各种处理操作，框内填写处理说明或算式 判断框 ? 表示算法中的条件判断操作，框内填写判断条件 注释框 ? 表示算法中某操作的说明信息，框内填写文字说明 流程线 和 表示算法的执行方向 连接点 ? ? 8.1.3 算法的表示方法 8.1 算法 T里保存： 1+2+3+…+K的连加和。 重复进行某种运算，运算对象有规律地变化, 采用循环结构。 例: 给定K值，求1到 K连加和。 循环 开始 输出 T 的值 结束 输入K T+I →T I+1 →I I≤K Y N 1→I，0 →T T=1+2+3+…+K。 1 → I 0 → T T+I→ T(I=1,2,3,…K) 8.1 算法 8.1.4 算法设计与优化 算法执行效率包括时间效率和空间效率两方面，称为时间复杂性（Time Complexity）和空间复杂性（Space Complexity) 对于具体问题，通常有很多不同的解决方法，即不同的算法。不同算法可能就有不同效率，有时候你选择了正确的算法，但却不一定是有效的算法。 算法的复杂度包括时间复杂度和空间复杂度，有时降低时间复杂度（或空间复杂度）是以牺牲空间复杂度（或时间复杂度）为代价的 对于不同的问题，应具体问题具体分析，找出问题的最佳算法。 8.1 算法 [练习与思考8-1] 冒泡排序法为什么很慢？ 假如要给十个数排序，请画出表达冒泡排序法的流程图，并思考这个算法为什么慢？可以通过什么途径解决？ 8.1 算法 8.1 算法 8.2 典型问题的算法设计 8.3 数据结构 8.4 程序设计 第8章 算法与程序设计 第八章 算法与程序设计 对4个数0,2,3,9按从大到小的顺序排序:冒泡法 0,2,3,9 0 - 2 2,0,3,9 0 - 3 2,3,0,9 0 - 9 2,3,9,0 2 - 3 3,2,9,0 2 - 9 3,9,2,0 3 - 9 第一轮（n-1=3）次比较， （n-1=3）次交换 第二轮（n-2=2）次比较， （n-2=2）次交换 9,3,2,0 第三轮（n-3=1）次比较， （n-3=1）次交换 引入 8.2 典型问题的算法设计 8.2.1 成绩排名问题—排序算法 问题描述：在一个班级有30名同学，一次考试每个同学有一个考试成绩，如何将这30名同学的成绩由高至低进行排序？ 问题分析：这是一个排序问题。一般认为，日常的数据处理中有1/4的时间应用在排序上，据不完全统计，到目前为止的排序算法有上千种。 算法设计： 1、用选择排序解决方案 2、用插入排序解决方案 8.2 典型问题的算法设计 8.2.1 成绩排名问题—排序算法 1、用选择排序解决方案 首先在30名同学中找到最高的分数，使其排在第1位； 然后在剩下的分数中再找最高的分数，使其排在第2位； 依次类推，直至所有的分数都已经排完。 这是一种常见的人工实现方式，这种解决方案其实就是计算机排序算法中的选择排序。 8.2 典型问题的算法设计 对5个数5,7,4,2,8按从小到大的顺序排序:选择法 5,7,4,2,8 5 - 2 2,7,4,5,8 7 - 4 2,4,7,5,8 7 - 5 2,4,5,7,8 2,4,5,7,8 第一轮（n-1=4）次比较 第二轮（n-2=3）次比较 完成排序 第三轮（n-3=2）次比较 第四轮（n-2=1）次比较 引 8.2 典型问题的算法设计 选择排序的改进： 以冒泡排序法为基础，在两两比较后，不马上进行交换，而是在找到最大（或最小）的数之后，记录该数的位置(在数组中的下标)，待一轮比较完毕，再将最大（或最小）的数一次交换到位。 8.2 典型问题的算法设计 8.2.1 成绩排名问题—排序算法 2、用插入排序解决方案 首先将第1位同学的分数放在一个队列中； 然后将第2位同学的分数与队列中的第1位同学的分数进行比较，如果分数比其高，则放在后面，如果分数比其低，则放在前面； 然后将第3位同学的分数与队列中的两位同学的分数进行比较，找到一个插入并仍保持有序的位置，将第3位同学的分数插入到该位置； 依次类推，直至将30位同学的分数都插入到相应位置。 这也