資源簡介

(共19張PPT)
第3課 算法的優化
信息技術青島出版社初中第三冊
同樣的馬，為什么結果不一樣了？
田忌
齊威王
上
中
下
上
中
下
學習目標：
理解算法優化的意義
學會用不同的算法來解決問題，并能對算法進行優化
學會多視角分析問題，能利用高效的方法解決問題，養成細致縝密思考問題的習慣
活動一 生活中算法的優化
華 羅 庚
你能為“燒水泡茶”提供幾種解決方案？
你認為哪種方案是最快捷的？
洗水壺1分鐘
燒開水15分鐘
洗茶壺1分鐘
洗茶杯2分鐘
拿茶葉1分鐘
泡茶1分鐘
洗水壺1分鐘
拿茶葉1分鐘
洗茶杯2分鐘
洗茶壺1分鐘
燒開水15分鐘
泡茶1分鐘
思考：
探討對統籌方法的認識和應用。
嘗試列舉生活中應用統籌方法的實例。
李明從早上起床到上學前這段時間要做以下幾件事：
疊被（2分鐘）、洗臉（3分鐘）、刷牙（2分鐘）、
刷鍋（1分鐘）、煮雞蛋（10分鐘）、吃早點（10分鐘）
學以致用
聰明的你能為李明同學設計一套最節約時間的方案嗎？
一位商人有9枚銀幣，其中有一枚略輕，是假銀幣，你能用天平（不用法碼）將假銀幣找出來嗎？
請給出最優化的算法。
如何找出假銀幣
螞蟻的視圖較差，但卻能在黑暗的世界中快速找到食物，而且可以找到從洞穴到食物的最短路徑。螞蟻是如何做到的呢？
神奇的螞蟻
活動二 排序的算法優化
排序的關鍵是比較。我們生活中常見的比較有大小、多少、輕重等。這些比較都是基于數字的比較。數字的排序是計算機科學中算法研究的一個重點。
【想一想】
將12、-3、4、+8、-5按由小到大的順序排列出來， 人工是如何排序的呢？請用自然語言說一說排序的算法過程。
4
8
-5
原始數據
第一輪
12
-3
第一輪結束
第二輪
12
-3
4
8
-5
12
-3
4
8
-5
-3
4
第二輪結束
冒泡排序法
試一試
請你模擬計算機使用冒泡排序法對數據“11、-2、4、+9、-6”進行排序，寫出每輪排序的結果
第一輪：-2、4、9、-6、11
第二輪：-2、4、-6、9、11
第三輪：-2、-6、4、9、11
第四輪：-6、-2、4、9、11
【快速排序法】
圖書管理員的一項重要工作是把學生還回來的書(如100本)按編號順序放人書架。如果你是管理員，應如何快速將這些書放回書架呢
2.經過算法優化的方法(快速排序法)
先從這堆書里隨便挑出一本，把比它編號小的（ ） ，比它編號大的放右邊。分成兩堆后，再（ ）步驟，直到所有的書都按序號排好。
再把從小到大排序后的書按照書架順序歸類，每個書架跑一次，這樣并不需要跑很多次就完成了。
1.傳統方法
一本一本按照編號還回到對應書架。要放回100本書，需要跑（ ）次。
【思考】
經過排放圖書，你能總結快速排序的思想么？
100
放左邊
重復
練一練
請你模擬計算機使用快速排序法對數據“11、-2、4、+9、-6”進行排序，寫出每輪排序的結果
第一輪：-2、4、9、-6、11
第二輪：-6、-2、4、9、11
以11為基準值，比11小的放在左邊
以-2為基準值，比-2小的放在左邊，大的放右邊
活動三 查找的算法優化
【查找的算法優化】
中央電視臺曾經有一檔節目，要求選手在限定時間內猜中某一物品的售價。如果猜中，就把物品獎勵給選手。例如:猜一種手機的價格，手機價格在500--1000之間。選手開始報價:"1000元。”主持人回答:“高了。”
—800元。
—低了。
—880元
—高了。
—850元。
—猜中了。
【思考】
猜價格具有一定的技巧性，你知道這種技巧么？
二分查找是先找有序數列的中點，利用中點將范圍分為兩部分，再經比較不斷找中點并一步一步逼近目標，最后按要求確定一個較小范圍。
【想一想】
從某水庫閘房到防洪指揮部的電話線路發生了故障。這是一條10千米長的線路，如何迅速查出故障所在 如果沿著線路一小段一小段查找，困難很多。搶修工人每查一個點就要爬一次電線桿。想一想:搶修工人怎樣工作最合理
實踐創新
1.某市的出租車計價規則為:在不考慮延時等待的情況下，起步價為11元，可以行駛3千米;接下來的7千米，每千米為2元;如果超過10千米，則剩余的路程每千米3元。不到1千米的按1千米計算。若路程為26千米，如何乘車才會使費用最少
2.一份20頁的試卷，打印了2份，打印出來的頁碼排序為:"1,、1、 2、2、3、3、4、4……20, 20"。傳統的分開方法為左一張反扣，右一張反扣，以此類推，需要翻動40次才能完全將兩份試卷分開。你能否提供一種更高效的方法來減少翻動次數
小結
生活中算法的優化
排序的算法優化
查找的算法優化

展開更多......

收起↑