枚举是基于逐个尝试答案的一种问题求解策略。
up
,down
或even
表示,分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
对于每一枚硬币先假设它是轻的,看这样是否符合称量结果。如果符合,问题即解决。如果不符合,就假设它是重的,看是否符合称量结果。把所有硬币都试一遍,一定能找到特殊硬币。
根据硬币的状态(轻重)和硬币所处的位置(左右或无)可以判断出称重结果,如果三次判断的结果与真实结果都相符,则当前硬币及当前状态即为结果。
#!/usr/bin/env python
# _*_ coding: utf-8 _*_
input_data = [['ABCD', 'EFGH', 'even'], ['ABCI', 'EFJK', 'up'], ['ABIJ', 'EFGH', 'even']]
labels = 'ABCDEFGHIJKL'
label_status = ['light', 'heavy']
for label in labels:
for status in label_status:
for data in input_data:
flag = True
left = data[0]
right = data[1]
result = data[2]
if label in left:
if status == 'light':
should_be = 'down'
else:
should_be = 'up'
elif label in right:
if status == 'light':
should_be = 'up'
else:
should_be = 'down'
else:
should_be = 'even'
if should_be != result:
flag = False
break
if flag:
print '%s is the counterfeit coin and it is %s.' % (label, status)
K is the counterfeit coin and it is light.
总结:有时候枚举问题并不像那么明显,需要仔细的分析与思考才能想到,当问题不是非常复杂时,有时可以先从枚举开始尝试解决问题。
源码地址:https://github.com/SnailTyan/programming-and-algorithms/blob/master/weigh_coins.py