检查是否可以通过将单个起始数字连续减半来产生一组数字

Question

给定一组数字，我想检查是否可以通过重复地将一个起始数字分成两半并对每一半的两半执行相同的操作来生成完整的数字集，如果可能的话找出可以实现这一目标的最小可能数字是多少。

如果要分割的数字

n

是奇数，则会分别分割为

floor(n/2)

和

ceiling(n/2)

。

例如给定集合

[1, 4, 5]

，最小的可能数字是

18

，因为它分裂成

9

和

9

，然后分别分裂成

4, 5

和

4, 5

。我们保留一对

4, 5

，并将另一对分成

2, 2, 2, 3

，最后分成

1, 1, 1, 1, 1, 1, 1, 2

。这样就得到了

1, 4, 5

。

另一方面，对于集合

[1, 2, 3, 4, 5, 6]

，无论以任何起始数字都不可能获得这些数字。

如何有效解决这个问题？我知道这似乎是某种整数分区问题，但除了直接暴力破解每个数字之外，我想不出任何明智的方法来做到这一点。

Answer 1

我尝试了这个问题并得到了第一个想法，我想与你分享！

Given your example set [1,4,5] the answere seems to be 2*9!
(1,4,5 => 2,4,5 => 4,5 => 4+5=9 => 9)

1,2,3,4,5,6 (multiply smaller numbers by 2^n to eliminate "same smaller" ones)
=> 4,5,6 (combine n with n+1)
=> 4+5=>9 5+6=>11
=> 9, 11 not a single number.

似乎步骤足够了。 然后我生成了这段代码，因为它减少了集合并且在发散之前无法找到单个数字：

import bisect
l = [1,2,3,4,5,6]
l.sort()
while len(l)>1:
    print(l)
    smallest = l.pop(0)
    l.insert(bisect.bisect_left(l,smallest<<1),smallest<<1)
    i=0
    while i+1<len(l):
        a,b = l[i],l[i+1]
        if a==b: 
            l.pop(i)
            print(l)
            continue
        if a+1==b:
            l.pop(i)
            l.pop(i)
            l.insert(bisect.bisect_left(l,a+b),a+b)
            i = max(0,i-1) #value before got new partner
            print(l)
            continue
        i+=1
    input()

现在您只需停止检测到错误的验证器即可。 您还可以计算需要多少个数字来生成该集合并相应地乘以最后一个数字！