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

@Dani · Регистрация: 11.08.2011

Студворк — интернет-сервис помощи студентам

Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная задача). И мне стало интересно: какой самый быстрый алгоритм разложения числа на слагаемые вы предложите? Думаю, максимальный тест n<=50.
З.Ы. Проверю на время сам. И разложения должны быть без повторений (перестановка слагаемых не дает новых разложений) и чтоб строка слагаемых выводилась в файл "in.txt".

@diagon · 18.08.2011, 11:59

Бывают более оптимальные.
http://acmp.ru/index.asp?main=bstatus&id_t=365
Я на 3м месте там. На первом в три раза быстрее.

@Olga_ · 18.08.2011, 12:02

Сообщение от diagon

Бывают более оптимальные.

Бывают-не бывают, по сравнению с моим вроде оптимальнее, хотя на моем компьютере наоборот, странно

@talis · 18.08.2011, 12:07

diagon, я бы не ориентировался на эту таблицу. Там основным критерием является количество символов кода, что не есть хорошо.

Olga_, ну у вас не самое худшее

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

Сообщение от Olga_

Бывают-не бывают, по сравнению с моим вроде оптимальнее, хотя на моем компьютере наоборот, странно

А что у вас за компилятор, процессор и ОС?

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

Добавлено через 1 минуту
Да и компилятор у них мелкосовтовский

@Olga_ · 18.08.2011, 12:08

Сообщение от talis

А что у вас за компилятор, процессор и ОС?

Да все простое: компиляторы Builder C++ и Visual Studio, процессор Celeron 2800, ОС - Win XP

@diagon · 18.08.2011, 12:10

Сообщение от talis

diagon, я бы не ориентировался на эту таблицу. Там основным критерием является количество символов кода, что не есть хорошо.

Однако это единственно возможный критерий. По другим критериями Java, Basic, c++ отлетают сразу, остаются чистый си и паскаль. А так как время/память вычисляются неточно, то можно пересдать задачу, и она может отработать оптимальнее. Тогда чтобы оказаться в топе, нужно писать прекалк и по сотне раз отправлять одну и ту же задачу...
А пытаясь сжать свой код я многому научился... =)

@Olga_ · 18.08.2011, 12:14

Сообщение от diagon

А пытаясь сжать свой код я многому научился... =)

Пойду учиться, наверное многому еще надо...

@talis · 18.08.2011, 12:17

Сообщение от diagon

А пытаясь сжать свой код я многому научился... =)

Знаете, мне кажется, что это может научить не писать комментарии, использовать неинформативные однобуквенные обозначения типов и переменных, писать труднопонимаемый (хотя и сжатый) код... В общем, если цель - написать как можно короче, то да, это хорошо. А если цель - написать, как можно лучше - то извиняйте, это не то. Например, в некоторых задачах гораздо быстрее было бы считать с использованием SSE, а SSE intrinsics - штука с большим количеством букв.

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

Вот статья и об SSE, и об способностях компиляторов к оптимизации.
http://www.liranuna.com/sse-in... compilers/

@Olga_ · 18.08.2011, 12:52

Это получается, что алгоритму diagona помог компилятор, а при общих равных условиях...

Ну ладно, это шутка (почти

)

@talis · 18.08.2011, 12:56

Olga_, да ладно вам. Ну выучите вы оба ассемблер для 686 и посоревнуйтесь, если так хотите - там вас ничего не спасёт. А вообще, мне кажется, что подобные вещи не должны становиться соревнованием. Давайте лучше учиться друг у друга

@diagon · 18.08.2011, 12:56

Сообщение от Olga_

Это получается, что алгоритму diagona помог компилятор, а при общих равных условиях...
Ну ладно, это шутка (почти)

Не-а, не шутка, так и есть.
Я такого подхода при решении каких-либо задач придерживаюсь - оптимизирую только алгоритм, а реализовываю так, как мне удобно + как можно более просто.
Остальное доделает компилятор...

Сообщение от talis

Машина - дура, но она права.

=)

@Olga_ · 18.08.2011, 13:07

Сообщение от talis

Olga_, да ладно вам...

talis, спасибо за вашу миротворческую миссию, но тут дело не принципе (ни в коем случае!), просто хочется понять как можно больше. Если мой алгоритм плох - сама первая это признаю, просто тут интересный момент оказался - компилятор оптимизирует по-своему, это как в Java - когда сборщик мусора освободит память от объекта - только ему ведомо (и разработчикам)

