分治算法講解-文庫吧
2025-07-21 03:31 本頁面
【正文】 每個小問題相互獨立專題一：分治算法之二分查找思考題：找假幣： 有一堆個數(shù)為32的硬幣，和一個天平，已知其中有一個假幣，且假幣比真硬幣輕，找出這個假幣1. 普通方法：兩兩比較，輕的那個是假幣，最多比較16次2. 二分法：將硬幣分為兩份，假幣在輕的那份中，然后繼續(xù)分，直到找出假幣，最多用5次 哪種方法好？課題：二分查找（折半查找）知識目標(biāo)：理解二分查找算法的概念以及執(zhí)行過程。 重點：掌握二分查找算法的常規(guī)寫法以及遞歸寫法。1. 邊界錯誤造成的問題 3. 溢出I. 算法介紹： 二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好。其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。II. 思路分析：二分查找的基本思想是：（1）先確定一組順序排列的數(shù)據(jù)存儲到數(shù)組中，輸入要查找的數(shù)據(jù)（2）將數(shù)組元素的中值與查找的數(shù)據(jù)相比較，如果兩者相等，則子函數(shù)返回相應(yīng)的結(jié)果后終止；（3）否則利用中間位置縮小數(shù)據(jù)查找的范圍。如果中間位置的數(shù)組元素大于查找數(shù)值，則進一步查找中值之前的數(shù)組元素，否則進一步查找中值之后的數(shù)組元素。（4）重復(fù)上述過程，直到在數(shù)組中找到相同的數(shù)字。（5）若在數(shù)組中找不到這個數(shù)據(jù)，則顯示查找不成功III. 算法框架： 按照分治算法三步驟，將二分算法作如下介紹：（1） 二分算法代碼設(shè)計模式: //arr[]表示要進行二分查找的順序排列對象數(shù)組，low表示數(shù)組下標(biāo)的最小值，high表示數(shù)組下表的最大值，key表示要查找的元素 int erfen(int arr[],int low,int high,int key){ ?如果數(shù)組下標(biāo)的最小值大于最大值 則返回結(jié)果為1至主函數(shù)；//表明在數(shù)組中不存在要查找的元素 ?確定數(shù)組的中間位置mid ?若查找的元素等于數(shù)組的中間元素，則進行相應(yīng)的步驟 ④ 若查找的元素大于數(shù)組（指定范圍內(nèi)）的中間元素 則將查找范圍縮小至數(shù)組（指定范圍內(nèi)）中間元素右邊； ⑤若查找的元素小于數(shù)組指定范圍內(nèi)的中間元素 則將查找范圍縮小至數(shù)組（指定范圍內(nèi)）中間元素左邊； } 例題1：輸入一個整數(shù)n，然后按升序輸入n個整數(shù)，將它們存入數(shù)組a中，再輸入一個數(shù)x,然后在數(shù)組中查找x,如果找到，輸出相應(yīng)的最小下標(biāo)，否則，輸出“Not Found”. 普通寫法：includeiostreamusing namespace std。int main(){ int i,s[100],n。 cinn。 for(i=0。in。i++) cins[i]。
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1