计算思维小试题.ppt

单击此处编辑母版标题样式,编辑母版文本样式第二级第三级第四级第五级,*,*,计算思维小试题,2018,01,02,03,04,机器人警察的巡逻路线,抢椅子的小游戏,参加派对的朋友们,机器人油漆工,目 录,CONTENTS,机器人警察的巡逻路线,01,海狸小镇上有一个机器人警察。每天晚上它都在街上巡逻（见左图）。机器人警察只有三种行动：,向前一步，向左转（不向前），向右转（不向前）。,机器人警察巡逻完街道之后需要回到最初开始的地方，请问它至少需要多少次行动？,A.11,B.16,C.12,D.18,机器人警察的巡逻路线,同学们，你们肯定已经知道答案了，对了，就是,D,，,18,次。好的开始是成功的一半，你们真棒,我是这么想的，在图上画出机器人警察的行走路线然后再数一数就可以了，要注意转弯的时候也要数一步。,如果机器人警察从其他位置的格子出发，路线会怎么走？至少需要多少次行动呢？,我发现，无论从哪个格子出发，都会至少行动,18,次。,这题也太简单了，哪里是计算思维的知识呀？,同学们，其实在设计路线的过程中你们已经开始运用计算思维了。,机器人警察只有向前和转弯两个行动，整条街道有,12,个位置和,6,个拐弯处，所以机器人警察至少需要,18,个行动，而且无论从哪个格子出发，都是这一种结论。,在这个活动的过程中，你们运用了算法设计，方案实施，应用迁移等，这就是计算思维啦。,如果用,F,代表前进，,L,代表向左，,R,代表向右，你能写出机器人警察的行走路线吗？,我设计的路线是：,FRFFFRFFRFLFRFFRFF,，你们的想法跟我一样吗？,从另外的点开始出发，这个序列只要适当的旋转，就可以使机器人警察完成一周的巡逻，这就是简单程序的编写。,如果你是机器人的设计者，你会给机器人编写程序了吗？,机器人警察的操作只有三种，因此，这是一个可以计算，可以编程的系统。在计算机科学中，制作可编写的程序系统是非常普遍的，一个程序可能需要很多操作，但在设计时需要给予尽可能少的操作，这也是计算思维。,如果从红点出发，我想路线应该是,RFFFRFFRFLFRFFRFFF,，其实就是把第一个动作顺延到了整个数列最后一个位置。,你们将是未来的程序设计师！,抢椅子的小游戏,02,在每个回合中，大海狸（,A,和,B,）可以往逆时针方向移动,3,把椅子，因为他们更加灵活。中海狸（,C,和,D,）可以往逆时针方向移动,2,把椅子，小海狸（,E,，,G,和,F,）只能向顺时针方向移动,1,把椅子。在同一时间，多只海狸可以占据同一把椅子。请问连续,3,轮过后，哪把椅子没有被占？,抢椅子的小游戏,7,只海狸正在玩抢椅子游戏，游戏规则如下：,A.2,和,7,B.3,和,7,C.1,和,2,D.1,和,3,我要开始移动啦！你知道逆时针是哪个方向吗？,1,这是逆时针方向,2,3,这就是我一轮到达的位置，但我不会马上坐下，我会继续进行第二轮。,1,2,3,这就是我二轮到达的位置，但我仍不会马上坐下，我会继续进行第三轮。,1,2,3,三轮过后，我最后坐在,6,号椅子上，我一共移动了,9,步。,正确答案是：,A.2,和,7,。,你们想的对吗？做对的同学，你是怎么想的呢？,解决该问题的,关键,是牢记每只海狸在每一轮的移动情况是一样的。,我们分析,信息,时要,关注主要的问题，而不要被重复的过程所影响。通过完成这个任务，你可以简化算法，找出模式,，这就是计算思维,。,大海狸向逆时针方向,一共,移动了,9,步。,因此，,A,从椅子,1,移动到了,6,。,B,从,6,移动到了,4,。,中海狸向逆时针方向,一共,移动了,6,步。,C,从椅子,4,移动到了,5,。,D,从,3,移动到了,4,。,小海狸向顺时针方向,一共,移动了,3,步。,E,从椅子,2,移动到了,5,，,F,从椅子,7,移动到了,3,，,G,从椅子,5,移动到了,1,。,所以，,在,3,轮过后，椅子,1,，,3,，,6,被,1,只海狸占据了，椅子,4,和,5,被两只海狸占据了。未被占据的椅子是,2,和,7,。,归纳整理,抢椅子的小游戏,我的想法,参加派对的朋友们,03,Patrick,住在,Beaveral,，他邀请住在周围村落的小伙伴们都来为他庆祝生日。可是只有那些住所在,20,千米以内的朋友来了。下图中标注了村落与村落之间的距离（千米）。,请问来了多少个朋友？,参加派对的朋友们,A.7,B.8,C.9,D.10,0,参加派对的朋友们,同学们这些标注黄色的就是能来参加派对的朋友们，数一数，一共有几位？,对了，答案就是,C.9,从,Beaveral,到各个村落的最短距离可以通过找出连接两个村落的合适路线计算出来，这样使总路线最短。然后只保留那些距,Beaveral,20,千米以内的村落。为保证各村落距离都能得到检测，从近到远的排序应该是自然而然的选择。下面展示了,迪吉杰斯特拉算法,：,Wells=2,Bath=8,Ranby,=12,Rand=13=2+11(Bilby=13+8=21 too far going this way),Saron,=16=8+8(,Penmon,=16+8=24 too far going this way),Mold=17(Weir=17+8=25 too far going this way),Stow=17=12+5,Blyth=18=8+10(Holt=18+3=21 too far going this way),H,olt=19=17+2,A.7,B.8,C.9,D.10,在这个任务中，我们用了一张图绘制出村落的分布和它们之间的距离。这不只是数学运算，因为涉及计算和对比，主要还是关于计算机科学的。它对于类似的，往往更复杂的结构很凑效，如图片中的地图。重要的是不仅要计算路线，还要,考虑,符合题目要求的村落。,该课题测试答题者是否可以在这样的结构中定位并运用存储在其中的数据,。,在像这样的数据结构中检测路径的手法叫做宽度优先搜索。,解读计算思维,计算思维是不是更像,计算机思维,机器人油漆工,04,机器人油漆工,机器人油漆工的任务是给栅栏上的木板涂颜料，而且每个木板涂一种颜色。它有一排装着不同颜料的桶（如下图所示），但不是所有的桶里都装满了颜料。机器人要按照颜料桶排列的顺序循环为木板上色，如果哪个桶的颜料用完了，机器人会把桶移走，直到所有的颜料桶都空了或者机器人要连续使用同一种颜色时，它就会停止工作。,红色颜料能涂,5,块木板,;,绿色颜料能涂,3,块木板,;,黄色颜料能涂,7,块木板,;,蓝色颜料能涂,2,块木板。,请问机器人要涂多少块木板才会停下来,?,A.5,B.8,C.17,D.15,机器人油漆工,红色颜料能涂,5,块木板,;,绿色颜料能涂,3,块木板,;,黄色颜料能涂,7,块木板,;,蓝色颜料能涂,2,块木板。,注意涂色要求,我想亲自涂一涂！,蓝色用完,绿色用完,红色用完,颜色重复,不算颜色重复的两个黄色，是,15,块，选,D,。,机器人油漆工,在思考这道题的时候，我们先考虑每种颜色能涂的块数，因为蓝色能涂的块数最少只有,2,块，按照四个颜色一循环涂完蓝色是,4+4=8,（块）。,绿色只能涂,3,块，因此还有一次三个颜色的循环，,8+3=11,（块），照这样计算，红色剩下,2,块，因此只能和黄色再循环两次，,11+2+2=15,（块）,算法（,Algorithm,）,是指解题方案的准确而完整的描述，是一系列解决问题、完成任务的清晰指令。你必须能够阅读和理解指令，并一步一步地执行它们，看看执行时会产生什么效果。这实际上是程序员需要具备的一项非常重要的技能，叫做,调试,。,这就是,计算思维,谢谢观看,