Форум программистов, компьютерный форум CyberForum.ru

Разложение числа на слагаемые - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 148, средняя оценка - 4.86
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 12:48     Разложение числа на слагаемые #1
Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная задача). И мне стало интересно: какой самый быстрый алгоритм разложения числа на слагаемые вы предложите? Думаю, максимальный тест n<=50.
З.Ы. Проверю на время сам. И разложения должны быть без повторений (перестановка слагаемых не дает новых разложений) и чтоб строка слагаемых выводилась в файл "in.txt".
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.08.2011, 12:48     Разложение числа на слагаемые
Посмотрите здесь:

C++ Разложение числа
C++ Разложение на слагаемые
Разложение числа C++
Разложение натурального положительного числа на слагаемые? C++
C++ Разложение числа на цифры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:59     Разложение числа на слагаемые #41
Бывают более оптимальные.
http://********/index.asp?main=bstatus&id_t=365
Я на 3м месте там. На первом в три раза быстрее.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 12:02     Разложение числа на слагаемые #42
Цитата Сообщение от diagon Посмотреть сообщение
Бывают более оптимальные.
Бывают-не бывают, по сравнению с моим вроде оптимальнее, хотя на моем компьютере наоборот, странно
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 12:07     Разложение числа на слагаемые #43
diagon, я бы не ориентировался на эту таблицу. Там основным критерием является количество символов кода, что не есть хорошо.

Olga_, ну у вас не самое худшее . Моя первая мысль вообще была создать кэш сумм всех цифр от 2 до n - 1, а затем его обходить и, при необходимости, этим же кэшем пользуясь, выводить слагаемые слагаемого. Но потом, правда, сообразил, что обход его будет дольше, чем простое вычитание, так что пришёл к чему-то вроде варианта diagon.

Цитата Сообщение от Olga_ Посмотреть сообщение
Бывают-не бывают, по сравнению с моим вроде оптимальнее, хотя на моем компьютере наоборот, странно
А что у вас за компилятор, процессор и ОС?

Добавлено через 2 минуты
diagon, и, если бы у них была не винда, может по памяти вы бы и вперёд вырвались - кто знает?

Добавлено через 1 минуту
Да и компилятор у них мелкосовтовский
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 12:08     Разложение числа на слагаемые #44
Цитата Сообщение от talis Посмотреть сообщение
А что у вас за компилятор, процессор и ОС?
Да все простое: компиляторы Builder C++ и Visual Studio, процессор Celeron 2800, ОС - Win XP
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 12:10     Разложение числа на слагаемые #45
Цитата Сообщение от talis Посмотреть сообщение
diagon, я бы не ориентировался на эту таблицу. Там основным критерием является количество символов кода, что не есть хорошо.
Однако это единственно возможный критерий. По другим критериями Java, Basic, c++ отлетают сразу, остаются чистый си и паскаль. А так как время/память вычисляются неточно, то можно пересдать задачу, и она может отработать оптимальнее. Тогда чтобы оказаться в топе, нужно писать прекалк и по сотне раз отправлять одну и ту же задачу...
А пытаясь сжать свой код я многому научился... =)
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 12:14     Разложение числа на слагаемые #46
Цитата Сообщение от diagon Посмотреть сообщение
А пытаясь сжать свой код я многому научился... =)
Пойду учиться, наверное многому еще надо...
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 12:17     Разложение числа на слагаемые #47
Цитата Сообщение от diagon Посмотреть сообщение
А пытаясь сжать свой код я многому научился... =)
Знаете, мне кажется, что это может научить не писать комментарии, использовать неинформативные однобуквенные обозначения типов и переменных, писать труднопонимаемый (хотя и сжатый) код... В общем, если цель - написать как можно короче, то да, это хорошо. А если цель - написать, как можно лучше - то извиняйте, это не то. Например, в некоторых задачах гораздо быстрее было бы считать с использованием SSE, а SSE intrinsics - штука с большим количеством букв.

Не знаю на счёт борландовских компиляторов, но майкросовотовский известен своей тугостью в оптимизации. И, основываясь на личном опыте, могу предположить, что реализация библиотеки C++ у него гораздо медленне реализации библиотеки C. А борландовские у вас, скорее всего, старые, Builder - 2002 или 2003 года. Компиляторы с тех пор сильно развились.

Вот статья и об SSE, и об способностях компиляторов к оптимизации.
http://www.liranuna.com/sse-intrinsi...lar-compilers/
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 12:52     Разложение числа на слагаемые #48
Это получается, что алгоритму diagona помог компилятор, а при общих равных условиях...
Ну ладно, это шутка (почти)
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 12:56     Разложение числа на слагаемые #49
Olga_, да ладно вам. Ну выучите вы оба ассемблер для 686 и посоревнуйтесь, если так хотите - там вас ничего не спасёт. А вообще, мне кажется, что подобные вещи не должны становиться соревнованием. Давайте лучше учиться друг у друга
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 12:56     Разложение числа на слагаемые #50
Цитата Сообщение от Olga_ Посмотреть сообщение
Это получается, что алгоритму diagona помог компилятор, а при общих равных условиях...
Ну ладно, это шутка (почти)
Не-а, не шутка, так и есть.
Я такого подхода при решении каких-либо задач придерживаюсь - оптимизирую только алгоритм, а реализовываю так, как мне удобно + как можно более просто.
Остальное доделает компилятор...

Цитата Сообщение от talis Посмотреть сообщение
Машина - дура, но она права.
=)
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 13:07     Разложение числа на слагаемые #51
Цитата Сообщение от talis Посмотреть сообщение
Olga_, да ладно вам...
talis, спасибо за вашу миротворческую миссию, но тут дело не принципе (ни в коем случае!), просто хочется понять как можно больше. Если мой алгоритм плох - сама первая это признаю, просто тут интересный момент оказался - компилятор оптимизирует по-своему, это как в Java - когда сборщик мусора освободит память от объекта - только ему ведомо (и разработчикам)
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 13:12     Разложение числа на слагаемые #52
Ну здесь сборщиков мусора нет. А на счёт эффективности алгоритма - посчитайте сами расход памяти и количество операций. Может, действительно окажется, что у вас алгоритм лучше, и вас подвёл компилятор. Скачайте Code::Blocks последний, и проверьте код на нём.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2011, 02:46     Разложение числа на слагаемые
Еще ссылки по теме:

C++ разложение на все возможные слагаемые
C++ разложение числа
C++ Подсчитать количество различных разбиений числа N на натуральные слагаемые

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Prividenie
74 / 74 / 6
Регистрация: 05.10.2008
Сообщений: 233
23.08.2011, 02:46     Разложение числа на слагаемые #53
я так понимаю время затраченное программой при н=50 тестировалось выше
скопировал код Ольги:
закомментировал:
//printf("n = ");
//scanf("%ld", &n);
присвоил:
long n = 50;

получил:
time ./a.out

real 0m0.350s
user 0m0.332s
sys 0m0.016s

и файл:
OUTPUT.TXT размером 6047041 b.

Добавлено через 2 минуты
GCC 4.4.5
OS: Debian 6
CPU Athlon II X4 630

Добавлено через 13 минут
соответственно код с 2 ответа:
закоментил/прописал:
//std::cin >> n;
n=50;
отправил выхлоп в /dev/null
time ./diagon > /dev/null

real 0m0.324s
user 0m0.324s
sys 0m0.000s
Yandex
Объявления
23.08.2011, 02:46     Разложение числа на слагаемые
Ответ Создать тему
Опции темы

Текущее время: 04:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru