計(jì)算思維小試題.ppt

1、計(jì)算思維小試題,2018,機(jī)器人警察的巡邏路線,搶椅子的小游戲,參加派對(duì)的朋友們,機(jī)器人油漆工,目 錄,CONTENTS,機(jī)器人警察的巡邏路線,01,海貍小鎮(zhèn)上有一個(gè)機(jī)器人警察。每天晚上它都在街上巡邏（見左圖）。機(jī)器人警察只有三種行動(dòng)： 向前一步，向左轉(zhuǎn)（不向前），向右轉(zhuǎn)（不向前）。 機(jī)器人警察巡邏完街道之后需要回到最初開始的地方，請問它至少需要多少次行動(dòng)？,A.11 B.16 C.12 D.18,機(jī)器人警察的巡邏路線,同學(xué)們，你們肯定已經(jīng)知道答案了，對(duì)了，就是D，18次。好的開始是成功的一半，你們真棒,我是這么想的，在圖上畫出機(jī)器人警察的行走路線然后再數(shù)一數(shù)就可以了，要注意轉(zhuǎn)彎的時(shí)候也要數(shù)一

2、步。,如果機(jī)器人警察從其他位置的格子出發(fā)，路線會(huì)怎么走？至少需要多少次行動(dòng)呢？,我發(fā)現(xiàn)，無論從哪個(gè)格子出發(fā)，都會(huì)至少行動(dòng)18次。,這題也太簡單了，哪里是計(jì)算思維的知識(shí)呀？,同學(xué)們，其實(shí)在設(shè)計(jì)路線的過程中你們已經(jīng)開始運(yùn)用計(jì)算思維了。 機(jī)器人警察只有向前和轉(zhuǎn)彎兩個(gè)行動(dòng)，整條街道有12個(gè)位置和6個(gè)拐彎處，所以機(jī)器人警察至少需要18個(gè)行動(dòng)，而且無論從哪個(gè)格子出發(fā)，都是這一種結(jié)論。 在這個(gè)活動(dòng)的過程中，你們運(yùn)用了算法設(shè)計(jì)，方案實(shí)施，應(yīng)用遷移等，這就是計(jì)算思維啦。,如果用F代表前進(jìn)，L代表向左，R代表向右，你能寫出機(jī)器人警察的行走路線嗎？,我設(shè)計(jì)的路線是：FRFFFRFFRFLFRFFRFF，你們的想法跟

3、我一樣嗎？,從另外的點(diǎn)開始出發(fā)，這個(gè)序列只要適當(dāng)?shù)男D(zhuǎn)，就可以使機(jī)器人警察完成一周的巡邏，這就是簡單程序的編寫。 如果你是機(jī)器人的設(shè)計(jì)者，你會(huì)給機(jī)器人編寫程序了嗎？ 機(jī)器人警察的操作只有三種，因此，這是一個(gè)可以計(jì)算，可以編程的系統(tǒng)。在計(jì)算機(jī)科學(xué)中，制作可編寫的程序系統(tǒng)是非常普遍的，一個(gè)程序可能需要很多操作，但在設(shè)計(jì)時(shí)需要給予盡可能少的操作，這也是計(jì)算思維。,如果從紅點(diǎn)出發(fā)，我想路線應(yīng)該是RFFFRFFRFLFRFFRFFF，其實(shí)就是把第一個(gè)動(dòng)作順延到了整個(gè)數(shù)列最后一個(gè)位置。,你們將是未來的程序設(shè)計(jì)師！,搶椅子的小游戲,02,在每個(gè)回合中，大海貍（A和B）可以往逆時(shí)針方向移動(dòng)3把椅子，因?yàn)樗麄兏?/p>

4、加靈活。中海貍（C和D）可以往逆時(shí)針方向移動(dòng)2把椅子，小海貍（E，G和F）只能向順時(shí)針方向移動(dòng)1把椅子。在同一時(shí)間，多只海貍可以占據(jù)同一把椅子。請問連續(xù)3輪過后，哪把椅子沒有被占？,搶椅子的小游戲,7只海貍正在玩搶椅子游戲，游戲規(guī)則如下：,A. 2 和 7 B. 3 和 7 C. 1 和 2 D. 1 和 3,我要開始移動(dòng)啦！你知道逆時(shí)針是哪個(gè)方向嗎？,1,這是逆時(shí)針方向,2,3,這就是我一輪到達(dá)的位置，但我不會(huì)馬上坐下，我會(huì)繼續(xù)進(jìn)行第二輪。,1,2,3,這就是我二輪到達(dá)的位置，但我仍不會(huì)馬上坐下，我會(huì)繼續(xù)進(jìn)行第三輪。,1,2,3,三輪過后，我最后坐在6號(hào)椅子上，我一共移動(dòng)了9步。,正確答案是

