一个我想不通的面试题

Question

所以写了一段代码在pycharm

解决这个问题：
选择任何 5 个正整数 加起来等于 100
并通过加法、减法或仅使用五个值
之一你应该能够让每个数字达到 100
例如 1,22,2,3,4
对于 1 我可以放弃 1
对于 2 我可以放弃 2
等等
21 我可以给 22 - 1
对于 25 我可以给出 (22 + 2) - 1

li = [1, 1, 1, 1, 1]
lists_of_li_that_pass_T1 = []
while True:
    if sum(li) == 100:
        list_of_li_that_pass_T1.append(li)
        if li[-1] != 100:
            li[-1] += 1
        else:
            li[-1] = 1
            if li[-2] != 100:
                li[-2] += 1
            else:
                li[-2] = 1
                if li[-3] != 100:
                    li[-3] += 1
                else:
                    li[-3] = 1
                    if li[-4] != 100:
                        li[-4] += 1
                    else:
                        li[-4] = 1
                        if li[-5] != 100:
                            li[-5] += 1
                        else:
                            break
    else:
        if li[-1] != 100:
            li[-1] += 1
        else:
            li[-1] = 1
            if li[-2] != 100:
                li[-2] += 1
            else:
                li[-2] = 1
                if li[-3] != 100:
                    li[-3] += 1
                else:
                    li[-3] = 1
                    if li[-4] != 100:
                        li[-4] += 1
                    else:
                        li[-4] = 1
                        if li[-5] != 100:
                            li[-5] += 1
                        else:
                            break

这应该会给出总数 1*10 ** 10 中加起来为 100 的所有数字组合
但它不起作用请帮我修复它以便打印所有整数集
我也想不出下一步我该怎么做才能得到解决问题的完美集

Answer 1

@JohnY 评论后，我认为问题是：

Find a set of 5 integers meeting the following requirements:

their sum is 100

any number in the [1, 100] range can be constructed using at most once the elements of the set and only additions and substractions

暴力方式当然是可能的，但证明任何数字都可以用这种方式构造将是乏味的。但是分而治之的策略是可能的：用一组 m 个数字 u₀..., u_{m-1[=83 构造所有直到 n 的数字=], 用 u₀..., u_m-2 就可以构建到 (n+2)/3 的所有数字并使用 u_m-1 = 2*n/3。 ((n+2)/3, u_m-1) 范围内的任何数都可以写成 u_m-1-x x 在 [1, (n+2)/3] 范围内，并且 (u_m-1, n] 范围内的任何数字为 u_m-1+y y 在相同的低范围内。}

所以我们可以在这里使用 u₄ = 66 并找到一种方法来构建最多 34 个数字和 4 个数字。

让我们迭代：u₃ = 24 并用 3 个数字构建最多 12 个数字。

再一步 u₂ = 8 并构建最多 4 个数字和 2 个数字。

ok: u₀ = 1 and u₁ = 3 马上给:

1 = u₀
2 = 3 - 1 = u₁ - u₀
3 = u₁
4 = 3 + 1 = u₁ + u₀

完成。

数学题外话：

事实上 u₀ = 1 和 u₁ = 3 可以构建所有数字到 4，所以我们可以使用 u₂ = 9 构建所有数字直到 9+4 = 13。我们可以很容易地证明序列 u_i = 3ⁱ 验证 sum(u_i for i in [0, m-1]) = 1 + 3 + ... + 3^m-1 = (3^m - 1)/(3 - 1) = (u_m - 1) / 2.

所以我们可以使用 u₀=1, u₁=3, u₂=9, u₃=27 构建所有数字直到40，最后设置u₄ = 60.

其实u₀和u₁只能是1和3和u₂可以是8或9。那么如果u₂ == 8，u₃可以在[22, 25]范围内，并且如果 u₂ == 9，u₃ 可以在 [21, 27] 范围内。上限由 3ⁱ 序列给出，下限由构建数字的要求给出，3 个数字最多为 12，4 个数字最多为 34。

没有使用代码，但我认为这种方式更快，更不容易出错。现在可以使用 Python 来表明所有 100 以内的数字都可以使用分而治之的策略从其中一个集合中构造出来。

一个我想不通的面试题

A test interview question I could not figure out

python

nested-lists

python-3.x

所以写了一段代码在pycharm