枚举——称硬币

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 条评论
登录 后参与评论

相关文章

来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

4988
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(1) (原创内容,转载请注明来源,谢谢) 一、连通分量和生成树 1、无向图 设E(G)为连通图G的所...

3699
来自专栏简书专栏

Python数据科学库-小测验

答:np.arange、np.array、np.ones、np.zeros、np.full

871
来自专栏King_3的技术专栏

leetcode-202-Happy Number

3007
来自专栏阮一峰的网络日志

四位计算机的原理及其实现

你是否想过,计算机为什么会加减乘除?或者更直接一点,计算机的原理到底是什么? Waitingforfriday有一篇详细的教程,讲解了如何自己动手,制作一台四位...

3286
来自专栏炉边夜话

考场安排---图的着色原理之运用

试设计一算法,当给定一个图时G=(V,E),|V|=n,(Vi,Vj)ЄE,当且仅当有一个同学选了课程i和课程j,试给出一个考试安排方案N1,N2,N3…Nk,...

741
来自专栏工科狗和生物喵

【计算机本科补全计划】CCF计算机职业资格认证 201709-01/02详解

正文之前 貌似我找到的那个题目网站更新了一波最新的题目。不过201709 只有1、2 题,所以先做了吧(其实是我自己对能不能做出第三题 持怀疑态度!)宝宝心里苦...

3016
来自专栏算法channel

除自身累乘算法题,又有创意解法了

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1)...

940
来自专栏算法修养

pta 习题集5-18 打印学生选课清单

假设全校有最多40000名学生和最多2500门课程。现给出每门课的选课学生名单,要求输出每个前来查询的学生的选课清单。 输入格式: 输入的第一行是两个正整...

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

一个例子教你如何与出题人斗智斗勇

我以前出过一道题,卡了10种贪心,但还是被第11种贪心A了,  一道题不会做?贪嘛,能怎么贪怎么贪,想怎么贪怎么贪! 现在NOIP题目的数据给的不...

2646

扫码关注云+社区