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