Разложение числа на слагаемые17.08.2011, 12:48. Показов 69035. Ответов 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 | |
|
Разложение на слагаемые разложение на все возможные слагаемые
Разбиение числа на слагаемые Найти все слагаемые заданного числа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Запрет пометки на удаление и отмены проведения
Maks 16.07.2026
Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2.
Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .
|
Как надо было делать правильно - вообще не слушать ИИ, его дело - текст.
Hrethgir 15.07.2026
А вообще надо было делать не так, чтобы не исправлять ошибку https:/ / www. cyberforum. ru/ blogs/ 223907/ 10996. html , правильно было : удалил кнопку, а потом добавил её.
Всё это стресс конечно. Почему?. . .
|
Знаете, от чего появляется стресс?
kumehtar 15.07.2026
Стресс появляется оттого, что вы, зная как поступить правильно, делаете наоборот.
Ларри Уингет
|
Нас бьют, а мы крепчаем? Какая чушь!
kumehtar 15.07.2026
Вот это вот бытующее мнение, что человек меняется только под действием проблем, всегда считал вредоносным. Поверь, от проблем у людей появляются не изменения, а нервное расстройство и ПТСР. А. . .
|
|
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным?
anaschu 12.07.2026
Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров
В текущей версии модели успешно реализован ключевой механизм. . .
|
сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию.
anaschu 12.07.2026
Анализ соответствия модели требованиям
Реализованные компоненты:
Механизм закисления почвы через протонную помпу
Конкуренция между типами микориз
pH как триггер сукцессии
C/ P соотношение. . .
|
Сукцессия 26. Мат модель создана.
anaschu 12.07.2026
Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .
|
Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста".
Hrethgir 12.07.2026
Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
|