文章目錄

• • 1 分治算法
  • • 1.1引入
    • 1.2 分治算法介紹
    • 1.3 應(yīng)用實(shí)例

1 分治算法

1.1引入

一個(gè)裝有 16 枚硬幣的袋子，16 枚硬幣中有一個(gè)是偽造的，偽造的硬幣和普通硬幣從表面上看不出有任何差別，但是那個(gè)偽造的硬幣比真的硬幣要輕。現(xiàn)有給你一臺(tái)天平，請(qǐng)你在盡可能最短的時(shí)間內(nèi)找出那枚偽造的硬幣。

常規(guī)思維：
每次從待比較的硬幣中取兩枚進(jìn)行計(jì)較，如果天平平衡（相等）就繼續(xù)取剩下的硬幣進(jìn)行比較。

繼續(xù)以上過程，直到找到硬幣。

強(qiáng)者思維:
我們先將 16 枚硬幣分為左右兩個(gè)部分，各為 8 個(gè)硬幣，分別稱重，必然會(huì)有一半輕一半重，而我們要的就是輕的那組,重的舍去。接下來我們繼續(xù)對(duì)輕的進(jìn)行五五分，直至每組剩下一枚或者兩枚硬幣，這時(shí)我們的問題自然就解決了，下面用一張圖進(jìn)行更好的理解。

1.2 分治算法介紹

分治法：
見名思義，即分而治之，從而得到我們想要的最終結(jié)果。分治法的思想是將一個(gè)規(guī)模為 N 的問題分解為 k 個(gè)較小的子問題，這些子問題遵循的處理方式就是互相獨(dú)立且與原問題相同。

兩部分組成：
分（divide）：遞歸解決較小的問題
治（conquer）：然后從子問題的解構(gòu)建原問題的解。

三個(gè)步驟：
1、分解（Divide）：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；
2、解決（Conquer）：若子問題規(guī)模較小而容易被解決則直接解決，否則遞歸地解各個(gè)子問題；
3、合并（Combine）：將各個(gè)子問題的解合并為原問題的解。

1.3 應(yīng)用實(shí)例

二分查找算法實(shí)現(xiàn)：

#include <stdio.h> #include <stdlib.h>/*遞歸實(shí)現(xiàn)二分查找 參數(shù):arr - 有序數(shù)組地址 arrminSub - 查找范圍的最小下標(biāo) minSubmaxSub - 查找范圍的最大下標(biāo) maxSubnum - 帶查找數(shù)字返回:找到則返回所在數(shù)組下標(biāo)，找不到則返回-1 */int BinarySearch(int* arr,int minSub,int maxSub,int num){if(minSub>maxSub){return -1;//找不到 num 時(shí),直接返回}int mid=(minSub+maxSub)/2;if(num<arr[mid]){return BinarySearch(arr,minSub,mid-1, num);}else if(num>arr[mid]){return BinarySearch(arr,mid+1,maxSub, num);}else{return mid;//找到 num 時(shí)直接返回} }int main(void){int arr[]={1, 3, 7, 9, 11};int index = BinarySearch(arr, 0, 4, 8);printf("index: %d\n", index);system("pause");return 0; }

---

參考資料：

C/C++從入門到精通-高級(jí)程序員之路【奇牛學(xué)院】

總結(jié)

以上是生活随笔為你收集整理的分治算法介绍的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。