(
课件网) 复习巩固 算法的定义: 所谓算法就是解决问题的方法和步骤。 算法可以使用自然语言,也可使用流程图来描述。 流程图具有形象、直观的特点。利用流程图,可以很好的表现出程序执行过程中的三种基本结构组成—顺序结构、选择结构、循环结构等。 图形 名称 含义 起止框 流程图的开始或结束 处理框 表示执行一个步骤 输入或输出框 表示需要用户输入或由计算机自动输出的信息 判断框 根据条件判断,选择其中一个分支 流程图 表示流程的方向 算法的优化 洗水壶 1、首先把9个硬币分成3等分,第一组第二组和第三组; 2、其次,拿任意两组放在天平上,如果天平重量相等,那假的就在最后一组里; 3、再其次拿最后一组三个硬币里面任意两个放在天平上,找出轻的那个,如果两个硬币一样重,那剩下一个就是假的。 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 常见的排序方法:冒泡排序、快速排序法 排序: 12 -3 4 8 -5 -3 12 4 8 -5 -3 4 12 8 -5 -3 4 8 12 -5 第一轮排序后: -3 4 8 -5 12 第二轮排序后: -3 4 -5 8 12 第三轮排序后: -3 -5 4 8 12(
课件网) 算法的优化2 1、理解算法优化的意义 2、学会用不同算法解决问题,并能对算法进行优化 3、学会多视角分析问题,能利用高效方法解决问题 4、养成细致缜密思考问题的习惯 学习目标 练一练 一位商人有9枚银币,其中有1枚略轻,是假银币,你能用天平(不用砝码)将假银币找出来吗?请给出最优化的算法。 方法 最多比较次数 最少比较次数 稳定性 4-4-1 3-3-3 练一练 3 1 不稳定 2 2 稳定 排序的算法优化 排序的算法优化 所谓“排序”,就是使一串记录按照其中的某个或某些关键字的大小递增或递减排列的操作。 排序的算法优化 排序方法包括: 冒泡排序 选择排序 插入排序 希尔排序 快速排序 ………等 冒泡排序 这个算法的名字由来是因为元素会经由交换慢慢“浮”到数列的顶端,就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。 冒泡排序 2 1 3 4 5 冒泡排序 1 3 4 5 2 冒泡排序 1 3 4 5 2 冒泡排序 2 3 4 5 1 冒泡排序 2 3 4 5 1 冒泡排序 2 4 5 1 冒泡排序 4 5 快速排序 75 23 44 43 55 12 64 77 33 44 75 55 64 77 43 12 23 33 44 基准值 第一次划分 快速排序 44 75 55 64 77 43 12 23 33 55 64 75 77 23 43 12 33 55 64 77 33 12 43 44 55 64 75 77 23 33 12 43 查找的算法优化 在计算机应用中,查找是常用的基本算法。快速高效地查找到需要的信息,是对计算机查找功能的一个重要要求。 查找的算法优化 想一想 64 22 35 . . 41 . . 8 123 顺序查找 41 想一想 1 2 3 . . 50 . . 99 100 猜数字:1-100直接猜数字,每猜一次都会告诉你大了、小了或者对了,如果用顺序查找,需要猜多少次? 你能用尽量少的次数猜出来吗? 二分法查找 13 25 7 4 2 1 50 二分查找:先找有序数列的中点,利用中点将范围分为两部分,再经比较不断找中点并一步一步逼近目标,最后按要求确定一个较小范围。 1-100的范围 最少用 次 最多用 次 1 7 ... ...