Разложение числа на слагаемые17.08.2011, 12:48. Показов 69102. Ответов 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 | |
|
Разложение на слагаемые разложение на все возможные слагаемые
Разбиение числа на слагаемые Найти все слагаемые заданного числа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Саморегулирующийся социальный контракт для сервера cross-section.
Hrethgir 14.08.2026
С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .
|
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет:
1. Использовать системное время и дату,
2. Есть возможность вводить время и дату вручную.
3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
|
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber.
Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
|
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео:
https:/ / vkvideo. ru/ video-240781534_456239017
YouTube:
eY5-5PyI9NM
Текстовая версия
|
|
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать
Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
|
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства.
Родственных связей существует 8 ступеней, такие как:
p - отец
P - мать
q - муж
Q - жена
b - брат
B - сестра
s - сын
S - дочь
|
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире.
Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
|
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С.
Задача:
Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
|