1、Python教学演示文稿12探究如何用计算机解决问题 用算法高效寻找问题答案目 录CONTENTS探究如何用计算机解决问题 学习程序设计，不仅要学习计算机语言的基本语法，更重要的是要学习解决问题的各种算法。无论是用顺序结构、选择结构，还是用循环结构的算法来构造程序，都是为用计算机解决问题提供一种有效的方案。探究如何用计算机解决问题1探究用程序加工数据的过程2用选择结构程序做出判断3用循环结构程序自动化计算微项目1.探究用程序加工数据的过程 一个事物的属性，形状、尺寸、颜色、质量等都是可以用数据来描述的。事物之间的关系，如高低、大小、距离，或者相同、不同也都可以用数据来描述。数据是用计算机解决问
2、题的基本要素。1.探究用程序加工数据的过程 在项目学习过程中，可以参考以下活动建议进行合作学习，分享交流。学习活动过程与目标核心问题编写数据加工程序体验输入、处理、输出数据，认识程序的作用数据加工基本过程用到哪些程序语句探究数据的存储方式尝试在变量、列表中存储数据，了解数据的存储方法变量的类型与用途有何关联“探究用程序加工数据的过程”微项目活动建议1.探究用程序加工数据的过程 活动1 编写数据加工的程序问题描述（样例）：我们要把一笔约10002000元之间的零花钱存在银行，定期一年（如年利率1.50%）。请问1年后的利息（税前）是多少呢？数据及其分析数据的操作10002000之间的不确定的金额
3、数输入，用x表示1.50%的固定数不用输入计算利息y=x*年利率显示利息结果输出y(1-1)1.探究用程序加工数据的过程 活动2 探究数据的存储方式 接下来，让我们使用列表存储一系列的数据。例如，同学们正在讨论的青少年应具有哪些优良品质的主题，可以使用列表存储、管理数据，并进行相关的操作如追加、访问等。(1-2)1.探究用程序加工数据的过程 科学探究 数据类型及其运算1.数字型 数字型包括 int（整数）、float（浮点数，即包含小数）等。2.字符串型 单个的符号称为字符，多个符号称为字符串，二者也通称为字符串。Python中的字符串用单引号（）或双引号（）括起来表示。字符串常用于文本数据的
4、处理，如姓名、地址等。(1-3)3.字符串与数字之间的转换 在用input输入字符后，使用int()函数可以将字符串型数据转换为数字型数据，而str()函数可把数字型数据转换成字符串型使用。1.探究用程序加工数据的过程 技术探索 尝试用文件存储数据 数据在变量中存储，实际上是在内存中存储的，程序结束或断电之后数值将消失。为了永久地保存数据，需要把数据保存在硬盘、U盘等存储介质上。(1-4)2.用选择结构程序做成判断 我们在现实生活中，经常需要根据变化了的客观情况做出判断。如，全班同学组织跳绳比赛，如果比赛当天下雨则在室内举行，否则将在室外操场举行。2.用选择结构程序做成判断 根据算法来设计程序
5、，程序的基本结构分为三种类型，分别是顺序结构、选择结构和循环结构。学习活动过程与目标核心问题根据条件做出判断通过对情况做出判断，掌握选择结构程序的功能条件表达式的作用是什么根据多个条件逐步推断运用多个条件逐步推断出结论，了解选择结构的嵌套选择结构嵌套程序中的多次判断有何联系“用选择结构程序做出判断”微项目活动建议2.用选择结构程序做成判断 活动1 根据条件做出判断 在程序中，条件是由条件表达式来构成的。条件表达式的值只有True（真）、False（假）两种，称为Bool（布尔）型的值。选择结构程序的一般形式如下。if 条件表达式：语句1 语句nelse：语句x 语句m 语句w Python程序
6、缩进很严格，同级别的程序行要缩进并对齐。例如，以上程序中if与else要对齐，语句1到语句n要缩进并对齐。(1-5)2.用选择结构程序做成判断 活动2 根据多个条件逐步判断1.用选择结构的嵌套程序对多种情况进行逐步推断(1)比较a，b的大小并输出它们的大小关系。(1-6)2.用多重选择的程序对多种情况进行逐步推断(1)推断宠物狗的年龄所对应的人的年龄。(1-7)(2)判断测试成绩所对应的评定等级。(1-8)2.用选择结构程序做成判断 科学探究 Python的比较运算符 在构造条件表达式的时候，我们经常需要从不同的角度进行比较，就要用到不同的比较运算符。条件表达式的值是布尔型True或False
7、，用int()可转换成数字型0和1，True对应1，False对应0。这分别与布尔型的值True和False等价。2.用选择结构程序做成判断比较运算符描述实例=比较是否相等(a=b)返回False!=比较是否不等(a!=b)返回True是否大于(ab)返回False是否小于(a=是否大于等于(a=b)返回False=是否小于等于(a=b)返回True 假设变量a为5，变量b为10，请根据下列表中的实例，分析相应的比较运算结果。3.用循环结构程序自动化计算 计算机具有运算速度快、自动化程度高等优势。对于用简单程序无法解决的问题，可以利用自动化处理的方式进行解决。而其中一个很重要的方法就是利用循环
8、结构程序进行控制。3.用循环结构程序自动化计算 循环结构程序有两种类型，一种是计数循环，一种是条件循环。学习活动过程与目标核心问题用计数循环统计程序利用for循环结构来完成已知次数的自动化处理，掌握计数循环结构应用方法循环的初值、终值的作用是什么用条件循环寻找答案利用while循环结构实现未知次数的自动化处理，掌握条件循环结构应用方法如何设定循环条件“用循环结构程序自动化计算”微项目活动建议3.用循环结构程序自动化计算 活动1 用计数循环统计数据用程序模拟抛硬币 在Python中，很多功能需要引入模块，其中有Python标准配置的，也有外来下载安装的。在执行import 命令导入模块之后就可以
9、使用相应的函数、命令。(1-9)3.用循环结构程序自动化计算 活动2 用条件循环寻找答案1.输入正确验证码跳出循环(1-10)2.输入错误时需要更换新的验证码(1-11)3.用循环结构程序自动化计算 科学探究 多重循环 利用循环的嵌套可以构成多重循环，用来解决一些更复杂的问题。比如，我们要输出乘法口诀表，可以用双重循环实现。(1-12)3.用循环结构程序自动化计算 技术探索 寻找内容的循环1.元素查找 对列表中的各个元素进行查找，可以用：元素 in 列表名。对列表中的所有元素全部访问，可以用：for 变量 in 列表名。(1-13)2.字母查找 对英文字符串，还可以对每一个字母进行查找，使用循
10、环完成全部访问。(1-14)用算法高效寻找问题答案 面对一项工作，需要考虑先做什么后做什么，每个决定都会影响整个工作的进度和效率。这些看似生活中才有的困扰，其实在计算机编程时也会遇到，让计算机根据实际需求处理问题时，人们也经常试图寻找更高效的方法。用算法高效寻找问题答案1探讨生活中的算法之美2用枚举算法寻找问题多解3用迭代算法探讨数据变化的规律微项目4 4用排序算法进行数据整理5 5用递归算法优化程序6 6用分治查找算法提高查找效率1.探讨生活中算法之美 日常生活中，几乎所有人都会面临一系列问题。例如，怎样规划景区游览路线来获得超值旅游体验？怎样调整红绿灯设置来有效缓解交通拥堵？这些问题都可以
11、归结为算法问题。解决问题的方法和步骤，我们称之为算法。1.探讨生活中算法之美学习活动过程与目标核心问题用算法提高效率通过生活案例体验算法的用途，了解算法的基本概念算法有什么特点与用途探究算法的应用通过实例探究生活算法和计算机算法的应用生活算法与计算机算法有什么联系“探讨生活中算法之美”微项目活动建议 在项目学习过程中，可以参考以下活动建议进行合作学习，分享交流。1.探讨生活中算法之美 活动1 用算法提高效率1.探究生活中的算法 每一项家务做起来，都需要经历一个相对复杂的过程，例如，炒菜从准备到完成，通常包括择菜、洗菜、切菜、热锅、放食用油、放香料、加菜翻炒、放盐、出锅等环节。那么，泡茶又要经过
12、哪些过程呢？1.探讨生活中算法之美 活动1 用算法提高效率2.根据生活法则探究算法的价值以下面的“37%法则”为例，体会问题中涉及的算法的作用。假设多人申请一个学生会职位，你是面试官。你不知道如何评分，但是可以判断谁更优秀。每次只能面试1个人且不允许重复面试，一旦选定某个人则面试结束。过早或过晚终止遴选程序，都可能错过优秀候选人，从而无法得到理想结果。你将如何选择？1.探讨生活中算法之美 活动2 探究算法的应用1.图书的分类存放(1)对书库图书的分类存放与查找。(2)读者检索。2.网络信息传输中的身份确认算法(1)模拟打电话中的身份确认。(2)网络传输身份确认算法。1.探讨生活中算法之美 科学
13、探究 算法的特征及描述方式1.算法的基本特征(1)有穷性(2)确定性(3)输入、输出(4)可行性2.算法的描述方式算法的描述方式有自然语言、伪代码、流程图、编程语言等。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。如：if 7点以前：锻炼elif 8点到17点：学习else：休息2.用枚举算法寻找问题多解 生活中有很多问题需要把所有可能的答案都列举出来，譬如借助电子地图查询去博物馆的公交路线，就是使用一定的算法逐一挑出所有可能的线路。把问题的所有结果都一一列举出来，并逐个检验出问题真正解的方法，称为枚举算法。2.用枚举算法寻找问题多解学习活动过程与目标核心问题快速寻找有规律的数
14、据通过对枚举对象、范围、条件的构造，体验枚举算法解决问题的思想如何确定枚举对象，枚举范围和判定条件一一列举可行的解决方案借助枚举算法解决问题的思想，找寻解决问题的多种答案组合构建多重循环嵌套，找到所有答案组合“用枚举算法寻找问题多解”微项目活动建议 用枚举算法（也称为穷举法）求解问题，就是从所有候选答案中搜索正确的结果，方法简单但很实用。2.用枚举算法寻找问题多解 活动1 快速寻找有规律的数据 “拍7”游戏，规则如下：把从1起的自然数中含“7”的数称作“明7”；把不含“7”且是“7”的倍数的数称作“暗7”。从1起轮流报数，轮到报“明7”或“暗7”的人，不能出声只拍一下手，报错数或拍错手都算输。
15、假设一起游戏的有33人，请记录经过3轮报数后拍手的数据。(2-1)2.用枚举算法寻找问题多解 活动2 一一列举可行的解决方案 砝码称重问题：现有足量的1 g、2 g、5 g、10 g砝码，共允许取用40枚，现在有100g食盐，要求每种砝码至少使用1枚，共有多少种称重方法？(2-2)2.用枚举算法寻找问题多解 科学探究 使用现代技术验证古代智慧 我国古代就有很多经典的数学问题，表现出中国人的智慧。公元前5世纪，我国古代数学家张丘建在算经中有一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意为：公鸡每只5钱，母鸡每只3钱，小鸡3只1钱。用100钱买10
16、0只鸡，问公鸡，母鸡，小鸡各多少？2.用枚举算法寻找问题多解 技术探索 探索枚举在数字中的应用寻找水仙花数 水仙花数是一个三位数，它的各位数字立方和等于该数本身，如153=13+53+33。请求出所有的水仙花数。(2-3)3.用迭代算法探讨数据变化的规律 “迭代”在汉语词典中解释为“更替、轮换”。而在编程中，迭代则是用旧值重复递推新值的过程。每一次迭代得到的结果会作为下一次迭代的初始值，如此一步步逼近所需目标或得到结果。3.用迭代算法探讨数据变化的规律学习活动过程与目标核心问题观察数据累加的迭代算法分析迭代过程，观察迭代的关系，体验迭代功能迭代的本质是什么用循环结构实现自动迭代用循环程序编写迭
17、代算法，解决实际问题自动迭代如何完成“用迭代算法探讨数据变化的规律”微项目活动建议 前文已经学到过用循环结构程序实现自动化计算的知识，迭代跟循环有着密切的联系。3.用迭代算法探讨数据变化的规律 活动1 用循环结构实现自动迭代 跳绳是一项简单易行的体育运动。为了增强体质，甲乙两位同学各自制订了循序渐进的锻炼方案。甲同学决定每天跳绳100下，第二天开始每天增加5下。乙同学也决定每天跳绳100下，但每隔一天增加10下。这样锻炼30天，各自的总运动量是多少下？看看谁的总运动量大。(2-4)3.用迭代算法探讨数据变化的规律 科学探究 迭代器 迭代器是一个对象，它可以记住访问的位置，表示可迭代的数据集合。
18、迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束，只能往前不会后退。迭代器包括iter()和next()等方法，用以实现迭代功能。列表（list）可以作为迭代对象，通过iter()函数获取迭代器，不断使用next()函数来访问下一个数据。(2-5)3.用迭代算法探讨数据变化的规律 技术探索 Python中数学函数的使用求任意前n个棋盘格的麦粒 在印度有一个古老的传说：舍汗王打算奖赏国际象棋的发明人宰相西萨班达依尔。国王问他想要什么。他对国王说：“陛下，请您在这张棋盘的第1个格子，赏给我1粒麦子，在第2个小格子里给2粒，第3小格里给4粒，以后每一小格都比前一小格多1倍。请您将这样
19、摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”那么，到底需要多少麦粒呢？(2-6)4.用排序算法进行数据整理 生活中经常遇到排序问题，如跑操时按身高排序、选购时按照价格排序、整理数码照片时按照日期排序等。无论生活还是学习，将数据排序有利于高效地进行信息的检索、分类。4.用排序算法进行数据整理学习活动过程与目标核心问题计算选手得分通过查找最大最小数，了解如何进行数据比较如何比较数据大小为选手排名次观察冒泡排序的基本过程，探索序列的生成过程冒泡排序中的数据交换位置如何实现“用排序算法进行数据处理”微项目活动建议 排序，就是按照某种逻辑将杂乱的“无序”数据调整为“有序”，可以为进一步的加工奠定基础
20、。4.用排序算法进行数据整理 活动1 计算选手得分 通过判断先找到12位评委给分中的最大、最小数，以便进行得分计算。(2-7)活动2 为选手排名次 通过计算已经得到了10名参赛选手的得分。按照得分高则名次靠前的原则，需要将10名选手的最终得分按照从大到小进行排序。计算机如何完成对选手成绩的排序呢？(2-8)4.用排序算法进行数据整理 冒泡排序算法的执行过程 所谓冒泡排序，就是从初始位置开始，每次对相邻两个数据进行比较，如顺序无误保持位置不变，顺序错误则交换位置，不断进行下一次比较，直至数据顺序调整完毕。第1轮比较第2轮比较4.用排序算法进行数据整理 科学探究 用列表方法排序 列表（list）是
21、Python中非常重要的数据类型，是一种有序的集合，可以随时添加和删除其中的元素。列表对象的追加、插入、删除、排序等，称为列表方法。格式为列表名.方法()。例如，列表的sort方法，可以实现排序（如果是字符串按首字母进行排序），默认升序。(2-9)4.用排序算法进行数据整理 技术探索 快速简单的桶排序 针对只要求一类数据的排序，还可以使用“桶排序”来快速完成。桶排序的方法是将无序数字记录到编号与之相同的有限数量“桶”里，然后按照顺序将不为空的桶编号逐一输出形成有序序列，即实现排序。(2-10)4.用排序算法进行数据整理 模拟桶排序以5个不大于10的自然数5，6，4，7，9进行排序为例。桶排序初
22、始化桶排序数据标记桶排序数据标记5.用递归算法优化程序 大家尝试过同时照两面镜子吗？站在两面相对的镜子中间，会是什么情景？镜子里会有千百个“你”，而真实的你只有一个，那千百个“你”都来源于你的存在，这如同是“递归”现象。生活中应用递归思想的例子还有很多，如益智玩具九连环、汉诺塔等。5.用递归算法优化程序学习活动过程与目标核心问题跟踪递归的运行过程通过数据跟踪实验，了解递归思想的基本思路和运行过程如何将大问题拆解为子问题探究递归算法的优势通过案例对比枚举与递归算法的不同，探究递归算法的优势递归的优势是什么“用递归算法优化程序”微项目活动建议 递归算法是一种反复调用（引用）自身直到某个条件（也称为
23、终止条件或基线条件）匹配的算法。在程序设计中使用递归算法通常需要定义递归函数，通过对该函数的调用来获得最终解。5.用递归算法优化程序 活动1 跟踪递归的运行过程 下面通过一个累乘过程的跟踪检测小实验来观察递归是如何工作的。假设一个自然数n，累乘是将从1到n的所有自然数相乘，乘积m=12345n。fact(7)7*fact(6)7*(6*fact(5)7*(6*fact(5*fact(4)7*(6*fact(5*fact(4*fact(3)7*(6*fact(5*fact(4*fact(3*fact(2)7*(6*fact(5*fact(4*fact(3*fact(2*fact(1)假设递归求解
24、1到7的自然数乘积，求解过程如下。(2-11)5.用递归算法优化程序 递归算法的条件 递归算法解决问题的核心在于递归函数的构建。因为递归函数不断调用自身，程序如果没有设置停止条件，递归调用会形成无限循环。递归函数的规范形式如下。def 函数名(参数1，参数2，)：if(条件表达式)：#基线条件 语句 return 值(或表达式)#可省略 else：#递归条件 函数名(参数1，参数2，)5.用递归算法优化程序 活动2 探究递归算法的优势 著名的斐波那契数列，又称为“兔子数列”，即1，1，2，3，5，8，13，21，34分别使用递归算法与迭代算法解决这个问题，对比了解两种算法的不同。(2-12)5
25、.用递归算法优化程序 科学探究 自定义函数进行模块化设计 要解决在程序中重复调用某段代码的问题，可以使用自定义函数。与数学中的函数概念不同，计算机科学中的函数指的是一段可重复调用的代码，通过输入参数返回需要的结果。自定义函数定义的格式如下。def 函数名(参数1，参数2，)：#注意结尾有英文冒号 函数主体#可以省略 return 值(或表达式)#可以省略，注意要缩进 例如，以体质测试达标为例，进行函数定义。5.用递归算法优化程序 技术探索 用计算机寻找素数 使用循环寻找素数(2-13)，然后使用递归算法(2-14)进一步优化。6.用分治查找算法提高查找效率 信息世界里的问题规模要大很多，如“在
26、10亿个网页中查找包含单词Python的网页”，这时我们就需要寻找更为高效的方法来缩减查找时间。分治查找算法则是解决这类问题的更优算法之一。分治查找算法的核心思想是分而治之。6.用分治查找算法提高查找效率学习活动过程与目标核心问题逻辑推演抽查游戏通过纸卡查找游戏和亲子阅读抽查，推演分治查找算法分治查找查找的过程是怎样的编程实现分治查找学习Python语言开发的分治查找算法，运行程序，分析代码逻辑分治查找算法的程序如何实现“用分治查找算法提高查找效率”微项目活动建议 通俗地讲，分治查找算法将待求解的问题分割成多个更小规模的“子问题”，如果“子问题”的规模还是不够小，就继续划分“孙问题”，直到问题
27、规模足够小。采用分治查找算法，可以逐步缩减问题的求解范围，从而加快问题的求解速度。6.用分治查找算法提高查找效率 活动1 逻辑推演抽查游戏 学校开展亲子阅读活动，在李明完成阅读任务之后，妈妈会保存一张填写当天日期的计分卡，爸爸将在月初检查上月的完成情况。检查时，李明爸爸会随机指定一个日期（如29），然后查看与它对应的计分卡是否存在；如果存在，就向李明赠送一份神秘礼物。假设8月份李明共获得12张计分卡，日期从小到大依次为1，5，7，8，12，15，18，21，27，29，30，31，李明妈妈已经从1到12编好序号，李明爸爸抽查的日期为x=29。编写Python程序模拟抽查过程。(2-15)6.用
28、分治查找算法提高查找效率 分治查找算法的执行过程6.用分治查找算法提高查找效率 科学探究 分治查找算法执行效率分析 分治查找算法，通常被称作二分查找算法，也叫作折半查找算法，它是最为典型的一种分治查找算法，其优点是执行效率比较高，缺点是对列表有特殊要求（列表必须是有序排列的）。二分查找算法每次循环可以将查找规模缩小一半。当问题规模足够大，如在2017年全国4442.06万初中在校生中查找某个身份证号，最坏的情况下（x值在列表中不存在）循环对比次数不超过30次，与穷举算法的4442.06万次相比，效率提升就非常可观了。6.用分治查找算法提高查找效率 技术探索 分治查找算法解决伪币问题 一个袋子装有16个硬币，硬币编号为1-16，已知其中1个硬币是伪造的，它比真的硬币要轻一些，如何找出伪造硬币的编号？(2-16)解决伪币问题的分治思想