5、：A. 2 和 7。 你們想的對(duì)嗎？做對(duì)的同學(xué)，你是怎么想的呢？,解決該問題的關(guān)鍵是牢記每只海貍在每一輪的移動(dòng)情況是一樣的。我們分析信息時(shí)要關(guān)注主要的問題，而不要被重復(fù)的過程所影響。通過完成這個(gè)任務(wù)，你可以簡化算法，找出模式，這就是計(jì)算思維。,大海貍向逆時(shí)針方向一共移動(dòng)了9步。 因此，A從椅子1移動(dòng)到了6。B從6移動(dòng)到了4。 中海貍向逆時(shí)針方向一共移動(dòng)了6步。 C從椅子4移動(dòng)到了5。D從3移動(dòng)到了4。 小海貍向順時(shí)針方向一共移動(dòng)了3步。 E從椅子2移動(dòng)到了5，F(xiàn)從椅子7移動(dòng)到了3，G從椅子5移動(dòng)到了1。 所以，在3輪過后，椅子1，3，6被1只海貍占據(jù)了，椅子4和5被兩只海貍占據(jù)了。未被占據(jù)的椅

6、子是2和7。,歸納整理,我的想法,參加派對(duì)的朋友們,03,Patrick住在 Beaveral，他邀請住在周圍村落的小伙伴們都來為他慶祝生日?？墒侵挥心切┳∷?0千米以內(nèi)的朋友來了。下圖中標(biāo)注了村落與村落之間的距離（千米）。 請問來了多少個(gè)朋友？,參加派對(duì)的朋友們,A. 7 B. 8 C. 9 D. 10,0,同學(xué)們這些標(biāo)注黃色的就是能來參加派對(duì)的朋友們，數(shù)一數(shù)，一共有幾位？ 對(duì)了，答案就是 C.9,從Beaveral到各個(gè)村落的最短距離可以通過找出連接兩個(gè)村落的合適路線計(jì)算出來，這樣使總路線最短。然后只保留那些距Beaveral 20千米以內(nèi)的村落。為保證各村落距離都能得到檢測，從近到遠(yuǎn)的

7、排序應(yīng)該是自然而然的選擇。下面展示了迪吉杰斯特拉算法：,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)

8、Holt = 19 = 17 + 2,A. 7 B. 8 C. 9 D. 10,在這個(gè)任務(wù)中，我們用了一張圖繪制出村落的分布和它們之間的距離。這不只是數(shù)學(xué)運(yùn)算，因?yàn)樯婕坝?jì)算和對(duì)比，主要還是關(guān)于計(jì)算機(jī)科學(xué)的。它對(duì)于類似的，往往更復(fù)雜的結(jié)構(gòu)很湊效，如圖片中的地圖。重要的是不僅要計(jì)算路線，還要考慮符合題目要求的村落。 該課題測試答題者是否可以在這樣的結(jié)構(gòu)中定位并運(yùn)用存儲(chǔ)在其中的數(shù)據(jù)。在像這樣的數(shù)據(jù)結(jié)構(gòu)中檢測路徑的手法叫做寬度優(yōu)先搜索。,解讀計(jì)算思維,計(jì)算思維是不是更像計(jì)算機(jī)思維,機(jī)器人油漆工,04,機(jī)器人油漆工,機(jī)器人油漆工的任務(wù)是給柵欄上的木板涂顏料，而且每個(gè)木板涂一種顏色。它有一排裝著不同顏料的

9、桶（如下圖所示），但不是所有的桶里都裝滿了顏料。機(jī)器人要按照顏料桶排列的順序循環(huán)為木板上色，如果哪個(gè)桶的顏料用完了，機(jī)器人會(huì)把桶移走，直到所有的顏料桶都空了或者機(jī)器人要連續(xù)使用同一種顏色時(shí)，它就會(huì)停止工作。,紅色顏料能涂 5 塊木板; 綠色顏料能涂 3 塊木板; 黃色顏料能涂 7 塊木板; 藍(lán)色顏料能涂 2 塊木板。,請問機(jī)器人要涂多少塊木板才會(huì)停下來? A. 5 B. 8 C. 17 D. 15,機(jī)器人油漆工,注意涂色要求,藍(lán)色用完,綠色用完,紅色用完,顏色重復(fù),機(jī)器人油漆工,在思考這道題的時(shí)候，我們先考慮每種顏色能涂的塊數(shù)，因?yàn)樗{(lán)色能涂的塊數(shù)最少只有2塊，按照四個(gè)顏色一循環(huán)涂完藍(lán)色是4+4=8（塊）。,綠色只能涂3塊，因此還有一次三個(gè)顏色的循環(huán)，8+3=11（塊），照這樣計(jì)算，紅色剩下2塊，因