給出了八個硬幣，只知道其中七個都是真的，另外一個是假的，假的那個比真的總或者比真的輕，請找出哪個是假的。
此處用決策樹來解決，決策樹算法一般用在一些數據分類問題方面，該問題其實并不是非常適合，僅作為使用演示。決策樹是一種依托于策略選擇而建立的樹，可以是二叉樹也可以是多叉樹。決策樹有兩大優點：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;
}
~~~
運行結果如下：
