Тестовый вопрос, который я не мог понять

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

это должно дать мне все комбинации чисел, которые складываются до 100 из общего 1 * 10 ** 10
но он не работает, пожалуйста, помогите мне исправить это, чтобы он печатал все наборы целых чисел
Я также не могу думать о том, что я буду делать дальше, чтобы получить идеальные наборы, которые решают проблему

Answer 1

После комментариев @JohnY я предполагаю, что вопрос:

Найдите набор из 5 целых чисел, удовлетворяющих следующим требованиям:

• их сумма равна 100
• любое число в диапазоне [1, 100] может быть построено с использованием не более одного раза элементов набора и только дополнений и вычитаний

Конечно, возможен метод грубой силы , но доказывать, что любое число может быть построено таким образом, было бы утомительно. Но стратегия «разделяй и властвуй» возможна: для построения всех чисел до n с помощью набора чисел m u ₀ ..., u _m-1 , достаточно построить все числа до (n + 2) / 3 с u ₀ ..., u _m-2 и использованием 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 и строить числа до 12 с 3 числами.

Еще один шаг u ₂ = 8 и строить числа до 4 с 2 числами.

Ok : u ₀ = 1 и u ₁ = 3 дают сразу:

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

Готово.

---

Математическое отступление:

Фактически вы ₀ = 1 и u ₁ = 3 может собрать все числа до 4, поэтому мы можем использовать u ₂ = 9 для построения всех чисел до 9+ 4 = 13. Мы можем легко доказать, что последовательность u _i = 3 ⁱ проверяет сумму (u _i для i в [0, m-1]) = 1 + 3 + ... + 3 ^м-1 = (3 ^м - 1) / (3 - 1) = (u _м - 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 ⁱ , а нижний предел задается требованием строить числа до 12 с тремя числами и до 34 с четырьмя.

Код не использовался, но я думаю, что это намного быстрее и менее подвержено ошибкам. Теперь можно использовать Python, чтобы показать, что все числа до 100 могут быть построены из одного из этих наборов с использованием стратегии «разделяй и властвуй».