資源簡介

(共13張PPT)
第4單元　計算與問題解決
4.3非數值計算
必修1　數據與計算
目
錄
1
知識梳理
2
知識拓展
3
鞏固練習
1.分治策略
分治的設計思想,是將一個難以直接解決的大問題,分割成一些較小的同類問題,各個擊破,最終達到解決問題的目的。二分查找實際上就是分治策略的一種典型運用。
2.二分查找
二分查找又叫折半查找,該方法主要將數列有序排列,采用跳躍式的方式查找數據。它是一種高效的查找方法,可以明顯減少比較次數,提高查找效率。在一個有n個元素的有序序列中,利用二分查找大約需要lo次。二分法查找的前提條件是被查找的數據必須是有序的。
查找的基本算法有：順序查找、二分查找、分塊查找和哈希查找等。
3.遞歸
直接或間接地調用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復的事物。
在數學與計算機領域中,遞歸函數是指用函數自身來定義該函數的方法。如著名的斐波那契數列“1,1,2,3,5,8,13,…”,可以遞歸定義為：
F（n）＝
遞推關系是遞歸的重要組成,而邊界條件是遞歸的另一要素,它保證遞歸能在有限次的計算后得出結果,而不會產生無限循環的情況。
遞歸的基本思想是把規模較大的問題層層轉化為規模較小的同類問題求解。對遞歸而言,遞推與回歸兩者缺一不可。結合分治策略,遞歸也可用“分”“治”“合”三個字概括。
（1）分：將原問題分解成k個子問題。
（2）治：對這k個子問題分別求解。如果子問題的規模仍然不夠小,則將其再分解為k個子問題,如此進行下去,直到問題足夠小時,就很容易求出子問題的解。
（3）合：將求出的小規模問題的解合并為一個更大規模問題的解,自下而上逐步求出原問題的解。
·迭代與遞歸的關系
迭代算法與遞歸算法都需要重復執行某些代碼,兩者既有區別又有著密切的聯系。
迭代是重復反饋過程的活動,其目的通常是逼近所需目標或結果。遞歸是重復調用函數自身。
遞歸中,遇到滿足終止條件的情況時逐層返回；迭代則通常使用計數器結束循環。
迭代程序可以轉換成等價的遞歸程序。
1.“大事化小、小事化了”體現出的問題求解的思想是（　C　）。
A.遞推法 B.窮舉法 C.分治法 D.歸納法
2.二分查找算法利用的算法思想是（　A　）。
A.分治策略 B.窮舉法
C.貪心法 D.回溯法
3.對線性表進行二分查找時,要求線性表必須（　B　）。
A.以順序方式存儲 B.以順序方式存儲,且數據元素有序
C.以鏈接方式存儲. D.以鏈接方式存儲,且數據元素有序
C
A
B
4.對于數列3,8,11,15,17,19,25,30,44,采用“二分查找”法查找“8”時,需要查找多少次？ （　A　）。
A.3 B.4 C.5 D.6
5.下面關于遞歸說法中正確的是（　B　）。
A.函數間接調用自己不是遞歸
B.遞歸出口和遞歸關系是遞歸函數編寫的關鍵
C.遞歸函數的嵌套調用次數沒有限制
D.遞歸函數的執行效率優于非遞歸函數
A
B

展開更多......

收起↑