題目

一個袋子里有30個銀幣，其中一枚是假幣，并且假幣和真幣一模一樣，肉眼很難分辨，目前只知道假幣比真幣重量輕一點。
請問，如何區分出假幣？

分析

首先，分析一下尋找假幣問題，采用遞歸分治的思想求解。

首先為每個銀幣編號，然后將所有的銀幣等分為兩份，放在天平的兩邊。這樣就將區分30個銀幣的問題變為區別兩堆銀幣的問題。

因為假幣分量較輕，因此天平較輕的一側中一定包含假幣。

再將較輕的一側中銀幣等分為兩份，重復上述做法。

直到剩下兩枚銀幣，便可用天平直接找出假銀幣。

分治算法思想

分治算法的基本思想是將一個計算復雜的問題分為若干個規模較小、計算簡單的小問題來進行求解，然后綜合各個小問題，得到最終問題的答案。

執行過程如下：

對于一個規模為N的問題，若該問題可以容易的解決（比如說規模N較小），則直接解決，否則執行下面的步驟；

將該問題分解為M個規模較小的子問題，這些子問題應該互相獨立，并且與原問題形式相同；

遞歸求解各個子問題；

然后將各個子問題的解合并得到原問題的解；

使用分治算法要求待求解的問題能夠化簡為若干個小規模的相同問題，通過逐步劃分，達到一個易于求解的階段而直接進行求解。然后再程序中使用遞歸算法進行求解。

代碼

#include <iostream> #include <cstdlib>using namespace std;const int MAXNUM = 30;int falseCoin(int weight[], int lhs, int rhs) {if (lhs == rhs)return lhs + 1;//如果只剩下兩個銀幣，則較輕的那個便是假幣else if (lhs == (rhs - 1)){return weight[lhs] < weight[rhs] ? lhs + 1 : rhs + 1;}int lsum = 0, rsum = 0;//如果偶數個銀幣，則比較兩等份if ((rhs - lhs + 1) % 2 == 0){for (int i = lhs; i < (lhs + (rhs - lhs + 1) / 2); i++){lsum += weight[i];}for (int j = lhs + (rhs - lhs + 1) / 2; j <= rhs; j++){rsum += weight[j];}//左右兩份等重，則無假幣if (lsum == rsum)return -1;elsereturn (lsum < rsum) ? falseCoin(weight, lhs, lhs + (rhs - lhs) / 2) : falseCoin(weight, lhs + (rhs - lhs) / 2 + 1, rhs);}//如果奇數個銀幣，則比較除中間銀幣外的兩等份else if ((rhs - lhs + 1) % 2 != 0){for (int i = lhs; i < (lhs + (rhs - lhs) / 2); i++){lsum += weight[i];}for (int j = (lhs + (rhs - lhs) / 2 + 1); j <= rhs; j++){rsum += weight[j];}//左右兩份等重，則無假幣if (lsum == rsum && weight[lhs] == weight[lhs + (rhs - lhs) / 2])return -1;//如果兩份等重，中間銀幣較輕，則中間銀幣為假幣else if (lsum == rsum && weight[lhs] > weight[lhs + (rhs - lhs) / 2])return lhs + (rhs - lhs) / 2 + 1;//否則，返回較輕那份中的假幣elsereturn (lsum < rsum) ? falseCoin(weight, lhs, lhs + (rhs - lhs) / 2 - 1) : falseCoin(weight, lhs + (rhs - lhs) / 2 + 1, rhs);} }int main() {int weight[MAXNUM];int n;while (cin >> n){for (int i = 0; i < n; i++)cin >> weight[i];int falsePos = falseCoin(weight, 0, n - 1);if (falsePos != -1)cout << "第" << falsePos << "個銀幣為假幣！" << endl;elsecout << "無假幣!" << endl;}//whilesystem("pause");return 0; }

GitHub代碼下載

總結

以上是生活随笔為你收集整理的3_寻找假币问题（分治法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。