Злобная задача для хитрых программистов

[Smith]

может, я сложно выражаюсь? вот мой пример:
из суммы чисел (либо их подмножества) 1 2 3 4 10 20 30 40 100 200 300 400 (всего - 12) можно набрать любое число от 0 до 1110. если нужно еще 0 - тогда получается 13.

а теперь вы с 11 числами, пожалуйста

[Um_nik]

1 1 2 4 8 16 32 64 128 256 512

[Smith]

1 1 2 4 8 16 32 64 128 256 512

да, спасибо. теперь понял что ты имел ввиду степени двойки, это зачетно.

ой, а можно еще одну серию? последнюю, больше не буду приставать 

[Um_nik]

меняешь единицу на любое другое число до 1024.

Да можешь сам придумывать)

Первое число - 1.
Любое последующее не больше суммы всех предыдущих и единицы.
Главное, чтобы все вместе давали не меньше 1024.

Любой такой набор удовлетворяет условиям.

[Smith]

я понял. то же, тока вместо 4 будет к примеру 5... и т.д.

я не сомневался, что ответ есть... меня цифра 250 млрд. как-то усомнила... 

[Smith]

Первое число - 1.
Любое последующее не больше суммы всех предыдущих и единицы.
Главное, чтобы все вместе давали не меньше 1024.

Любой такой набор удовлетворяет условиям.

кстати, имхо, это уже не просто перебор, здесь бы выводящую составляющую дописать, тогда и сравнивать ненужно

[Um_nik]

нет, это почти просто перебор.
Ну т.е. он будет долго работать (2^55 циклов (меньше, но все равно)), да и нет никакой задумки хорошей.

[Smith]

интересно, а сколько времени требуется просто на вывод 250 млрд. чисел пусть с минимальным количеством операций по расчету? это же будет, ну, как минимум даже без учета рассчета, правильно?!

[Um_nik]

Зависит от языка, насколько я знаю.
Мне говорили, что на паскале 10^9 операций в секунду. т.е. 4 минуты)

[Smith]

Зависит от языка, насколько я знаю.
Мне говорили, что на паскале 10^9 операций в секунду. т.е. 4 минуты)

значит, у Сириона другой язык.
либо он спутал часы с минутами 

[Um_nik]

Ну, я почти уверен, что Сирион пишет на чем-то покруче паскаля)

[Sirion]

Сирион пишет на всём. В данном случае - на делфи) А при чём здесь вывод? Нужно посчитать количество, а не выводить все возможные комбинации (которые ещё не на всякий жёсткий диск влезут).

[zhekas]

Показать скрытый текст

283645008433

[Sirion]

Истинная истина. Какое было решение?

[zhekas]

Сначала был перебор. С помощью рекурсии Podgon(n,m,k) вычислялась количество для комбинаций из n - членов, которые составлют суммы до m включительно (но m+1 уже не включают) и каждый элемент не превосходит k. В процедуре суммировались Podgon(n-1,m-i,i).

Но выполнялось это долго. Тогда я подумал что функции с одним и тем же параметрами должны повторятся при вычислении. И для n=8 записал таблицу значений a8[m][k] = Podgon(8,m,k). Уже по этой таблице нашёл a9[m][k], затем a10[m][k] и a11[m][k]