Страниц: [1] 2 3
  Печать  
Автор Тема: Злобная задача для хитрых программистов  (Прочитано 17157 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Sirion
Гений-Говорун
*****
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
: Июнь 28, 2012, 23:49:19 �

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

Эти пользователи сказали вам СПАСИБО :

zhekas

За это сообщение 1 пользователь сказал спасибо!
Последнее редактирование: Июнь 29, 2012, 00:07:51 от Sirion Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
zhekas
Гений-Говорун
*
Offline Offline

Сообщений: 1035

СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486



Просмотр профиля Email
Ответ #1 : Июнь 29, 2012, 00:14:34 �

С повторениями?
Записан
Sirion
Гений-Говорун
*****
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #2 : Июнь 29, 2012, 00:16:26 �

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

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
zhekas
Гений-Говорун
*
Offline Offline

Сообщений: 1035

СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486



Просмотр профиля Email
Ответ #3 : Июль 01, 2012, 13:49:27 �

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

Сообщений: 1161

СПАСИБО
-вы поблагодарили: 277
-вас поблагодарили: 341


Любовь - дело техники

623784586
Просмотр профиля Email
Ответ #4 : Июль 01, 2012, 14:03:04 �

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

"за полчаса до смерти..."
Показать скрытый текст
//текст доступен после регистрации//
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #5 : Июль 01, 2012, 16:13:42 �

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

Зачем откладывать на завтра то, что можно отложить на послезавтра?
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #6 : Июль 01, 2012, 17:36:58 �

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

Сообщений: 1161

СПАСИБО
-вы поблагодарили: 277
-вас поблагодарили: 341


Любовь - дело техники

623784586
Просмотр профиля Email
Ответ #7 : Июль 01, 2012, 17:57:16 �

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

Эти пользователи сказали вам СПАСИБО :

Smith

За это сообщение 1 пользователь сказал спасибо!
Записан

"за полчаса до смерти..."
Показать скрытый текст
//текст доступен после регистрации//
Sirion
Гений-Говорун
*****
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #8 : Июль 02, 2012, 03:01:01 �

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

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Um_nik
Гений-Говорун
*
Offline Offline

Сообщений: 1161

СПАСИБО
-вы поблагодарили: 277
-вас поблагодарили: 341


Любовь - дело техники

623784586
Просмотр профиля Email
Ответ #9 : Июль 02, 2012, 06:40:04 �

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

"за полчаса до смерти..."
Показать скрытый текст
//текст доступен после регистрации//
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #10 : Июль 02, 2012, 15:12:27 �

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

спасибо
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #11 : Июль 02, 2012, 15:53:53 �

вот, у меня получается так:
чтобы набрать любое от 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 пока не увенчались успехом  Тормоз
прошу помощи  Помощь
Записан
Um_nik
Гений-Говорун
*
Offline Offline

Сообщений: 1161

СПАСИБО
-вы поблагодарили: 277
-вас поблагодарили: 341


Любовь - дело техники

623784586
Просмотр профиля Email
Ответ #12 : Июль 02, 2012, 15:56:10 �

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

"за полчаса до смерти..."
Показать скрытый текст
//текст доступен после регистрации//
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #13 : Июль 02, 2012, 16:01:38 �

от 2^0 до 2^9 и любое из чисел от 1 до 1024
напиши тупо 11 чисел из которых можно выбрать числа, из суммы которых можно составить любое число от 1 до 1024
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #14 : Июль 02, 2012, 16:03:31 �

а! можешь написать остро!! Wink
Записан
Страниц: [1] 2 3
  Печать  
 
Перейти в: