Разложение числа на слагаемые17.08.2011, 12:48. Показов 69047. Ответов 54
Метки нет (Все метки)
Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная задача). И мне стало интересно: какой самый быстрый алгоритм разложения числа на слагаемые вы предложите? Думаю, максимальный тест n<=50.
З.Ы. Проверю на время сам. И разложения должны быть без повторений (перестановка слагаемых не дает новых разложений) и чтоб строка слагаемых выводилась в файл "in.txt".
0
|
|
| 17.08.2011, 12:48 | |
|
Ответы с готовыми решениями:
54
Разложение натурального положительного числа на слагаемые? Разложение на слагаемые |
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|||||||
| 18.08.2011, 10:44 | |||||||
А вы так тестируете?
0
|
|||||||
|
|
|
| 18.08.2011, 10:47 | |
|
Olga_, Dani, на время тестирования отключайтесь от инета и отключайте антивирус. У меня с ним время выполнения прыгает на 1000мс в каждую сторону, без него - разброс порядка 300мс.
Добавлено через 44 секунды Да, и на винде консоль тормознутая, не выводите на неё.
0
|
|
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
| 18.08.2011, 10:49 | |
|
0
|
|
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||
| 18.08.2011, 10:52 | ||
![]() Я просто хочу привлечь ваше внимание к тому, что алгоритм получился очень экономичным и быстрым
0
|
||
|
|
||||||
| 18.08.2011, 10:56 | ||||||
|
Вот доказательство тормознутости вывода
А варианты сейчас прогоню у себя и отпишусь
1
|
||||||
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||||||
| 18.08.2011, 11:03 | ||||||
Сообщение было отмечено как решение
Решение
Тот же самый алгоритм на С++:
1
|
||||||
|
Higher
|
||
| 18.08.2011, 11:05 | ||
|
Сменить язык, немного изменить условия - получится то же самое. Даже аргументы функций практически совпадают. P.S. clock'ом неточно измерять, погрешность у него высокая. Попробую у себя более точно time'ом замерить.
0
|
||
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||
| 18.08.2011, 11:07 | ||
После смены языка - пост 27. И все же алгоритмы немного разные и написаны независимо
0
|
||
|
Higher
|
||||||
| 18.08.2011, 11:11 | ||||||
Но это все-таки погрешность, ибо разницы в коде практически нету. Причем с ключем -O3, что странно, обе программы медленнее работают..
1
|
||||||
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||
| 18.08.2011, 11:15 | ||
|
Diagon, я не хвалю свой алгоритм, просто хочу понять почему так... Почему ваш у вас быстрее, а мой - у меня, чудо какое-то...
1
|
||
|
Higher
|
||
| 18.08.2011, 11:22 | ||
|
Результат будет зависеть от компилятора(gcc оба кода отлично соптимизировал, а какой-нибудь VC вообще повиснет при компиляции), загруженности системы, расположения звезд на небе... По поводу отсечения - алгоритмы одинаковые, разная реализация. У вас она более оптимальная, а у меня более понятная и больше простора оптимизирующему компилятору =)
0
|
||
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||
| 18.08.2011, 11:26 | ||
|
0
|
||
|
|
|
| 18.08.2011, 11:35 | |
|
Я не эксперт, но вот, прогнал Сишный вариант Ольги, первый вариант diagon (извините, не знаю как склоняется ваш ник
) и последний вариант -=ЮрЫ=-, все при n = 50. Единственное - ко всем прикрутил метод замера через разницу показаний clock() до и после просчёта, и весь вывод, кроме результатов замера, отправил в файл. К моему великому удивлению:Olga_ - 1109, 1109, 1125, 1110, 1141, 1142, avg = 1122,6666 diagon - 226, 265, 250, 250, 255, 250, avg = 249,3333 -=ЮрА=- - 0, 16, 0, 16, 16, 0, avg = 8 Теперь о выводе: У diagon и Ольги вывод выглядит равноценным и занимает под 6 метров. У -=ЮрЫ=- он занимает 47,7 килобайт, но и выдаёт не все варианты разложения слагаемых. Файловый вывод в варианте diagon был через std::ofstream (c++ так c++), а в Ольгином и -=ЮриноМ=- через fprintf. При глупой и наивной попытке скопировать вывод Ольги в сообщение firefox сильно задумался, по-этому пришлось снять задачу... Выкладываю файлами. test_c_2.7z Система: Windows XP SP2 (увы, какая была загружена, такая и была загружена) AMD Turion X-2 DualCore Mobile RM-74 2.2 GHz (к чёрту DualCore, всё равно в одном потоке выполняется) 3 Gb RAM gcc 4.4.1 TDM-2 mingw
2
|
|
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
| 18.08.2011, 11:38 | |
|
0
|
|
|
Higher
|
||
| 18.08.2011, 11:42 | ||
|
Это как вообще? А разница банально в оптимизации.. Только результат действительно нереалистичный какой-то, даже если компилировать с ключами на максимальную оптимизацию.
0
|
||
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|||
| 18.08.2011, 11:44 | |||
Но спасибо за тест![]() Добавлено через 1 минуту
0
|
|||
|
|
||||||||
| 18.08.2011, 11:53 | ||||||||
|
Добавлено через 8 минут Не по теме: У всех было 502 bad gateway..? Вот код Юры, который я компилировал. Сами смотрите:
0
|
||||||||
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||
| 18.08.2011, 11:57 | ||
|
Придется признать, что у diagon оптимальнее вариант
1
|
||
| 18.08.2011, 11:57 | |
|
Разложение на слагаемые разложение на все возможные слагаемые
Разбиение числа на слагаемые Найти все слагаемые заданного числа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Теория всего 12. ВГК
anaschu 21.07.2026
### Главные семантические изменения и дешифровка новой физики
1. **`REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`)**: Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .
|
Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание
Hrethgir 21.07.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928
Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .
|
Теория всего 11. Основные параметры
anaschu 21.07.2026
Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего
Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .
|
Теория всего 10. Клод трусишка
anaschu 21.07.2026
Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы
Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
|
|
Теория всего 9. Окончательная проработка метафоры "дерево = традиции"
anaschu 21.07.2026
Скрытые параметры ядра ОДУ: Механика Глубинного Рока
Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .
|
Теория всего 8. Clauude трусишка. Ответ джемени
anaschu 21.07.2026
Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .
|
Теория всего 7. Дерево - это патриархат, грибы - это феминизм
anaschu 21.07.2026
Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат»
Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .
|
История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры.
anaschu 21.07.2026
Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .
|