(
课件网) 高中信息技术 必修一 数据与计算 第 二 章 算法与程序实现 第三节 常用算法及其程序实现 当今社会,人们可以借助计算机来解决的问题越来越多,但由于问题类型和复杂程度的不同,很难有解决所有问题的统一算法。因此,只能针对某个或某类问题,通过分析研究,寻找解决问题的适当算法。 课 堂 导 入 某些智能跑步机的配套移动应用程序除了能记录和显示运动过程中人体的各项身体数据,还可以提供丰富的跑步训练课程,让用户可以在科学的课程指导下,达到更好的锻炼,如图 2.17所示。 思考： 如果要在移动应用程序上显示用户跑步训练课程的报表信息,例如显示用户在一周内已经 完成的训练项目和未完成的训练项目等信息,应该如何实现 如果时间跨度延长至一个月,又应该如何实现 一、枚举法 在生活中,人们有时会遇到数字密码锁打不开的情况。遇到这种 情况,大部分人会采用类似的解决方法,那就是逐个数字进行尝试,直 到打开为止,如图2.18所示。这种逐一尝试的方法在算法中被称之 为枚举法,它是处理问题常用的算法思想之一。 图 2.18 数字密码锁 问题所涉及的情况有哪些,情况的种数是否可以 确定; 确定范围 验证条件 这些情况需要满足什么条件才能成为问题的解答。 图 2.19 使用枚举法“挑选苹果”的流程图 表 2.21 “求解最大公约数”的程序 二、枚举法的程序实现 一般,智能跑步机配套的移动应用程序会通过统计报表的形式给用户提供明确的跑步训练课程完成 度信息,用户也可以选择日报表、周报表或月报表进行查看。假设用户设定的某跑步训练课程需要持续一 周,每天需要完成固定的训练内容和时长,完成后的数据会上传到远程服务器上。 1. 请设计算法,显示某用户在训练课程中完成了哪几项训练内容,未完成哪几项训练内容。 2. 选用适当的方法描述算法。 输入:跑步课程中的每日训练内容和对应训练内容消耗的卡路里 数,这些信息由程序自动 读取数据库中存储的数据,不需要用户输入; 输出:完成的项目数和未完成的项目名称; 1.抽象与建模 2. 设计算法 3.编写程序 4. 调试运行 在Python环境中调试运行以上程序,结果显示如下: 假设每项训练内容都有要求的卡路里消耗最低值,请参考以上程序进行编程,实现统计“该用户哪些 训练项目未达标”,请将你的分析和程序填入表 2.22中。 例如,每项训练内容要求的卡路里消耗最低值存储在 mindata[380,580,380,450,380,650,380]中,从 中可以看出“坡度练习”训练要求的卡路里消耗最低值为 650千卡。 请同学们分析一下本题使用枚举法实现的 Python程序,从程序结构的角度上总结枚举法一般需要包含哪几种基本控制结构。 项 目 实 践 表 2.22 算法分析及程序实现表 排序和查找 排序算法,就是如何使得记录按照要求(升序或降序)排列的方法。与枚举法一样,排序算法早在计算 机出现之前就已经被人们在实际生活中使用了。人们可以通过“看一眼”“扫一遍”的方式对两个数据快速 分辨大小,因此可以在较短的时间内对有限的数据快速地进行排序。而计算机只有通过比较才能够分清 两个数(在计算机中不仅仅指数值数据)的大小,从而在排序时要进行反复的比较和交换,但由于计算机具 有高速运算的能力,因此面对大数据量时就比人显得更有优势。 选择排序的基本思想非常直接,每一次从序列的所有元素中先找到最小的,然后放到第一个位置。之 后再看剩余元素中最小的,放到第二个位置……依此类推,就可以完成整个排序工作了。选择排序的关键 是帮助固定位置找到合适的元素。 例如,待排序数据为“456712783923”,使用选择排序算法的排序过程如表 2.23所示。 表 2.23 选择排序算法过程记录表 冒泡排序 快速排序 插入排序 堆排序 归并排序 选择排序 查找算法的效率取决于查找的次数, ... ...
