С Новым годом! Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.86/29: Рейтинг темы: голосов - 29, средняя оценка - 4.86
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
1

Разложение числа на неповторяющиеся слагаемые

16.12.2014, 23:08. Показов 5899. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Собственно, задача сказана. Вот код для количества:
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
27
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
int main() {
    int n, count = 0;
    cin >> n;
    stack<pair<int, int> > st;
    st.push(make_pair(1, 1));
    while(!st.empty()) {
        if(st.top().first < n) {
            int i = st.top().second;
            st.push(make_pair(st.top().first+i+1, i+1));
        } else {
            if(st.top().first == n) {
                count ++;
            }
            st.pop();
            if(!st.empty()) {
                st.top().first++;
                st.top().second++;
            }
        }
    }
    cout << count << endl;
    return 0;
}
А вот для вывода
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
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
int main() {
    int n;
    cin >> n;
    stack<pair<int, int> > st;
    st.push(make_pair(1, 1));
    while(!st.empty()) {
        if(st.top().first < n) {
            int i = st.top().second;
            st.push(make_pair(st.top().first+i+1, i+1));
        } else {
            if(st.top().first == n) {
                // печатать
                stack<pair<int, int> > st1;
                while(!st.empty()) {
                    st1.push(st.top());
                    st.pop();
                }
                while(!st1.empty()) {
                    cout << st1.top().second << ' ';
                    st.push(st1.top());
                    st1.pop();
                }
                cout << endl;
            }
            st.pop();
            if(!st.empty()) {
                st.top().first++;
                st.top().second++;
            }
        }
    }
    return 0;
}
Не могу понять принцип работы. Просто за счет какого свойства, функции алгоритм является рабочим? 2-ой день сижу, не понимаю. Читал Липиского(http://rutracker.org/forum/viewtopic.php?t=1088760), не понял. Очень круто будет, если объясните на школьном языке.
0
IT_Exp
Эксперт
8794 / 1073 / 104
Регистрация: 17.06.2006
Сообщений: 12,602
Блог
16.12.2014, 23:08
Ответы с готовыми решениями:

Разложение числа на слагаемые
Здравствуйте, товарищи форумчане! Нужна помощь в доработке программы. #include &lt;stdio.h&gt; ...

Разложение числа на слагаемые
Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная...

Разложение числа на слагаемые
Не могу найти найти не рекурсивный алгоритм разложения числа на заданное кол-во слагаемых. Может у...

Разложение числа на слагаемые.
На входе у нас число (нат, пол) которое нужно разложить и ожидаймое количество слагаймых алгоритм...

7
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,197
18.12.2014, 11:21 2
Цитата Сообщение от Domonion Посмотреть сообщение
Не могу понять принцип работы. Просто за счет какого свойства, функции алгоритм является рабочим? 2-ой день сижу, не понимаю
Что хотите разобраться хорошо, но по коду (тем более без всяких примечаний) это непросто.

В стеке содержатся пары, у каждой first - текущая сумма, и second - последнее слагаемое. Как только это (структура данных) ясна, дальше все проще. Пока сумма меньше заданной - просто добавляем новую пару, second растет на 1 и сумма соответственно. Сумма равна заданной - фиксируем рез-т (count++). Переход к след варианту - последнее удаляем (pop), а предпоследнее как бы "забываем", наращивая последнюю пару. Напр слагаемые были 1, 2, 3. 4, стали 1, 2, 4, т.е. опять пытаемся но уже без тройки.
0
834 / 642 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
18.12.2014, 12:55 3
Чего бы просто рекурсию с ленивой динамикой не сделать?

Добавлено через 16 секунд
И что выводится-то?
0
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
18.12.2014, 19:54  [ТС] 4
Цитата Сообщение от Qwertiy Посмотреть сообщение
Чего бы просто рекурсию с ленивой динамикой не сделать?
Как? Рекурсию понятно, куда пихать ленивку? И как это вообще должно выглядеть?
Цитата Сообщение от Qwertiy Посмотреть сообщение
И что выводится-то?
количество комбинаций и сами комбинации.
Цитата Сообщение от Igor3D Посмотреть сообщение
Что хотите разобраться хорошо, но по коду (тем более без всяких примечаний) это непросто.
В стеке содержатся пары, у каждой first - текущая сумма, и second - последнее слагаемое. Как только это (структура данных) ясна, дальше все проще. Пока сумма меньше заданной - просто добавляем новую пару, second растет на 1 и сумма соответственно. Сумма равна заданной - фиксируем рез-т (count++). Переход к след варианту - последнее удаляем (pop), а предпоследнее как бы "забываем", наращивая последнюю пару. Напр слагаемые были 1, 2, 3. 4, стали 1, 2, 4, т.е. опять пытаемся но уже без тройки.
Спасибо. А Асимптотика тут какая? Я затрудняюсь с ее подсчетом. Уж как-то слишком странно.

Добавлено через 5 минут
Извините, до ленивки с рекурсией допер. Код предоставите?

Добавлено через 7 минут
Нет, не предоставляйте. Я сам выложу, хочу поломаться. С асимптотикой лучше помогите, у меня проблемы с ее подсчетом. Там квадрат чтоль получается?
0
834 / 642 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
18.12.2014, 20:48 5
Цитата Сообщение от Domonion Посмотреть сообщение
С асимптотикой лучше помогите
Ассимптотика посчсёта числа комбинаций - квадрат или куб - до меня сейчас дошло, что то, про что я думал изначально, немнонго неверно. Тем не менее, идея с ленивой данамикой, либо с динамикой с обновлением впрерёд (надо понять, какая в данном случае удобнее) остаётся в силе. На вскидку приходит в голову кубический вариант (квадрат состояний и n переходов), но есть стойкое подозрение, что эта оценка неверна, либо алгоритм может быть оптимизирован.

Цитата Сообщение от Domonion Посмотреть сообщение
сами комбинации
Что касается вывода всех комбинаций - если он действительно нужен, то имеет смысл просто делать перебор и с динамикой не муддрить. Т. е. обычный рекурсивный алгоритм, который выводит всё что требуется и считает количество.
0
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,197
19.12.2014, 09:47 6
Цитата Сообщение от Qwertiy Посмотреть сообщение
Т. е. обычный рекурсивный алгоритм, который выводит всё что требуется и считает количество.
Так он фактически и предъявлен, только рекурсия заменена стеком, что более грамотно. Технически было проще использовать std::vector (вместо std::stack), тогда не пришлось бы городить 2 варианта.

2Qwertiy Ваши любознательность/упорство "заслуживают лучшего применения". Но увидев задачу посерьезнее - Вы убегаете
0
834 / 642 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
19.12.2014, 23:18 7
Цитата Сообщение от Igor3D Посмотреть сообщение
Ваши любознательность/упорство "заслуживают лучшего применения". Но увидев задачу посерьезнее - Вы убегаете
Я всё ещё тут
А код не читал, что должно ясно следовать из вопроса "И что выводится-то?"

Добавлено через 12 часов 55 минут
Цитата Сообщение от Igor3D Посмотреть сообщение
Но увидев задачу посерьезнее - Вы убегаете
Вот код (ассимптотика - куб):
VB.NET
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
27
Module All
  Private Function Solve(N As Integer) As Integer
    Dim Ways(N, N) As Integer, Res As Integer = 0
 
    Ways(0, 0) = 1
    For S As Integer = 0 To N ' Текущая сумма
      For Q As Integer = 0 To S ' Последнее использованное слагаемое (максимальное)
        For W As Integer = Q + 1 To N - S ' Добавляемое слагаемое
          Ways(S + W, W) += Ways(S, Q)
        Next W
      Next Q
    Next S
 
    For S As Integer = 0 To N
      Res += Ways(N, S)
    Next S
 
    Return Res
  End Function
 
  Public Sub Main()
    For N As Integer = 1 To 128
      Console.WriteLine("{0,3} {1}", N, Solve(N))
    Next N
    Console.ReadKey()
  End Sub
End Module
Результат:
Код
  1 1
  2 1
  3 2
  4 2
  5 3
  6 4
  7 5
  8 6
  9 8
 10 10
 11 12
 12 15
 13 18
 14 22
 15 27
 16 32
 17 38
 18 46
 19 54
 20 64
 21 76
 22 89
 23 104
 24 122
 25 142
 26 165
 27 192
 28 222
 29 256
 30 296
 31 340
 32 390
 33 448
 34 512
 35 585
 36 668
 37 760
 38 864
 39 982
 40 1113
 41 1260
 42 1426
 43 1610
 44 1816
 45 2048
 46 2304
 47 2590
 48 2910
 49 3264
 50 3658
 51 4097
 52 4582
 53 5120
 54 5718
 55 6378
 56 7108
 57 7917
 58 8808
 59 9792
 60 10880
 61 12076
 62 13394
 63 14848
 64 16444
 65 18200
 66 20132
 67 22250
 68 24576
 69 27130
 70 29927
 71 32992
 72 36352
 73 40026
 74 44046
 75 48446
 76 53250
 77 58499
 78 64234
 79 70488
 80 77312
 81 84756
 82 92864
 83 101698
 84 111322
 85 121792
 86 133184
 87 145578
 88 159046
 89 173682
 90 189586
 91 206848
 92 225585
 93 245920
 94 267968
 95 291874
 96 317788
 97 345856
 98 376256
 99 409174
100 444793
101 483330
102 525016
103 570078
104 618784
105 671418
106 728260
107 789640
108 855906
109 927406
110 1004544
111 1087744
112 1177438
113 1274118
114 1378304
115 1490528
116 1611388
117 1741521
118 1881578
119 2032290
120 2194432
121 2368800
122 2556284
123 2757826
124 2974400
125 3207086
126 3457027
127 3725410
128 4013544
0
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,197
20.12.2014, 08:38 8
Цитата Сообщение от Igor3D Посмотреть сообщение
Но увидев задачу посерьезнее - Вы убегаете
Вы поняли с точностью до наоборот Ну зачем Вы тратите время/силы на очередную комбинаторную задачу? Конечно дело Ваше, но ведь ясно что дальше олимпиады это никуда не пойдет, чисто "зарядка для хвоста". А ведь есть задачи где Ваше умение было бы куда больше к месту (и совсем не безвозмездно). Но они у Вас почему-то интереса не вызывают
0
20.12.2014, 08:38
BasicMan
Эксперт
19315 / 2622 / 84
Регистрация: 17.02.2009
Сообщений: 10,364
Блог
20.12.2014, 08:38
Помогаю со студенческими работами здесь

Разложение числа на слагаемые [рекурсия]
Привет! Пишу программу разложения числа на слогаемые, но опять хочу попросить помощи - не...

Разложение натурального числа на слагаемые
Я не силен в математике, но математику надоело вести математические методы и он начал давать...

Разложение натурального положительного числа на слагаемые?
Помогите... Нужно разложить число на слагаемые... Причем, условия такие: слагаемые должны быть в...

НЕ Рекурсивное разложение числа на слагаемые. Алгоритм Эрлиха
У меня возникла задача разложения числа на слагаемые из этой задачи:...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Блоги программистов
Обновление сайта www.historian.b­y
Reglage 05.01.2025
Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .
Как использовать GraphQL в C# с HotChocolate
Programming 05.01.2025
GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .
Модель полного двоичного суматора с помощью логических операций (python)
AlexSky-coder 04.01.2025
def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()
Это мы не проходили, это нам не задавали...(аси­­хронный счётчик с управляющим сигналом задержки).
Hrethgir 04.01.2025
Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .
Руководство по созданию бота для Телеграм на Python
IT_Exp 04.01.2025
Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .
Применение компонентов PrimeVue в Vue.js 3 на TypeScript
BasicMan 04.01.2025
Введение в PrimeVue и настройка окружения PrimeVue представляет собой мощную библиотеку компонентов пользовательского интерфейса для Vue. js 3, которая предоставляет разработчикам богатый набор. . .
Как стать Senior developer
cpp_developer 04.01.2025
В современной индустрии разработки программного обеспечения позиция Senior Developer представляет собой не просто следующую ступень карьерной лестницы, а качественно новый уровень профессионального. . .
Что известно о дате выхода Windows 12 и чего от нее ждать
IT_Exp 04.01.2025
В мире технологий постоянно происходят изменения, и операционные системы не являются исключением. Windows 11, выпущенная в октябре 2021 года, принесла множество инноваций и улучшений, но. . .
Что новенького в .NET Core 9
Programming 04.01.2025
Обзор ключевых изменений в . NET Core 9 Платформа . NET Core продолжает активно развиваться, и версия 9 представляет собой значительный шаг вперед в эволюции этой технологии. Новый релиз. . .
Инструкция по установке python3.13.1 в Debian 12
AlexSky-coder 03.01.2025
sudo apt update sudo apt install build-essential zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libreadline-dev libffi-dev wget. . .
Затестил триггеры. архив проекта прилагаю с GOA файлами в настройках архиватора проектов.
Hrethgir 03.01.2025
В этот раз нет закольцованности, потому что от неё только глюки, как я понял, логика не вырезанная. Триггеры очень быстрые если верить измерениям с помощью анализатора от Gowin. Есть ещё регистры,. . .
Python в помощь DevOps
IT_Exp 03.01.2025
Причины использования Python в работе DevOps Python стал неотъемлемой частью мира DevOps, и это не случайно. Этот язык программирования обладает множеством преимуществ, которые делают его. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru