八硬币问题

给出了八个硬币，只知道其中七个都是真的，另外一个是假的，假的那个比真的总或者比真的轻，请找出哪个是假的。

此处用决策树来解决，决策树算法一般用在一些数据分类问题方面，该问题其实并不是非常适合，仅作为使用演示。决策树是一种依托于策略选择而建立的树，可以是二叉树也可以是多叉树。决策树有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

为所有的硬币赋相同的值，随机选择一个来赋予不同的值，是为假硬币。通过决策树来选择那个假的硬币，详见代码：

//八枚银币比较问题，决策树，根据每次比较结果的不同而采用不同的决策
#include <iostream>
#include <time.h>
using namespace std;

void CoinCmp(int *coins, int smallOne, int bigOne, int RightOne)
{
	if (coins[smallOne] < coins[RightOne])
	{
		cout<<"银币"<<smallOne+1<<"为假银币，重量较轻"<<endl;
	}
	else
		cout<<"银币"<<bigOne+1<<"为假银币，重量较重"<<endl;

}

void EightCoid(int *CoinWeight)
{
	if (CoinWeight[0] + CoinWeight[1] + CoinWeight[2] == CoinWeight[3] + CoinWeight[4] + CoinWeight[5] )
	{
		if (CoinWeight[6] > CoinWeight[7])
		{
			CoinCmp(CoinWeight, 7, 6, 0);
		}
		else
			CoinCmp(CoinWeight, 6, 7, 0);

	}
	else if (CoinWeight[0] + CoinWeight[1] + CoinWeight[2] > CoinWeight[3] + CoinWeight[4] + CoinWeight[5])
	{
		if ( CoinWeight[0] + CoinWeight[3] > CoinWeight[1] + CoinWeight[4])
		{
			
				CoinCmp(CoinWeight, 4, 0, 2);
			
		}
		else if (CoinWeight[0] + CoinWeight[3] <  CoinWeight[1] + CoinWeight[4])
		{
			CoinCmp(CoinWeight, 3, 1, 2);
		}
		else
			CoinCmp(CoinWeight, 5, 2, 0);
	}
	
	else if (CoinWeight[0] + CoinWeight[1] + CoinWeight[2] < CoinWeight[3] + CoinWeight[4] + CoinWeight[5])
	{
		if ( CoinWeight[0] + CoinWeight[3] < CoinWeight[1] + CoinWeight[4])
		{

			CoinCmp(CoinWeight, 0, 4,  2);

		}
		else if (CoinWeight[0] + CoinWeight[3] > CoinWeight[1] + CoinWeight[4])
		{
			CoinCmp(CoinWeight,  1,3, 2);
		}
		else
			CoinCmp(CoinWeight,  2, 5, 0);
	}

}

int main()
{
	int nCoinWeight[8];
	for (int i = 0; i< 8; i++)
	{
		nCoinWeight[i] = 20;
	}

	srand(time(NULL));
	nCoinWeight[rand()%8] = rand()%40;

	for (int i = 0; i< 8; i++)
	{
		cout<<i+1<<": "<<nCoinWeight[i]<<endl; 
	}
	EightCoid(nCoinWeight);
	system("pause");
	return 1;

}

运行结果如下：