@talis · 18.08.2011, 13:12

Ну здесь сборщиков мусора нет. А на счёт эффективности алгоритма - посчитайте сами расход памяти и количество операций. Может, действительно окажется, что у вас алгоритм лучше, и вас подвёл компилятор. Скачайте Code::Blocks последний, и проверьте код на нём.

@Prividenie · 23.08.2011, 02:46

я так понимаю время затраченное программой при н=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

@robotcode · 06.12.2018, 01:27

Столкнулся с похожей задачей, только мы должны указать на какие именно номиналы разбивать:

есть общая сумма (например, 5) и номиналы (например, 1,2,3). Общую сумму нужно разбить на всевозможные комбинации по возрастанию
11111
1112
113
122
23

Комбинации не должны повторяться (123=312)
Если не разбивается - сообщение, что разбить нельзя
По умолчанию номиналы не должны повторяться

Может кто-нибудь помочь?

Новичок · 06.12.2018, 23:24

robotcode,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
#include <algorithm>
 
std::vector<int> answer;
std::vector<int> coins{1, 2, 3};
 
void find(int sum, size_t i = 0){ 
    if (sum < 0) return;
    if (sum == 0) {
        for (auto &num: answer) std::cout << num << ' ';
        std::cout << '\n';
        return;
    }
    for (size_t j = i; j < coins.size(); j++) {
        answer.push_back(coins[j]);
        find(sum - coins[j], j);
        answer.pop_back();
    }
    
}
 
int main() {
    std::sort(coins.begin(), coins.end());
    find(5);
}

https://rextester.com/HDTUH18596

Добавлено через 2 минуты

Сообщение от robotcode

Если не разбивается - сообщение, что разбить нельзя

Вот это я забыл. Но легко реализовать: добавили переменную found типа bool, изначально found = false, внутри if (sum == 0) добавляем found = true;

Новые блоги и статьи Все статьи Все блоги /
Знаете, от чего появляется стресс? 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 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .	сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2

	Разложение числа на слагаемые 17.08.2011, 12:48. Показов 69031. Ответов 54 Метки нет (Все метки) Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная задача). И мне стало интересно: какой самый быстрый алгоритм разложения числа на слагаемые вы предложите? Думаю, максимальный тест n<=50. З.Ы. Проверю на время сам. И разложения должны быть без повторений (перестановка слагаемых не дает новых разложений) и чтоб строка слагаемых выводилась в файл "in.txt". 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	18.08.2011, 11:59
	Бывают более оптимальные. http://acmp.ru/index.asp?main=bstatus&id_t=365 Я на 3м месте там. На первом в три раза быстрее. 1

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	18.08.2011, 12:52
	Это получается, что алгоритму diagona помог компилятор, а при общих равных условиях... Ну ладно, это шутка (почти) 0

@talis 794 / 546 / 61 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	18.08.2011, 12:56
	Olga_, да ладно вам. Ну выучите вы оба ассемблер для 686 и посоревнуйтесь, если так хотите - там вас ничего не спасёт. А вообще, мне кажется, что подобные вещи не должны становиться соревнованием. Давайте лучше учиться друг у друга 1

@talis 794 / 546 / 61 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	18.08.2011, 13:12
	Ну здесь сборщиков мусора нет. А на счёт эффективности алгоритма - посчитайте сами расход памяти и количество операций. Может, действительно окажется, что у вас алгоритм лучше, и вас подвёл компилятор. Скачайте Code::Blocks последний, и проверьте код на нём. 0

@Prividenie 74 / 73 / 25 Регистрация: 05.10.2008 Сообщений: 233
	23.08.2011, 02:46
	я так понимаю время затраченное программой при н=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 0

@robotcode 28 / 8 / 6 Регистрация: 20.09.2017 Сообщений: 133
	06.12.2018, 01:27
	Столкнулся с похожей задачей, только мы должны указать на какие именно номиналы разбивать: есть общая сумма (например, 5) и номиналы (например, 1,2,3). Общую сумму нужно разбить на всевозможные комбинации по возрастанию 11111 1112 113 122 23 Комбинации не должны повторяться (123=312) Если не разбивается - сообщение, что разбить нельзя По умолчанию номиналы не должны повторяться Может кто-нибудь помочь? 0