資源簡介

(共16張PPT)
哪個算法更“好”？
順序查找
二分查找
算法的評價方法
如何比較這兩個查找算法的運行效率
時間長短
↓
語句的執行次數？
↓
用循環語句執行次數估算效率
循環次數 范圍 范圍初值cz 范圍終值zz 猜測編號cai （取中間數） 編號比較 （cai vs da） 輸出結果
（猜低了/猜高了/猜對啦）
1 1~20 1 20 10 10<17 猜低了
2 11~20 11 20 15 15<17 猜低了
3 16~20 16 20 18 18>17 猜高了
4 16~17 16 17 16 16<17 猜低了
5 17~17 17 17 17 17=17 猜對啦
可能影響循環次數的因素有哪些？
如果答案編號da=17：
范圍？
目標值？
二人小組在1-100范圍內繼續數目標值50、100時兩種算法分別執行了多少次。
實驗一：相同查找范圍，不同目標值的探究。
慢
容易錯
1
3→
6→
12→
25→
50→
6
思考：當查找范圍相同時，影響循環次數的因素是什么？
有沒有更快記錄循環次數的方法？
利用變量記錄循環次數！
修改程序，變量計數
變量：ci
ci賦初始值0
每進入循環ci加1
查找結束輸出結果
ci初始化
ci增加1
輸出ci
修改程序，變量計數
ci初始化
ci增加1
輸出ci
放在哪？
①
②
③
④
⑤
⑥
⑦
⑧
修改程序，變量計數
增加計次變量；
二人小組合作對照流程圖，將下方語句寫入程序對應“行”中。
程序記錄次數的探究
順序查找
二分查找
實驗二：相同目標值，不同查找范圍的探究
修改查找范圍、目標值,運行程序驗證
思考：當查找范圍相同時，影響循環次數的因素是什么？
999
999
999
999
9
14
17
20
查找范圍、目標值
更多的實驗數據
哪個算法更“好”？
一直是二分查找“好”嗎？
好的時候好多少？
二分查找好
大概率
效率好且很顯著
在相同查找范圍內，查找不同目標值時，大概率是二分查找效率高且顯著。
“好”算法的標準
正確性、有效性
效率：
你的電腦“卡”過嗎？
占用內存空間
時間
給程序計時！
猜猜這段程序有什么用？
下課~

展開更多......

收起↑