分治法递归求解查找假币问题C++

查找假币问题可以通过分治法递归求解。

假设有n个硬币，其中有且仅有一个假币，重量比真币轻。现在给你一个天平，问最少需要称多少次，才能找出假币。

解题思路：

1.如果有1个硬币，显然不需要称。

2.如果有2个硬币，只需要称一次即可。

3.如果有3个硬币，可以将它们分成两组，分别称一次。如果两组的重量相等，那么假币在第三组中，需要再称一次；否则假币在较轻的那组中，需要再称一次。

4.如果有4个硬币，可以将它们分成两组，分别称一次。如果两组的重量相等，那么假币在另外两个硬币中，需要再称一次；否则假币在较轻的那组中，需要再称一次。

……

可以发现，如果有n个硬币，可以将它们分成三组：每组都有n/3个硬币。然后分别称一次，如果三组的重量相等，那么假币在剩余的n-3n/3=n/3个硬币中，需要再称一次；否则假币在较轻的那组中，需要再称一次。这个过程可以用递归实现。

下面是C++代码实现：

#include<iostream>
using namespace std;

int weigh(int n)
{
    if(n==1) return 0; //只有一个硬币，不需要称
    if(n==2) return 1; //有两个硬币，只需要称一次
    int w=weigh(n/3*2); //先将n个硬币分成三组，每组都有n/3个硬币
    if((n-n/3*3)==1) return w+2; //剩余一个硬币，需要称两次
    else if((n-n/3*3)==2) return w+1; //剩余两个硬币，需要称一次
    else return w+2; //剩余三个硬币，需要称两次
}

int main()
{
    int n;
    cout<<"请输入硬币的个数：";
    cin>>n;
    cout<<"最少需要称的次数为："<<weigh(n)<<endl;
    return 0;
}