c

codeye

V1

2022/10/30阅读:13主题:默认主题

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