假幣問題：在n枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣較輕。通過一架來任意比較兩組硬幣，從而得知兩組硬幣的重量是否相同，或者哪一組更輕一些，假幣問題要求設計一個高效的算法來檢測出這枚假幣。請編碼實現。

思路：將這n個硬幣分成2等份，放到天平的兩端，假幣在較輕的那一端；然后將較輕的那一端的硬幣再分成2等份，再放到天平的兩端進行比較，假幣還是在較輕的那一段；直到最后只剩下兩個硬幣了，分別放到天平的兩端，輕的哪一個就是假幣。當然，最后也可能剩下3個硬幣，我們可以將這3個硬幣中任意拿出來一個，然后將剩下的兩個放到天平的兩端，如果天平是平的，則說明拿出來的那個硬幣就是假幣；如果天平不是平的，則輕的那一端是假幣。

Divide the n coins into two equal parts and put them at the two ends of the balance, and the counterfeit coins will be at the lighter end; then the coins at the lighter end will be divided into two equal parts, and then put them at the two ends of the balance for comparison, and the counterfeit coins are still in the lighter part; until there are only two coins left, put them at the two ends of the balance respectively, which one is the lighter is the counterfeit. Of course, there may be three coins left in the end. We can take one of these three coins and put the remaining two on both ends of the balance. If the balance is flat, it means that the coin is counterfeit; if the balance is not flat, the lighter end is counterfeit.

#include <iostream> #include<stdlib.h> #include <ctime> using namespace std;#define MAX 101 //MAX是硬幣的個數(n)void produceCoins(int coins[], int n)//n 是硬幣個數 {int i;srand((unsigned int)time(NULL));int a = rand() % 10 + 1;//在1~11之間隨機產生真幣的重量//先把所有硬幣的重量都賦值為真幣的質量for(i = 0; i < n; i++){coins[i] = a;}int b;//假幣的重量do{b = rand() % 10 + 1;//在1~21之間隨機產生假幣的重量}while(b >= a);//假幣的重量比真幣的重量輕 int c = rand() % n;//隨機產生假幣的坐標coins[c] = b;//把假幣添加進去 }//求coins數組下標從from到to的所有硬幣的重量的和 int sum_coins(int coins[], int from, int to) {int i, sum = 0;for(i = from; i <= to; i++){sum+=coins[i];}return sum; }// 通過比較找出假幣 int find(int a[],int begin,int end) {int k;int mid = (begin + end) / 2;if(end-begin==1&&a[begin]>a[end]) //遞歸出口，end-begin代表只剩兩個數（針對個數為偶數）{k=end;}if(end-begin==1&&a[begin]<a[end]) //遞歸出口，end-begin代表只剩兩個數（針對個數為偶數）{k=begin;}if(begin-end==0)//遞歸出口，end-begin代表只剩一個數 (針對個數為奇數){k=begin;}if((begin+end)%2==1)//傳入個數為偶數{if(sum_coins(a,begin,mid)<sum_coins(a,mid+1,end)) //(前面半組比后面半組輕){k=find(a, begin, mid );}if(sum_coins(a,mid+1,end)<sum_coins(a,begin,mid))//前邊半組比后面半組重{k=find(a, mid+1, end);}}if((begin+end)%2==0&&sum_coins(a,begin,mid-1)==sum_coins(a,mid+1,end))//針對數組元素為寄個數時，兩邊數組相同則中間即為我們要找的假幣{return mid;}if((begin+end)%2==0)//針對數組個數為奇數{if(sum_coins(a,begin,mid-1)<sum_coins(a,mid+1,end))//前面比后面輕，遞歸前面{k=find(a, begin, mid - 1);}if(sum_coins(a,begin,mid-1)>sum_coins(a,mid+1,end))//前面比后面重，遞歸后面{k=find(a, mid + 1, end);}}return k; }//測試 int main(){int coins[MAX],n,m;cout<<"輸入硬幣個數"<<endl;cin>>n;produceCoins(coins,n);for(int i=0;i<n;i++){cout<<coins[i]<<" ";}cout<<endl;m=find(coins,0,n-1);cout<<"假幣為第"<<m+1<<"個";return 0; }

總結

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

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