八硬币问题
最后更新于：2022-04-01 10:11:48
给出了八个硬币，只知道其中七个都是真的，另外一个是假的，假的那个比真的总或者比真的轻，请找出哪个是假的。
此处用决策树来解决，决策树算法一般用在一些数据分类问题方面，该问题其实并不是非常适合，仅作为使用演示。决策树是一种依托于策略选择而建立的树，可以是二叉树也可以是多叉树。决策树有两大优点：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;
}
~~~
运行结果如下：
