题目
如果有砝码序列【1, 3, 9, 27, 81, 243, 729 】
我们至少可以称量1000以内的所有整数重量
比如: 5 = 9 - 3 - 1 即:9 放入对侧盘,3,1 放入同侧盘
再比如: 19 = 27 - 9 + 1
编程的目标是:给定一个重量,求:天平称重时,砝码的放置方案。
解法一
只有 7 个砝码,每个砝码有三种放置方法:放左边,放右边,不放。
因而,总的可能组合方案数为 3 的 7 次方种。
我们只有逐一枚举所有的可能方案,再筛选符合要求的就可以了。
这是典型的暴力破解。
直接 7 层 for 循环嵌套似乎是可以,但有点丑陋,并且将来也无法扩展。
用递归比较容易点。
# 天平与砝码
'''
天平称重时,砝码可以放在左盘或右盘
有砝码:[1, 3, 9, 27, 81, 243, 729]、
给定 1000 以内待称重量 w
求称重方案
例如:w = 5
则返回 [-1, -3, 9]
'''
# w: 待称重量
# 返回使用的砝码列表,放在物品同侧的为负值
def fama(w):
a = [3**i for i in range(7)]
b = [0] * len(a)
# 考虑放置 k 号位置
def f(k):
if<