本文主要是介绍国王赏赐金币问题（减治法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
国王赏赐大臣30枚金币，但是有一枚是假的，并且假的金币较轻，国王让大臣仅用一个天平，比较最少的次数得到答案。也就是，在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻，可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些。
解法：
我们可以把假币一分为二，也就是把n枚硬币分为两组，每组有n/2个硬币，如果n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。如果两组硬币的重量相同，那么留下的硬币就是假币；否则用同样的方法对较轻的那组硬币进行同样的处理，因为假币一定在较轻的那组里。
代码如下：
#include<iostream>
using namespace std;
int GetSum(int arr[], int low, int high) {int sum = 0;for (int i = low; i <= high; i++)sum += arr[i];return sum;
}
int SeletCoin(int arr[],int low,int high) {int len = high - low + 1;if (low + 1 == high) {if (arr[low] > arr[high])return high;else {return low;}}int tem1, tem2;if (len % 2 == 0) {tem1 = GetSum(arr, low, low+len / 2-1);tem2 = GetSum(arr, low+len / 2, high);if (tem1 < tem2) {return SeletCoin(arr, low, low + len / 2 - 1);}else {return SeletCoin(arr, low + len / 2, high);}}else {tem1 = GetSum(arr, low, low + len / 2 - 1);tem2 = GetSum(arr, low + len / 2 + 1, high);if (tem1 == tem2)return low + len / 2;else if (tem1 < tem2)return SeletCoin(arr, low, low + len / 2 - 1);else return SeletCoin(arr, low + len / 2 + 1, high);}
}
int main() {int arr[] = { 2,2,2,1,2,2,2,2 };cout << SeletCoin(arr, 0, 7);return 0;}这篇关于国王赏赐金币问题（减治法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
