1 | |
Разложение числа на слагаемые17.08.2011, 12:48. Показов 65164. Ответов 54
Метки нет (Все метки)
Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная задача). И мне стало интересно: какой самый быстрый алгоритм разложения числа на слагаемые вы предложите? Думаю, максимальный тест n<=50.
З.Ы. Проверю на время сам. И разложения должны быть без повторений (перестановка слагаемых не дает новых разложений) и чтоб строка слагаемых выводилась в файл "in.txt".
0
|
17.08.2011, 12:48 | |
Ответы с готовыми решениями:
54
Разложение натурального числа на слагаемые Разложение натурального положительного числа на слагаемые? Разложение на слагаемые Разложение на слагаемые |
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||||||
18.08.2011, 10:44 | 21 | |||||
Странно, а у меня его программа 2500 миллисекунд работает, а моя 1200 А вы так тестируете?
0
|
18.08.2011, 10:47 | 22 |
Olga_, Dani, на время тестирования отключайтесь от инета и отключайте антивирус. У меня с ним время выполнения прыгает на 1000мс в каждую сторону, без него - разброс порядка 300мс.
Добавлено через 44 секунды Да, и на винде консоль тормознутая, не выводите на неё.
0
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
18.08.2011, 10:49 | 23 |
0
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
18.08.2011, 10:52 | 25 |
Так вы же написали, что у diagona быстрее? Хотя, по коду и времени, нет
Я просто хочу привлечь ваше внимание к тому, что алгоритм получился очень экономичным и быстрым
0
|
18.08.2011, 10:56 | 26 | |||||
Вот доказательство тормознутости вывода
А варианты сейчас прогоню у себя и отпишусь
1
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||||||
18.08.2011, 11:03 | 27 | |||||
Сообщение было отмечено как решение
Решение
Тот же самый алгоритм на С++:
1
|
Higher
|
|
18.08.2011, 11:05 | 28 |
А в чем разница-то? =)
Сменить язык, немного изменить условия - получится то же самое. Даже аргументы функций практически совпадают. P.S. clock'ом неточно измерять, погрешность у него высокая. Попробую у себя более точно time'ом замерить.
0
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
18.08.2011, 11:07 | 29 |
Меньше условий После смены языка - пост 27. И все же алгоритмы немного разные и написаны независимо
0
|
Higher
|
||||||
18.08.2011, 11:11 | 30 | |||||
Но это все-таки погрешность, ибо разницы в коде практически нету. Причем с ключем -O3, что странно, обе программы медленнее работают..
1
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
18.08.2011, 11:15 | 31 |
Diagon, я не хвалю свой алгоритм, просто хочу понять почему так... Почему ваш у вас быстрее, а мой - у меня, чудо какое-то...
1
|
Higher
|
|
18.08.2011, 11:22 | 32 |
Так если бы эксперты =)
Результат будет зависеть от компилятора(gcc оба кода отлично соптимизировал, а какой-нибудь VC вообще повиснет при компиляции), загруженности системы, расположения звезд на небе... По поводу отсечения - алгоритмы одинаковые, разная реализация. У вас она более оптимальная, а у меня более понятная и больше простора оптимизирующему компилятору =)
0
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
18.08.2011, 11:26 | 33 |
Да, вы правы, от всего зависит. А еще от системы зависит - запись/чтения в файл.
0
|
18.08.2011, 11:35 | 34 |
Я не эксперт, но вот, прогнал Сишный вариант Ольги, первый вариант 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 | 35 |
0
|
Higher
|
|
18.08.2011, 11:42 | 37 |
xDDDDD
Это как вообще? А разница банально в оптимизации.. Только результат действительно нереалистичный какой-то, даже если компилировать с ключами на максимальную оптимизацию.
0
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
18.08.2011, 11:44 | 38 |
Странно, очень странно Но спасибо за тест
Добавлено через 1 минуту Присоединяюсь
0
|
18.08.2011, 11:53 | 39 | |||||
Да никаких ключей не было, даже на целевой процессор. Просто вам с Ольгой нужно просчитать 6 метров вывода, а ему - 50 килобайт
Добавлено через 8 минут Не по теме: У всех было 502 bad gateway..? Вот код Юры, который я компилировал. Сами смотрите:
0
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
18.08.2011, 11:57 | 40 |
Тогда этот вариант сразу отпадает, нужны все разбиения числа на слагаемые.
Придется признать, что у diagon оптимальнее вариант
1
|
18.08.2011, 11:57 | |
18.08.2011, 11:57 | |
Помогаю со студенческими работами здесь
40
разложение на все возможные слагаемые Разбиение числа на слагаемые Разбиение числа на слагаемые Найти все слагаемые заданного числа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |