枚举——称硬币

1. 枚举

枚举是基于逐个尝试答案的一种问题求解策略。

2. 称硬币(POJ1013)

  • 问题描述 有12枚硬币。其中有11枚真币和1枚假币。假币和真币重量不同,但不知道假币比真币轻还是重。现在,用一架天平称了这些币三次,告诉你称的结果,请你找出假币并且确定假币是轻是重(数据保证一定能找出来)。
  • 输入 第一行是测试数据组数。 每组数据有三行,每行表示一次称量的结果。银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示:天平左边放置的硬币、天平右边放置的硬币、平衡状态。其中平衡状态用updowneven表示,分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。
  • 输出 输出哪一个标号的银币是假币,并说明它比真币轻还是重。
  • 输入样例
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
  • 输出样例 K is the counterfeit coin and it is light.
  • 解题思路

对于每一枚硬币先假设它是轻的,看这样是否符合称量结果。如果符合,问题即解决。如果不符合,就假设它是重的,看是否符合称量结果。把所有硬币都试一遍,一定能找到特殊硬币。

  • 分析

根据硬币的状态(轻重)和硬币所处的位置(左右或无)可以判断出称重结果,如果三次判断的结果与真实结果都相符,则当前硬币及当前状态即为结果。

  • 代码
#!/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

参考资料

  1. 程序设计与算法(二)算法基础

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

LeetCode小白菜笔记4:Roman to Integer

LeetCode小白菜笔记[4]:Roman to Integer13. Roman to Integer [Easy] 题目:Given a roman n...

1898
来自专栏张善友的专栏

Active Record和Domain Object + Dao

Martin Fowler的 Active Record pattern实现,它是指一个既包含数据又包含行为的对象,这些数据需要持久保存到对应的数据表中。...

1769
来自专栏java架构师

Hadoop学习19--推测式执行

  所谓推测式执行,就是计算框架判断,如果有一个task执行的过慢,则会启动备份任务,最终使用原任务+备份任务中执行较快task的结果。产生原因一般是程序bug...

2719
来自专栏哲学驱动设计

WCF 框架运行时类图

本文画出了 WCF 框架运行时的重点类之间的类关系图。 Binding 一个 Binding 由多个 BindingElement 组成。BindingElem...

1785
来自专栏芋道源码1024

【Netty 专栏】深入浅出 Netty 内存管理 PoolChunk

摘要: 原创出处 https://www.jianshu.com/p/c4bd37a3555b 「占小狼」欢迎转载,保留摘要,谢谢!

790
来自专栏大内老A

WCF客户端运行时架构体系详解[上篇]

客户端调用WCF服务的方式不外乎有两种:其一、通过代码生成工具(比如SvcUtil.exe)导入服务的元数据生成服务代理相关的类型;其二、通过ChannelFa...

16910
来自专栏hi

原生HTTP服务器

let server = http.createServer((req, res) => {

1746
来自专栏wym

2018年湘潭大学程序设计竞赛 F题题解

小明来到一个由n x m个格子组成的迷宫,有些格子是陷阱,用'#'表示,小明进入陷阱就会死亡,'.'表示没有陷阱。小明所在的位置用'S'表示,目的地用'T'表示...

432
来自专栏数据结构与算法

1506 传话

1506 传话 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 一个朋友网...

2695
来自专栏灯塔大数据

每周学点大数据 | No.60磁盘算法实践

NO.60 磁盘算法实践 Mr. 王:前面讨论了很多理论方面的内容,从今天开始,我们研究如何从实践的角度去进行磁盘算法、并行算法和众包算法的设计。 小可:嗯,...

35811

扫码关注云+社区