活动1 让计算机猜价格 课件 沪科版信息技术九年级上册.ppt

03、分析问题新知讲解1、要解决的问题如下:有一件价格不高于100元的商品(价格为整数)，现要让计算机猜测其实际价格每次猜测后，可以通过输入告知计算机猜测价格与实际价格的大小关系，那么，如何用尽可能少的次数猜.为了简化问题，我们设定本活动中涉及的待查找序中商品的实际价格?列是一个从1开始的连续正除了顺序查找外，还可以采用二分查找法。二分整数序列，即第n个数的值查找法也称折半查找法，是一种效率较高的查找方法等于n。新知讲解2、除了顺序查找外，还可以采用二分查找法。二分查找法也称折半查找法，是一种效率较高的查找方法。我们将所有可能价格按从小到大的顺序排列，以中间值为界，将其余数值分为中间值前、中间值后两个部分。在查找时，先将中间值与目标值比对，如果相等则查找成功，如果不相等则比较中间值与目标值的大小，并判断出目标值处于中间值前还是中间值后。将目标值所在区间再次分为中间值、中间值前和中间值后重复之前的操作，直到查找到目标值为止。新知讲解3、中间值的选择可按如下规则进行:假设最低价格为low，最高价格为high，则取(low+high)/2为中间值，计算结果舍去小数位。例如，设价格范围为1到9，实际价格为3，则三次查找即可找出实际价格。第一次查找，取中间值5，与目标值3比较，由于53，可知目标值在中间值前。新知讲解4、第二次查找，在1到4之间，取中间值2，与目标值3比较，由于23，可知目标值在中间值后。第三次查找，在3到4之间，取中间值3，与目标值比较，发现两者相等，查找完成。新知讲解提示板5、在使用二分查找法时，所有可能价格可以按从小到大的顺序排列，也可以按照从大到小的顺序排列，但不能无序排列。顺序查找法则没有排序限制，我们可以将所有可能价格任意排列，之后从第一个数字开始向后验证。新知讲解6、针对1到100之间的任意整数，使用二分查找法，最多需要多少次查找?使用顺序查找法，最多需要多少次查找?哪种查找方法效率相对更高?答：在1到100之间的整数中使用二分查找法最多需要7次查找，这是因为每一次查找都会将待有哪些信誉好的足球投注网站范围减半，直到找到目标数字或者有哪些信誉好的足球投注网站区间缩小到为空。在1到100之间的整数中使用顺序查找法最多需要100次查找。这是因为顺序查找法需要逐个地检查每个数字，直到找到目标数字或者有哪些信誉好的足球投注网站完整个范围。因此，可以看出二分查找法的效率更高，因为它的时间复杂度为O(logn)，而顺序查找法的时间复杂度为O(n)。在大部分情况下，当数据量较大时，二分查找法通常比顺序查找法更高效。04、设计算法新知讲解1、二分查找法需要多次执行相似操作，因此，可以使用循环结构。另外，每次猜测后要判断猜测价格与实际价格的大小关系，需要使用选择结构。如下所示，中间值用变量mid表示。每次查找后，将mid与实际价格比对，若相等则查找成功:若mid大于实际价格，则在low到mid-1间继续查找:若mid小于实际价格则在mid+1到high间继续查找。新知讲解2、可以设置变量i来统计查找次数，每次查找时i加1，查找完成后输出实际价格的值和查找次数。算法流程图如图3-1-1所示。05、编写程序新知讲解1、用Pvthon编写如图3-1-2所示的程序。新知讲解2、猜到正确答案后，程序不再需要执行下一次循环。这时可以使用break语句，在循环条件仍然成立的情况下终止循环。新知讲解3、尝试画出顺序查找算法的流程图，写出相应程序，比较两种查找算法的不同不同点：在大部分情况下，当数据量较大时，二分查找法通常比顺序查找法更高效。06、运行、调试程序新知讲解1、随意设想一个1到100间的整数，运行程序，当计算机做出猜测后，告知计算机猜测结果与答案间的大小关系，重复几次后计算机将猜出正确答案观察运行结果，分析程序有无错误。若有，尝试解决。新知讲解2、二分查找法要求待查找数据有序排列，但如果此条件不满足，就需要先排序再查找。上网学习并参考“知识链接”，了解冒泡排序法。冒泡排序1、从第一个元素开始，依次比较相邻的两个元素，如果顺序不对则交换它们。2、继续对每一对相邻元素进行同样的操作，直到最后一对元素。3、重复以上步骤，直到没有任何一对元素需要交换为止。新知讲解3、算法的效率针对同一个问题，可以采用不同的算法。虽然不同算法得出的最后结果是相同的，但它们的效率却可能大不相同。例如，查找算法的效率取决于查找的次数。与顺序查找法相比，二分查找法的效率要高得多，但二分查找法必须基于有序排列的数据。对手查找规模(数据量)较小的无序数据，顺序查找法也是一种常用的方法。新知讲解4、