Форум умных людей

Сколькими способами можно выбрать 11 натуральных чисел так, чтобы любое натуральное число от 1 до 1024 можно было представить как сумму некоторого их подмножества?

С повторениями?

Имеете в виду, могут ли среди этих 11 чисел быть одинаковые? Да, могут.

Заканчивается обход множеств начинающихся с двух едениц. И количество уже 1627475601. Ещё на подходе множества начинающихся с 1,2. Предположительно, около 3-4 миллиардов.

Неужели нет хорошего решения без длинного перебора? Или вся суть именно написать такую программу, которая адекватно переберет?

у меня получилось приблизительно 250 млрд.

извините меня малообразрванного, но я с подмножеством не понял в условии... кто-нить может "на пальцах" объяснить чего надо?

Напишем наши числа на бумажках.
Для каждого натурального числа от 1 до 1024 можно так выбрать бумажки, чтобы сумма чисел на этих бумажках была равна нужному нам числу.

250 миллиардов - довольно близко к истине
моя программа считает эту задачу где-то за минуту
и принцип её работы далёк от перебора

Сирион, ок. Тогда ничего не имею против)

я конечно дико извиняюсь, но можно хотябы 1 из 250 млрд. решение из 11 чисел. удовлетворяющим условию задачи в студию...

спасибо

вот, у меня получается так:
чтобы набрать любое от 1 до 10 нужно минимум 4 числа, а именно:
1) 1 1 3 5
2) 1 2 3 4
3) 1 2 3 5
4) 1 1 3 6
5) 1 2 3 6 наверное, еще какие-то, но пока что не в этом суть, а суть в том, что сделать это тремя цифрами не получается (во всяком случае, у меня)..
я уже не говорю о том, что цифру 1 суммой вообще набрать нельзя, разве что использовать для этого 0, но ладно, предположим, что нужное число может приравниваться условно к сумме самого себя с виртуальным нулем.

тогда имеем как минимум 4 числа, чтобы набрать десятки, и столько же, чтобы набрать сотни. итого - 12 чисел, и можем набрать любое число от 1 до 1110. мои попытки сократить количество необходимых чисел до11 пока не увенчались успехом  :tormoz:
прошу помощи  :help:

от 2^0 до 2^9 и любое из чисел от 1 до 1024

напиши тупо 11 чисел из которых можно выбрать числа, из суммы которых можно составить любое число от 1 до 1024

а! можешь написать остро!! ;)

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

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

1 1 2 4 8 16 32 64 128 256 512

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сначала был перебор. С помощью рекурсии 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]

Да, у меня точно так же)

В наше время понятие "хитрая задача" уже не существует). Сейчас просто полно различных ресурсов, на которых можно заказать решение задач http://2dip.su/zakazat/reshenie_zadach/ . Стоит это недорого, да и результат предоставляют в короткие сроки.