N个砝码

雨点打透心脏的1/2处 2024-04-01 12:40 56阅读 0赞

有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}

更多尝试人民币面额；

本文由[ mdnice ][mdnice]多平台发布

[mdnice]: https://mdnice.com/?platform=4