資源簡介

(共23張PPT)
算法的多樣性
浙教版六年級上冊
第8課 算法的多樣性
學習內容
1. 同一問題存在多種算法。
2. 同一問題的多種算法驗證。
討論
現實中，解決一個問題的算法是不是唯一的？你能舉例來說明嗎？
建構
現實中，解決一個問題的算法往往具有多樣性，即可用多種不同的算法來解決同一個問題。
一、問題描述
利用計算機可以來實現一些小游戲。如猜數字游戲，計算機預先在1~100 范圍內設定一個目標數 mb，同學 A 輸入數字去猜該目標數。計算機根據同學 A 的輸入數字給出“大了”“小了”或“對了”的提示，直到同學 A的輸入數字等于目標數，游戲結束。
二、問題分析
這個猜數字游戲是一個“查找”問題，即在 1~100 范圍內查找數 mb。針對該問題，可采用多種不同的策略來解決，例如：
策略一：順序查找
依次將 1、2、3、…、99、100 （或 100、99、98、…、2、1）與 mb 比較，直到找到為止。
二、問題分析
策略二：二分查找
先取 1~100 的中間數 50 與 mb 比較，若 mb 等于 50，則查找成功；若 mb 小于 50，則取 1~49 的中間數 25 與 mb 比較；若 mb 大于 50，則取 51~100 的中間數 75 與 mb 比較……如此反復，直到找到為止。例如，在
1~100 范圍內查找目標數 37 的過程如下所示：
二、問題分析
小知識
計算機根據所給條件查找出滿足條件的對象，即在存儲的一批數據內尋找出一個特定的數據，或者確定在該批數據內是否存在這樣的數據。
試一試
若采用“順序查找”的策略，在1~100范圍內查找數37，則一共需比較多少次？
三、問題的多種算法設計
要解決這個問題，可分別采用上述策略，將取到的數分別和目標數進行比較，直到找到為止。假設目標數為 37，并用變量 mb 表示，取到的數用變量 qs 表示。
算法一：順序查找。若變量 qs 的取值依次為 1、2、3、…、99、100，該過程可采用循環結構來實現。每取一個值都與目標數 mb 比較，若相等，則輸出找到的信息，否則變量 qs 取下一個值，該過程可采用分支結構來實現。
三、問題的多種算法設計
對應的算法流程圖，如圖所示：
三、問題的多種算法設計
算法二：二分查找。
用變量 cz 和 zz 表示可取數的范圍，初始范圍為1~100，則 cz 的初始值為 1，zz 的初始值為 100。變量 qs 的值依次為變量 cz 和zz 所指范圍的中間值，直到變量 cz 的值超過 zz 的值，該過程可采用循環結構來實現。每取一個值都與目標數 mb 比較，若相等，則輸出找到的信息，否則改變變量 cz 或 zz 的值，調整變量 cz 和zz 所指范圍，該過程可采用分支結構來實現。
三、問題的多種算法設計
對應的算法流程圖，如圖所示：
四、問題的多種算法驗證
根據上述兩種算法，可以通過編寫程序或流程圖的執行進行驗證。算法一的程序驗證：
想一想
上述程序中，若變量的值為137，則程序運行結果是什么？若要顯示對應提示，則應如何修改程序？
四、問題的多種算法驗證
算法二的流程圖驗證：
根據上述算法二的流程圖，可通過表格的形式列出變量 cz、zz 和 qs 的值來驗證該算法。
通過 3 次循環，找到數 37。
試一試
若變量 mb 的值為 137，請用表格的形式列出變量 cz、zz 和 qs 的值。
練一練
在上述算法一中，若變量 qs 的取值依次為 100、99、…、2、1，則相應算法和程序如何修改？
謝謝聆聽！
INTERNET OF THINGS
謝謝
21世紀教育網（www.21cnjy.com)
中小學教育資源網站
兼職招聘：
https://www.21cnjy.com/recruitment/home/admin

展開更多......

收起↑