Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Для практического подсчёта эта формула наиболее удобна. Можно ли её привести к какому-нибудь "более приемлемому" виду --- не знаю. Возможно, что и нет.
Добавлено спустя 29 минут 21 секунду:
Лучше даже с нуля начинать, тогда формулы будут покрасивше.
Имеем для любого и
Получается, что дельты уже не нужны.
the_mescalito
07.05.2008, 08:54
А как оценить в этой рекурсивной формуле зависимость от ? Она полиномиальна или экспоненциальна?..
Trotil
07.05.2008, 09:25
Я решал похожую задачу, правда (1,1,2); (1,2,1); (2,1,1) считал за одно разбиение. Помнится, получить явную формулу у меня получилось.
Профессор Снэйп
07.05.2008, 09:40
the_mescalito писал(а):
А как оценить в этой рекурсивной формуле зависимость от ? Она полиномиальна или экспоненциальна?..
При больших сумма при вычислении будет состоять из слагаемых. То есть для фиксированного при данном при вычислении нужно выполнить порядка сложений.
Получается линейная зависимость от и экспоненциальная от длины двоичной записи .
Но, кстати, я подозреваю, что по величине растёт экспоненциально с ростом . Так что экспоненциальная зависимость времени вычисления от длины двоичной записи будет иметь место при любом алгоритме вычисления.
the_mescalito
07.05.2008, 09:50
Trotil А как Вы решали свою задачу? Можете припомнить?
Trotil
07.05.2008, 10:14
the_mescalito Припоминаю, что аналогично, как и Профессор Снэйп. То есть через реккуренты.
the_mescalito
07.05.2008, 10:40
Профессор Снэйп писал(а):
А Вы не могли бы пояснить на пальцах, как эта формула получается?
Откуда дельта мне понятно.. А откуда все берутся?
maxal
09.05.2008, 03:24
Ответом также будет коэффициент при в разложении
Отсюда можно получить явную формулу:
где - это коэффициент при в разложении :