C-POJ上的算法题寻找假币的问题。

Question

某人有12枚硬币，确定其中有且仅有一枚为假的，且不知较轻或较重，已知条件有
1.假币又且仅有一枚
2.真币刚好11枚
3.每个case保证有且仅有唯一解
4.每个case只称量三次
5.每次称量都保证天平左右两边硬币数量一致
6.硬币编号用大写字母 A-L 表示
7.even表示tiao天平两头平衡
8.down表示天平右侧下沉
9.up表示天平右侧上升
输入：
1.第一行为case总数量
2.接下去每三行代表一个case
3.每个case中的每一行分三部分
4.第一部分表示天平左边
5.第二部分表示天平右边
6.第三部分表示天片右边平衡状态
输出：
1.输出假硬币的编号
2.输出假硬币是轻是重

Answer 1

首先，把12个硬币分成三等份，每份四只。
拿出其中两份放到天平两侧称（第一次）
情况一：天平是平衡的。
那么那八个拿上去称的硬币都是正常的，特殊的在四个里面。
把剩下四个硬币拿出三个放到一边，另一边放三个正常的硬币（第二次）
如天平平衡，特殊的是剩下那个。
如果不平衡，在天平上面的那三个里。而且知道是重了还是轻了。
剩下三个中拿两个来称，因为已经知道重轻，所以就可以知道特殊的了。（第三次）
情况二：天平倾斜。
特殊的硬币在天平的那八个里面。
把重的一侧四个硬币记为A1A2A3A4，轻的记为B1B2B3B4。
剩下的确定为四个正常的记为C。
把A1B2B3B4放到一边，B1和三个正常的C硬币放一边。（第二次）
情况一：天平平衡了。
特殊硬币在A2A3A4里面，而且知道特殊硬币比较重。
把A2A3称一下，就知道三个里面哪个是特殊的了。（第三次）
情况二：天平依然是A1的那边比较重。
特殊的硬币在A1和B1之间。
随便拿一个和正常的称，就知道哪个特殊了。（第三次）
情况三：天平反过来，B1那边比较重了。
特殊硬币在B2B3B4中间，而且知道特殊硬币比较轻。
把B2B3称一下，就知道哪个是特殊的了。（第三次）

答案来自百度知道

Answer 2

因为题目一定是有解的，即在这12枚硬币，2中重量的24个组合中(coin，weight)有且仅有一组满足输入的情况。下面我们就在这24中可能结果中搜索，找到这一种情况就可以了

#include <stdio.h>
#include <string.h>
/* lf:left side; rt:right side; ans:up/down/equal */
char lf[3][7], rt[3][7], ans[3][6];

bool isLight(char);
bool isHeavy(char);

int main()
{
//freopen("dat.txt", "r", stdin);
int tc;
scanf("%d", &tc);
//测试的数据的组数
while(tc--){
for(int i = 0; i < 3; i++)
scanf("%s %s %s", lf[i], rt[i], ans[i]);

for(int i = 0; i < 12; i++) {
char cur = 'A' + i;
/* 假设硬币cur是重的，看是否满足输入数据 */
if(isHeavy(cur))
printf("%c is the counterfeit coin and it is heavy.n", cur);
/* 否则，假设硬币cur是重的，看是否满足输入数据 */
else if(isLight(cur))
printf("%c is the counterfeit coin and it is light.n", cur);
}
}

return 0;
}

bool isLight(char cur)
{
for(int i = 0; i < 3; i++) {
switch(ans[i][0]) {
/* 假设假币偏轻时，若右侧为up,则假币必在右侧；若两边平衡，则假币必不在两侧；若右侧为down，则假币必在左侧 */
case 'u' : if(strchr(rt[i], cur) == NULL) return false;
break;
case 'e' : if(strchr(lf[i], cur) != NULL ||
strchr(rt[i], cur) != NULL) return false;
break;
case 'd' : if(strchr(lf[i], cur) == NULL) return false;
break;
}
}
return true;
}

bool isHeavy(char cur)
{
for(int i = 0; i < 3; i++) {
switch(ans[i][0]) {
/* 假设假币偏重时，若右侧为up,则假币必在右左侧；若两边平衡，则假币必不在两侧；若右侧为down，则假币必在右侧 */
case 'u' : if(strchr(lf[i], cur) == NULL) return false;
break;
case 'e' : if(strchr(lf[i], cur) != NULL || strchr(rt[i], cur) != NULL) return false;
break;
case 'd' : if(strchr(rt[i], cur) == NULL) return false;
break;
}
}
return true;
}