好久以前学算法时看的一个题、、、

说明： 现有八枚银币a b c d e f g h，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。

解法单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树（decision tree），使用分析与树状图来协助求解。一个简单的状况是这样的，我们比较a+b+c与d+e+f ，如果相等，则假币必是g或h，我们先比较g或h哪个较重，如果g较重，再与a比较（a是真币），如果g等于a，则g为真币，则h为假币，由于h比g轻而 g是真币，则h假币的重量比真币轻。

简单测试

VS2013

#define _CRT_SECURE_NO_WARNINGS#include#include#include "conio.h"#includeint count = 0;

void compare(int[], int, int, int);

void eightcoins(int[]);

int main(void)

{

int coins[8] = { 0 };

int i,w;

printf("\n输入假币重量(比10大或小)： "); scanf("%d", &w);

do

{

for (i = 0; i < 8; i++)

coins[i] = 10;

srand(time(NULL));

coins[rand() % 8] = w; // 产生随机数 1~7 【1,7】 中有一为假 coins[0] 为真 eightcoins(coins);

printf("\n列出所有钱币重量：\n\n"); printf("标号：");

for (i = 1; i <= 8; i++)

printf("%3d ", i);

printf("\n重量：");

for (i = 0; i < 8; i++)

printf("%3d ", coins[i]);

printf("\n\n");

printf("\n输入假币重量(比10大或小,输入0结束)： ");

scanf("%d", &w);

printf("\n");

}

while (w!=0);

return 0;

}

void compare(int coins[], int i, int j, int k)

// 将其与真 相比

{

if (coins[i] > coins[k])

printf("\n假币 %d 较重\n", i + 1);

else

printf("\n假币 %d 较轻\n", j + 1);

}

void eightcoins(int coins[])

{ if (coins[0] + coins[1] + coins[2] == coins[3] + coins[4] + coins[5])

{ if (coins[6] > coins[7]) compare(coins, 6, 7, 0);

else if (coins[6] < coins[7]) compare(coins, 7, 6, 0);

}

else if (coins[0] + coins[1] + coins[2] > coins[3] + coins[4] + coins[5])

{

if (coins[0] + coins[3] == coins[1] + coins[4]) compare(coins, 2, 5, 0);

else if (coins[0] + coins[3] > coins[1] + coins[4])

compare(coins, 0, 4, 1);

if (coins[0] + coins[3] < coins[1] + coins[4]) compare(coins, 1, 3, 0);

}

else if (coins[0] + coins[1] + coins[2] < coins[3] + coins[4] + coins[5])

{

if (coins[0] + coins[3] == coins[1] + coins[4]) compare(coins, 5, 2, 0);

else if (coins[0] + coins[3] > coins[1] + coins[4])

compare(coins, 3, 1, 0);

if (coins[0] + coins[3] < coins[1] + coins[4]) compare(coins, 4, 0, 1);

}

}