Я предлагаю вам начать с нескольких раундов 2048. Но не вини меня, если не можешь остановиться.
В вашем списке слагаемых есть наименьшее, 2−k. Вы можете масштабировать всю сумму на 2k, чтобы сделать все числа целыми, а на самом деле степенями двойки. Это может облегчить размышления о проблеме. Теперь подумайте о сумме как об операции над двоичными числами, например.
0100
0100
0100
0010
0001
+ 0001
= 10000
Начните складывать наименьшие целые числа. Их должно быть два. В противном случае вы не могли бы обнулить последний бит. Исключение из этого правила, если n=1, т.е. у вас есть только одно слагаемое. Таким образом, вы можете сложить два самых маленьких числа, чтобы получить одно, которое в два раза больше. Затем продолжайте, пока не дойдете до одного числа. Вы можете сделать то же самое с двоичными дробями, чтобы избежать шага масштабирования, если хотите.
Таким образом, важным инвариантом здесь является то, что вы можете добавлять термины таким образом, чтобы они оставались отрицательными степенями двойки. Последовательность дополнений сформирует двоичное дерево со значением узла, указываемым глубиной: корень имеет 1, следующий уровень 1/2, следующий 1/4 и так далее. Каждый узел является либо листом без дочерних элементов, либо внутренним узлом с двумя дочерними элементами. Вас интересуют бинарные деревья с n листьями, но деревья считаются равными, если они имеют одинаковое количество листьев на каждом уровне.
Чтобы начать думать рекурсивно, как перейти от дерева с n листьями к дереву с n+1 листьями? Вы добавляете пару дочерних элементов к существующему листу. Давайте напишем код на Python.
def expansions(v):
for i in range(len(v) - 1):
if v[i]:
yield tuple(x - 1 if j == i else x + 2 if j == i + 1 else x
for j, x in enumerate(v))
yield v[:-1] + (v[-1] - 1, 2) # start a new level
s = set([(1,)]) # start with a bare root
for n in range(1, 21):
print("{:4d}: {:10d}".format(n, len(s)))
s = set(y for x in s for y in expansions(x))
Затем перейдите на http://oeis.org/ и введите последовательность, которую вы получили с трудом. Поиск отобразит одно обращение, A002572, которое описано как
Количество разбиений 1 на n степеней 1/2
Бинго. К сожалению, он не имеет закрытой формулы. Но есть список значений, предварительно рассчитанных для n=2000. Итак, вот сценарий оболочки для определения результата для любого заданного n путем поиска в нем:
wget -qO- 'http://oeis.org/A002572/b002572.txt' | tail -n+${n:?} | head -n1 | cut -d' ' -f2
Если вам нужен более серьезный ответ, я предлагаю вам следовать ссылкам, приведенным в OEIS. Или попытайтесь понять эту функцию v, которая описана как
v(c, d) — количество разбиений d на натуральные числа вида d = c + c1 + c2 + … + cn, где c1 ≤ 2 c, ci+1 ≤ 2 ci< /под>.
и который используется для магического динамического программирования в Mathematica, Maple и Pari.
Так где связь? Чтобы ответить на этот вопрос, переключитесь с рассмотрения листовых узлов на рассмотрение внутренних узлов. Если у вас n конечных узлов, то у вас есть d=n−1 внутренних узлов. v(1,d) подсчитывает способы размещения этих внутренних узлов путем разделения количества внутренних узлов в соответствии со слоем. Вам нужен один внутренний узел в корне, если только у вас не n=1, что не полностью охвачено этим соображением. И каждый последующий слой может иметь как минимум ноль внутренних узлов и не более чем удвоенное количество внутренних узлов предыдущего слоя.
За исключением угловых случаев, основная рекурсия
v(c, d) = sum(v(i, d-c) for i=1..2*c)
потому что если d=c+c1+c2< /sub>+…+cm, тогда это соответствует d−c =c1+c2+…+cm, поэтому вам нужны способы разделения d-c, где i=c1 находится между 0 и 2 c . Это можно использовать для хорошей реализации динамического программирования. Вот все значения, которые вам нужно вычислить до d=20, т. е. n=21:
v(c,d) c=1 c=2 c=3 c=4 c=5 c=6 c=7 c=8 c=9
d= 1: 1
d= 2: 1 1
d= 3: 2 1 1
d= 4: 3 2 1 1
d= 5: 5 4 2 1 1
d= 6: 9 7 4 2 1 1
d= 7: 16 12 7 4 2 1 1
d= 8: 28 22 13 7 4 2 1 1
d= 9: 50 39 24 13 7 4 2 1 1
d=10: 89 70 42 24 13 7 4 2
d=11: 159 126 76 43 24 13 7 4
d=12: 285 225 137 78 43 24 13 7
d=13: 510 404 245 140 78 43 24 13
d=14: 914 725 441 251 141 78
d=15: 1639 1299 792 452
d=16: 2938 2331 1420 812
d=17: 5269 4182 2550 1457
d=18: 9451 7501
d=19: 16952 13458
d=20: 30410
person
MvG
schedule
25.09.2018
