c
codeye
V1
2022/10/30阅读:21主题:默认主题
N个砝码
有1,2,4,8,16,共个砝码,总共能称出多少种不同的重量?
注意两种规则约定: a/ 砝码只能放在天平一侧; b/ 砝码可以放在天平两侧;
问题关键在于砝码的状态如何表达?
a/ 砝码只能放在天平一侧,砝码只有两个状态
status = [0,1]
wgt = [1,2,4,8,16]
def Perweight(wgt):
setweigt = set()
#range(0,max(weight)
maxwgt = int('0b'+len(wgt)*'1',2)
status = [bin(n)[2:].rjust(5,'0') for n in range(min(wgt),maxwgt+1)]
print(status)
for s in status:
w = sum([int(x)*(int(y)-1) for x,y in zip(wgt,s)])
setweigt.add(abs(w))
return len(setweigt),setweigt
print('只放在天平一侧:',Perweight(wgt))
输出结果:
31
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30}
如何用数学求解?
C(1,5) + C(2,5) + C(3,5) + C(4,5) + C(5,5) = 5 + 10 + 10 + 5 + 1 = 31
b/ status = [-1,0,1]
天平左边 +1,右边 -1,不在天平是 0
1、构造3进制表达每个砝码的状态。天平左边 +1,右边 -1,不在天平是 0
#初始化数组
wgt = [1,2,4,8,16]
#砝码5个
def Trin(n,b): # b = Binary
# 10进制数n 转换为 b进制的数,从0 ->
if not n:return '0'
thr,i = '',1
while n > 0:
d, r = divmod(n, 3)
#print(d,r)
thr += str(r)
if d < 3:
thr += str(d)
return thr[::-1]
n = d
i += 1
n,b = 27,3
print('3进制:',Trin(n,b))
2、枚举 b进制数,从0到bits位之间所有的连续正整数
def Trinary(bits,b): # str tri ->decimal
# 5位的三进制数00000 -> 11111等于10进制的多少?
d = sum([3**int(i) for i in range(bits)])
seq = []
for i in range(0,d+1):
t = Trin(i,b)
t = (bits-len(str(t)))*'0' + t
seq.append(t)
return seq
bits,b = 5,3
print(Trinary(bits,b))
3、穷举 n个砝码所有状态组合并且做去重!
def Perweight(wgt):
setweigt = set()
status = Trinary(len(wgt),b)
for s in status:
w = sum([int(x)*(int(y)-1) for x,y in zip(wgt,s)])
setweigt.add(abs(w))
return setweigt
print(Perweight(wgt))
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30, 31}
更多尝试人民币面额;
作者介绍
c
codeye
V1