【海淀高中信息技术】2.1解决问题的一般过程和用计算机解决问题

算法与程序实现----起始课城市数据大脑处理交通问题通过大数据和云计算，更准更快地处理交通事件城市大脑”让救护车时间缩短一半01高速度、高精度、大存储、自动运行、逻辑判断、不知疲倦计算机的特点是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等一系列的思维活动。美国计算机科学家周以真教授计算思维01为什么要学习算法与程序设计？计算机科学教育的核心是算法设计和编程，这要求学生面对一个给定的现实问题要能够找到一个正确和高效的办法(算法)并将其变成计算机能理解的语言(程序设计语言),进而让计算机计算出人们需要的结果来。像快递员最佳路径算法就是一个典型的现实问题。这个过程并不容易,因为将一个问题抽象并构造一个模型,需要一定的数学基础,还得理解计算机的特点,“指挥”计算机干活。这还涉及欲求解问题的“可计算性”,因为并不是任何问题都可以由计算机求解的。计算机也并不知道什么是“问题”,是人告诉计算机,如何按照一步一步的程序求解。这个过程,就会训练一个人求解问题的能力,相应地,其具备的让计算机做事的思维能力称之为“计算思维”(ComputationalThinking)。我们平常操作计算机(包括手机这些终端设备)仅仅像开关电灯那样简单,并不会使我们具备计算思维能力,而只有通过上述步骤才能训练这样的能力。随着计算机和网络的发展,未来越来越多的工作将和计算(机)有关(据美国政府的统计是51%以上)。我们必须知道如何让计算机做事,起码知道计算机是如何做事的,这就要求普及计算机科学教育(注意:不是计算机教育,也不是信息技术教育)。----摘自《中学生计算机程序设计》中的序中国计算机学会秘书长杜子德项目布置：课下准备课上进行2.1解决问题的一般过程和用计算机解决问题学习目标：经历用计算机解决问题的基本过程，并能应用于实际问题的解决。体验编程解决问题的基本方法，提高学习算法与程序的兴趣，发展计算思维。课例学校胡同两侧停了很多车，此时一辆蓝车与一辆红车相向而行，如何顺利通过？真实问题：胡同里会车分析问题：分析问题：问题可以转换成完成两辆车位置的互换。寻找解决问题的途径与方法：必须借助中间的一个空位置才可完成。先将红车开入空位置，再将蓝车开到红车原先位置，最后红车开到蓝车原先位置。解决问题并验证结果：完成两辆车位置的交换，实现顺利通过。132真实问题：胡同里会车学校胡同两侧停了很多车，此时一辆蓝车与一辆红车相向而行，如何顺利通过？一般来说,用计算机进行问题求解时,大致需要经过下列几个步骤:首先要分析问题，从具体问题抽象出一个适当的计算模型,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用语言加以描述。然后设计方案，将问题按照求解过程分解为若干相对独立的功能，每个功能完成一个特定的任务。然后再分别进行算法设计解决每个计算模型。最后编写程序、进行调试、调整。直至得到最终解决。计算机解决问题：模拟胡同里会车抽象建立计算模型：用变量x表示路右侧的这个位置（红车原先位置）变量y表示路左侧的这个位置（蓝车原先位置）用数值1表示红车，用数值2表示蓝车x1表示路右侧位置停着红车y2表示路左则位置停着蓝车交换车辆的位置结果就是：使x的值变为2（右侧位置停着蓝车）而y的值变为1（左则位置停着红车）计算机解决问题：模拟胡同里会车设计算法：1）设置初始状态：x1,y2。打印初始状态x，y2）用变量k表示中间的空位置，把x位置里的红车挪入中间空位置k里：kx3）把y位置里的蓝车挪入x位置里：xy4）把中间空位置k里的红车挪入y位置里：yk5）打印交换后状态x，y32计算机解决问题：模拟胡同里会车1编程实现：x=1y=2print(x,y)k=xx=yy=kprint(x,y)运行结果：1，22，1计算机解决问题：模拟胡同里会车分析问题问题计算模型求解算法计算机程序数据结构问题的解设计算法程序运行设计数据用计算机解决问题的过程抽象自动化计算思维计算1+2+3+4+……+100的和问题2：求和问题计算12+22+32+42+……+1002的和计算1+𝟏𝟐+𝟏𝟑+𝟏𝟒+……+𝟏𝟏𝟎𝟎的和计算1+2+3+4+……+100的和问题2：求和问题问题分析：计算1+2+3+4+……+100的和问题2：求和问题问题分析：按照顺序依次完成求和操作，拿一个空盒子，第一次把1放进去相加，第二次把2放进去相加，第三次把3放进去相加，……，第一百次把100放进去相加，最终得到所有数相加的和。建立计算模型：用变量s表示盒子里的和，最初盒子里为空（s0）用变量x依次表示变化的数，第一次x1,第二次x2,第三次x3,直到第一百次x100。每次都做加法操作s+x，并把新的结果还放在盒子里ss+x计算1+2+3+4+……+100的和问题2：求和问题建立计算模型：用变量s表示盒子里的和，最初盒子里为空（s0）用变量x依次表示变化的数，第一次x1,第二次x2,第三次x3,直到第一百次x100。每次都做加法操作s+x，并把新的结果还放在盒子里ss+x算法设计：设置初始状态：s0设置依次变化的变量x的取值范围，[1,100]，每次递增1设置重复操作的任务：ss+x打印最终的和s问题2：求和问题程序实现：s=0forxinrange(1,101):s=s+xprint（s）运行结果：5050计算1+2+3+4+……+100的和算法设计：设置初始状态：s0设置依次变化的变量x的取值范围，[1,100]，每次递增1设置重复操作的任务：ss+x打印最终的和s试一试：计算12+22+32+42+……+1002的和计算1+𝟏𝟐+𝟏𝟑+𝟏𝟒+……+𝟏𝟏𝟎𝟎的和试一试：求和问题算法设计：设置初始状态：s0设置依次变化的变量x的取值范围，[1,100]，每次递增1设置重复操作的任务：ss+x2打印最终的和s程序实现：s=0forxinrange(1,101):s=s+x**2print（s）运行结果：338350计算12+22+32+42+……+1002的和试一试：求和问题算法设计：设置初始状态：s0设置依次变化的变量x的取值范围，[1,100]，每次递增1设置重复操作的任务：ss+𝟏x打印最终的和s程序实现：s=0forxinrange(1,101):s=s+1/xprint（s）运行结果：5.187377517639621计算1+𝟏𝟐+𝟏𝟑+𝟏𝟒+……+𝟏𝟏𝟎𝟎的和试一试：求和问题运行结果：2.937774848474907计算1+𝟏𝟑+𝟏𝟓+𝟏𝟕+……+𝟏𝟗𝟗的和算法设计：设置初始状态：s0设置依次变化的变量x的取值范围，[1,99]，每次递增2设置重复操作的任务：ss+𝟏x打印最终的和s程序实现：s=0forxinrange(1,100,2):s=s+1/xprint（s）警察局抓了甲、乙、丙、丁四名偷窃嫌疑犯，其中只有一人是小偷，审问记录如下：甲说：“我不是小偷。”乙说：“丙是小偷。”丙说：“小偷肯定是丁。”丁说：“丙在冤枉人。”已知：四个人中三人说的是真话，一人说的是假话问：到底谁是小偷？问题3：警察抓小偷警察局抓了甲、乙、丙、丁四名偷窃嫌疑犯，其中只有一人是小偷，审问记录如下：甲说：“我不是小偷。”乙说：“丙是小偷。”丙说：“小偷肯定是丁。”丁说：“丙在冤枉人。”已知：四个人中三人说的是真话，一人说的是假话问：到底谁是小偷？问题3：警察抓小偷问题分析：依次假设每个人是小偷的情况，然后一一代入那4句话，依次检验已知条件“四个人中三人说的是真话，一人说的是假话”是否成立，如果成立，那么对应的假设成立，小偷找到。问题分析：依次假设每个人是小偷的情况，然后一一代入那4句话，依次检验已知条件“四个人中三人说的是真话，一人说的是假话”是否成立，如果成立，那么对应的假设成立，小偷找到。问题3：警察抓小偷建立计算模型：将甲、乙、丙、丁四个人进行编号为1，2，3，4用变量x存放小偷的编号，若x1表示甲是小偷，若x2表示乙是小偷，若x3表示丙是小偷，若x4表示丁是小偷x从1到4依次去检验“四个人中三人说的是真话，一人说的是假话”是否成立，若成立则x当时存放的编号就是小偷的编号。问题3：警察抓小偷甲说：“我不是小偷。”乙说：“丙是小偷。”丙说：“小偷肯定是丁。”丁说：“丙在冤枉人。”建立计算模型：将甲、乙、丙、丁四个人进行编号为1，2，3，4用变量x存放小偷的编号，若x1表示甲是小偷，若x2表示乙是小偷，若x3表示丙是小偷，若x4表示丁是小偷x从1到4依次去检验“四个人中三人说的是真话，一人说的是假话”是否成立，若成立则x当时存放的编号就是小偷的编号。问题3：警察抓小偷甲说：“我不是小偷。”乙说：“丙是小偷。”丙说：“小偷肯定是丁。”丁说：“丙在冤枉人。”建立计算模型：将甲、乙、丙、丁四个人进行编号为1，2，3，4用变量x存放小偷的编号，若x1表示甲是小偷，若x2表示乙是小偷，若x3表示丙是小偷，若x4表示丁是小偷x从1到4依次去检验“四个人中三人说的是真话，一人说的是假话”是否成立，若成立则x当时存放的编号就是小偷的编号。甲说：x不等于1乙说：x等于3丙说：x等于4丁说：x不等于4问题3：警察抓小偷甲说：“我不是小偷。”乙说：“丙是小偷。”丙说：“小偷肯定是丁。”丁说：“丙在冤枉人。”四个人中三人说的是真话，一人说的是假话(真为1，假为0）建立计算模型：将甲、乙、丙、丁四个人进行编号为1，2，3，4用变量x存放小偷的编号，若x1表示甲是小偷，若x2表示乙是小偷，若x3表示丙是小偷，若x4表示丁是小偷x从1到4依次去检验“四个人中三人说的是真话，一人说的是假话”是否成立，若成立则x当时存放的编号就是小偷的编号。甲说：x不等于1乙说：x等于3丙说：x等于4丁说：x不等于4问题3：警察抓小偷甲说：“我不是小偷。”乙说：“丙是小偷。”丙说：“小偷肯定是丁。”丁说：“丙在冤枉人。”四个人中三人说的是真话，一人说的是假话(真为1，假为0）四个逻辑式的值相加1+1+1+0=3建立计算模型：将甲、乙、丙、丁四个人进行编号为1，2，3，4用变量x存放小偷的编号，若x1表示甲是小偷，若x2表示乙是小偷，若x3表示丙是小偷，若x4表示丁是小偷x从1到4依次去检验“四个人中三人说的是真话，一人说的是假话”是否成立，若成立则x当时存放的编号就是小偷的编号。甲说：x不等于1乙说：x等于3丙说：x等于4丁说：x不等于4问题3：警察抓小偷甲说：x不等于1乙说：x等于3丙说：x等于4丁说：x不等于4x!=1x==3x==4x!=4算法设计：x从1到4依次去检验“四个人中三人说的是真话，一人说的是假话”是否成立，若成立则x当时存放的编号就是小偷的编号。问题3：警察抓小偷甲说：x不等于1乙说：x等于3丙说：x等于4丁说：x不等于4四个人中三人说的是真话，一人说的是假话(真为1，假为0）四个逻辑式的值相加(x!=1)+(x==3)+（x==4)+(x!=4)==3x!=1x==3x==4x!=4算法设计：x从1到4依次去检验“四个人中三人说的是真话，一人说的是假话”是否成立，若成立则x当时存放的编号就是小偷的编号。问题3：警察抓小偷甲说：x不等于1乙说：x等于3丙说：x等于4丁说：x不等于4四个人中三人说的是真话，一人说的是假话(真为1，假为0）四个逻辑式的值相加(x!=1)+(x==3)+（x==4)+(x!=4)==3程序实现：x=1if(x!=1)+(x==3)+（x==4)+(x!=4)==3:print(x,“是小偷”)x!=1x==3x