轉(zhuǎn)載請(qǐng)注明出處：優(yōu) YoU? http://blog.csdn.net/lyy289065406/article/details/6661421
大致題意：
有一打（12枚）硬幣，其中有且僅有1枚假幣，11枚真幣
用A~L作為各個(gè)硬幣的代號(hào)
假幣可能比真幣略輕，也可能略重
現(xiàn)在利用天枰，根據(jù)Input輸入的3次稱量，找出假幣，并輸出假幣是輕還是重。
解題思路：
模擬法要考慮的情況較繁瑣，可利用簡(jiǎn)單的邏輯推理進(jìn)行解題。
注意Input一行代表一次稱量，每行有三個(gè)字符串，分別為
Left?? right???? status
代表該次稱量時(shí)，天枰左盤放的硬幣、天枰右盤放的硬幣、天枰 右盤 的狀態(tài)
共三種狀態(tài)：
Up：右盤上升，說(shuō)明右盤可能有輕假幣，也可能左盤有重假幣。
Down：右盤下降，說(shuō)明右盤可能有重假幣，也可能左盤有輕假幣。
Even：右盤與左盤平衡，由于假幣有且僅有1枚，則說(shuō)明此時(shí)天枰兩邊的硬幣全為真幣。
注意題目的字眼：
1、? 有且僅有1枚假幣
2、? 假幣相對(duì)于真幣的重量，可能輕可能重
3、? 只稱量3次，且稱量3次恰好且必能找到假幣
4、? 每次稱量時(shí)天枰兩邊的硬幣數(shù)目一樣
5、? 選取哪些硬幣稱量由input決定
從3、4、5可知，由于無(wú)法知道每次選取稱量的硬幣，那么3次稱量可能只選用了幾個(gè)硬幣，也可能僅有一兩個(gè)硬幣沒(méi)有選上，那么用模擬法去記錄每次用于稱量的硬幣的狀態(tài)（真假，其中假幣又有輕重之分）并推導(dǎo)沒(méi)有被稱量的硬幣狀態(tài)（或狀態(tài)變化）是很困難的，雖然人很容易做到這點(diǎn)，但計(jì)算機(jī)卻很難去“推導(dǎo)”，因?yàn)榉Q量硬幣的方法是無(wú)規(guī)律的且非常多。
那么只能通過(guò)適當(dāng)轉(zhuǎn)化問(wèn)題后用另一種有效的方法去解決。
雖然稱量硬幣的方法是無(wú)規(guī)律且未知的，但是稱量硬幣后的結(jié)果卻只有3個(gè)，up、down和 even。且當(dāng)出現(xiàn)even時(shí)，天枰兩邊的硬幣必然都為真幣，假幣必定在余下的硬幣之間（這是因?yàn)榧賻庞星抑挥幸幻叮敲次覀兙涂梢远x一個(gè)標(biāo)記數(shù)組 zero[]去標(biāo)記even時(shí)的真幣，在以后的處理把他們排除在外。
而唯一難以處理的是up和down的狀態(tài)，因?yàn)榧賻趴赡茌p可能重，則這兩種狀態(tài)都無(wú)法得知究竟假幣出現(xiàn)在天枰的哪邊。
處理up和down狀態(tài)方法：
當(dāng)出現(xiàn)up或down狀態(tài)時(shí)，天枰兩邊的所有硬幣都應(yīng)該被懷疑為假幣（已標(biāo)記必定為真幣的硬幣不必被懷疑）。
首先time[]記錄每個(gè)硬幣的被懷疑程度，time[i]=0表示該硬幣i不被懷疑（即其可能為真幣）。定義在up狀態(tài)盤的硬幣為“輕懷疑假幣”，通過(guò)“--”操作加深其被懷疑為輕假幣的程度，“負(fù)號(hào)”為輕假幣的懷疑方向；在down狀態(tài)盤的硬幣為“重懷疑假幣”，通過(guò)“++”操作加深其被懷疑為重假幣的程度，“正號(hào)”為重假幣的懷疑方向。
那么若一枚真幣被懷疑為“輕假幣”時(shí)，它就可能通過(guò)下次稱量通過(guò)“++”操作取消嫌疑了。初始化所有硬幣的懷疑程度均為0。
稱量完畢后，找出被懷疑程度最大（注意取絕對(duì)值）的硬幣，它就是假幣。而當(dāng)其懷疑方向?yàn)檎龝r(shí)，則其為重假幣。為負(fù)時(shí)，為輕假幣。
1
//
Memory Time
2
//
252K 0MS
3
4
#include
<
iostream
>
5
#include
<
cmath
>
6
using
namespace
std;
7
8
int
main(
void
)
9
{
10
int
cases;
11
cin
>>
cases;
12
for
(
int
c
=
1
;c
<=
cases;c
++
)
13
{
14
char
left[
3
][
6
],right[
3
][
6
],status[
3
][
6
];
15
16
int
time[
'
L
'
+
1
]
=
{
0
};
//
標(biāo)記各個(gè)字母被懷疑的次數(shù)
17
bool
zero[
'
L
'
+
1
]
=
{
false
};
//
標(biāo)記絕對(duì)為真幣的字母（令天枰平衡的所有字母）
18
19
for
(
int
k
=
0
;k
<
3
;k
++
)
20
cin
>>
left[k]
>>
right[k]
>>
status[k];
21
22
for
(
int
i
=
0
;i
<
3
;i
++
)
23
{
24
switch
(status[i][
0
])
//
檢查天枰狀態(tài)
25
{
26
case
'
u
'
:
//
up，天枰左重右輕
27
{
28
for
(
int
j
=
0
;left[i][j];j
++
)
29
{
30
time[ left[i][j] ]
++
;
//
左重
31
time[ right[i][j] ]
--
;
//
右輕
32
}
33
break
;
34
}
35
case
'
d
'
:
//
down，天枰左輕右重
36
{
37
for
(
int
j
=
0
;left[i][j];j
++
)
38
{
39
time[ left[i][j] ]
--
;
//
左輕
40
time[ right[i][j] ]
++
;
//
右重
41
}
42
break
;
43
}
44
case
'
e
'
:
//
down，天枰平衡
45
{
46
for
(
int
j
=
0
;left[i][j];j
++
)
47
{
48
zero[ left[i][j] ]
=
true
;
//
絕對(duì)真幣
49
zero[ right[i][j] ]
=
true
;
//
絕對(duì)真幣
50
}
51
break
;
52
}
53
}
54
}
55
56
int
max
=-
1
;
//
查找被懷疑程度最高的硬幣（假幣）
57
char
alpha;
58
for
(
int
j
=
'
A
'
;j
<=
'
L
'
;j
++
)
59
{
60
if
(zero[j])
//
絕對(duì)真幣
61
continue
;
62
63
if
(max
<=
abs(time[j]))
64
{
65
max
=
abs(time[j]);
66
alpha
=
j;
67
}
68
}
69
70
cout
<<
alpha
<<
"
is the counterfeit coin and it is
"
;
71
if
(time[alpha]
>
0
)
72
cout
<<
"
heavy.
"
<<
endl;
73
else
74
cout
<<
"
light.
"
<<
endl;
75
}
76
return
0
;
77
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
