Вывести все "интересные" разбиения числа на слагаемые

@aassii · Регистрация: 12.10.2018

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

Недавно на кружке математики Дезидерий узнал о разбиении на слагаемые.
Разбивкой числа n на слагаемые называется представление его в виде суммы неубывающая набора натуральных чисел. Например, 9 = 1 + 2 + 2 + 4 является разбивкой числа 9 на слагаемые.
Дезидерий называет разбиение интересным, если никакие два слагаемых в наборе не равны и не различаются ровно на 1. Так, например, разбиения, приведенное выше не является интересным, а разбиение 9 = 1 + 3 + 5 - интересное.
Помогите Дезидерию вывести все интересные разбиение числа n на слагаемые.

Входные данные:
На ввод подается одно целое число n (1 ≤ n ≤ 80).

Исходные данные:
Выведите все интересные разбиение числа n на слагаемые. Разбивку можно выводить в произвольном порядке. Следуйте формату.

Пример:
stdin
9

stdout
9=1+3+5
9=1+8
9=2+7
9=3+6
9=9

Алгоритм решения:

Кликните здесь для просмотра всего текста

Напишем функцию rek(vector <int> ans, int p, int sum),
в которой vector <int> ans - вектор собраных поточных слагаемых,
int p - последнее добавленное слагаемое,
int sum - собранная поточная сумма.
Делаем рекурсивную функцию:
- если собранная сумма sum>n, то выходим: if (sum>n) return;
- добавляем последнее слагаемое в вектор ans: ans.push_back(p);
- если sum==n то выводим собранный набор слагаемых: if (sum==0) {out(ans); return;}
- запускаем рекурсию со слагаемого p+2, чтоб каждое последующее слагаемое было больше за предыдущее, это чтоб небыло повторения согласно условия задания:
for (long long i=p+2; i<=n-sum; i++) rek(ans,i,sum+i);

Желательно написать программу без использования векторов (и без динамики). (использовать массивы и рекурсию можно)

Байт · 09.01.2019, 19:55

Дезидерий, сам не пытался чего-нибудь сделать сделать? Алгоритм-то есть. И на первый взгляд - хороший.

@aassii · 09.01.2019, 20:38 **[ТС]**

Байт, Дезидерий, векторы не учил еще но алгоритм нашел.))

Вот что, Дезидерий, пытался написать: ))

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
using namespace std;
int n;
void  rek(vector <int> ans, int p, int sum)
{
    if (sum>n) return;
    ans.push_back(p);
    if (sum==0) {out(ans); return;}
}
int main()
{
    cin>>n;
    vector <int> ans;
    long long sum=0, p=0;
    for (long long i=p+2; i<=n-sum; i++) rek(ans,i,sum+i);
    cout<<endl;
    return 0;
}

Байт · 09.01.2019, 20:59

aassii, Ага! Векторов, значит, не хочется...А к чему тама они - ума не приложу. Можно с обычными массивами работать...
И рекурсии в творении уважаемого Дезидерий, нигде не вижу. А может и не нужна она...
Однако, было дело. Решали уже эту задачку на форуме. Правда, без такого смешного условия

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

никакие два слагаемых в наборе не равны и не различаются ровно на 1.

Коее только упрощает задачу (сокращает перебор)
Сейчас ни писать, ни искать неохота. Будет светлый момент - попробую.
Конечно, надо так построить все, чтобы числа двигались в одном направлении. Убывали или возрастали. Мне больше нравится, чтобы убывали. Но это симметрично, и дело вкуса и метафоры.

@aassii · 09.01.2019, 22:36 **[ТС]**

Сообщение от Байт

И рекурсии в творении уважаемого Дезидерий, нигде не вижу. А может и не нужна она...

Дезидерий еще не додумался до рекурсии.)) Но задание надо сделать с использованием рекурсии. (на худой вариант - хоть както сделать)

Добавлено через 1 час 16 минут

Сообщение от Байт

Сейчас ни писать, ни искать неохота. Будет светлый момент - попробую.

Первый светлый момент: вот задачка, но она выводит все варианты, а нужно только отдельные варианты согласно условию. Как учесть условие?

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<int>  T_summands;
 
void  print_summands (int n_start, const T_summands& summands)
{
    cout << n_start << "=";
    for(T_summands::const_iterator  summands_it = summands.begin(); summands_it != summands.end(); ++summands_it)
    {
        cout << *summands_it << (summands_it != summands.end() - 1 ? "+" : "\n");
    }
}
 
void  summands_partition (int n_start, int n_cur, const T_summands&  summands)
{
    if(!n_cur) {print_summands(n_start, summands);}
    for(int cur_slag = summands.empty() ? 1 : summands.back(); n_cur - cur_slag >= 0; ++cur_slag)
    {
        T_summands  summands_new(summands);
        summands_new.push_back(cur_slag);
        summands_partition(n_start, n_cur - cur_slag, summands_new);
    }
}
 
int main()
{
    int  n = 0;
    cin >> n;
    T_summands  summands;
    summands_partition(n, n, summands);
}

@ReDoX · 09.01.2019, 23:01

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

Как учесть условие?

Если время выполнения не принципиально, то можно просто в лоб: создать set<vector<int>> в котором будут все разбиения, а потом подогнать под условие, пройдясь по всем

Байт · 09.01.2019, 23:06

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

просто в лоб

Тут дело в том, что в такой трактовке задачка становится совершенно никому не интересной...

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

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

Первый светлый момент:

Дык, но опять же вектора. А вы с приятелем их не любите...

@aassii · 09.01.2019, 23:20 **[ТС]**

Сообщение от Байт

Дык, но опять же вектора. А вы с приятелем их не любите...

А вот это темный момент((, можно както вектор переделать на обычный массив?

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

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

Если время выполнения не принципиально

Time limit: 1 s
Чтоб вложится во время нужно както использовать приведенный мною алгоритм решения, но он на вектора ((.

Байт · 09.01.2019, 23:40

aassii, я вам предлагаю о предложении ReDoX вообще не задумываться.

Добавлено через 3 минуты
aassii, там все в самом деле не очень сложно. Можно и рекурсией, можно и без. И без векторов. Я как-бы уже вижу решение. Но в код пока не складывается. Вечер уже. Да и гости совсем недавно ушли...

@ReDoX · 10.01.2019, 00:24

Сообщение от Байт

aassii, я вам предлагаю о предложении ReDoX вообще не задумываться.

Не по теме:

с TL в 1с я бы тоже о нем не задумывался)

@aassii · 10.01.2019, 01:12 **[ТС]**

Второй светлый момент: условие учтено и задача в векторах решена))

Кликните здесь для просмотра всего текста

C++
1
int cur_slag = summands.empty() ? 1 : summands.back() + 2;

Вот если бы ее переделать без использования векторов, то будет день!

@ReDoX · 10.01.2019, 01:32

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

Вот если бы ее переделать без использования векторов, то будет день!

Напишите полный код с исправлениями, а там можно подумать

@aassii · 10.01.2019, 01:49 **[ТС]**

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<int>  T_summands;
 
void  print_summands (int n_start, const T_summands& summands)
{
    cout << n_start << "=";
    for(T_summands::const_iterator  summands_it = summands.begin(); summands_it != summands.end(); ++summands_it)
    {
        cout << *summands_it << (summands_it != summands.end() - 1 ? "+" : "\n");
    }
}
 
void  summands_partition (int n_start, int n_cur, const T_summands&  summands)
{
    if(!n_cur) {print_summands(n_start, summands);}
    for(int cur_slag = summands.empty() ? 1 : summands.back() + 2; n_cur - cur_slag >= 0; ++cur_slag)
    {
        T_summands  summands_new(summands);
        summands_new.push_back(cur_slag);
        summands_partition(n_start, n_cur - cur_slag, summands_new);
    }
}
 
int main()
{
    int  n = 0;
    cin >> n;
    T_summands  summands;
    summands_partition(n, n, summands);
}

@ReDoX · 10.01.2019, 02:17

За правильность не ручаюсь, но на девятке работает:

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
38
39
40
#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<int>  T_summands;
 
void  print_summands(int n_start, int* a, int n) {
  cout << n_start << "=";
 
  for (int i = 0; i < n; ++i)
    cout << a[i] << (i == n - 1 ? '\n' : '+');
}
 
void  summands_partition(int n_start, int n_cur, int* a, int n, int cur) {
  if (!n_cur)
    print_summands(n_start, a, n);
 
  for (int cur_slag = (n == 0 ? 1 : a[cur] + 2); n_cur - cur_slag >= 0; ++cur_slag) {
    int b[100];
 
    int b_cur = 0;
    int size = 0;
 
    for (int i = 0; i < n; ++i, ++size)
      b[b_cur++] = a[i];
    
    b[b_cur] = cur_slag;
    ++size;
 
    summands_partition(n_start, n_cur - cur_slag, b, size, b_cur);
  }
}
 
int main() {
  int  n = 0;
  cin >> n;
  int* a = new int[100];
 
  summands_partition(n, n, a, 0, 0);
}

@aassii · 10.01.2019, 23:13 **[ТС]**

ReDoX, Спасибо большое, но

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

Желательно написать программу без использования векторов (и без динамики). (использовать массивы и рекурсию можно)

@ReDoX · 10.01.2019, 23:18

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

ReDoX, Спасибо большое, но

смешная шутка? замените на статику и результат на изменится

@aassii · 10.01.2019, 23:34 **[ТС]**

Так и сделал)) Спасибо.

@TechnoRat · 11.01.2019, 00:10

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

typedef vector<int> T_summands;

Извиняюсь за оффтоп, но не ткнёте ли носом меня в туториалы, гайды или книги, в которых научают вот такому именованию типов? Не в первой вижу на форуме такой лайфхак, но у самого пока не приходит в голову как его корректно применять. Или это лишь с опытом придёт?

@aassii · 11.01.2019, 00:35 **[ТС]**

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

Извиняюсь за оффтоп, но не ткнёте ли носом меня в туториалы, гайды или книги, в которых научают вот такому именованию типов? Не в первой вижу на форуме такой лайфхак, но у самого пока не приходит в голову как его корректно применять. Или это лишь с опытом придёт?

В даном примере эту строку просто надо удалить.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240

	Вывести все "интересные" разбиения числа на слагаемые 09.01.2019, 18:58. Показов 4862. Ответов 18 Метки нет (Все метки) Недавно на кружке математики Дезидерий узнал о разбиении на слагаемые. Разбивкой числа n на слагаемые называется представление его в виде суммы неубывающая набора натуральных чисел. Например, 9 = 1 + 2 + 2 + 4 является разбивкой числа 9 на слагаемые. Дезидерий называет разбиение интересным, если никакие два слагаемых в наборе не равны и не различаются ровно на 1. Так, например, разбиения, приведенное выше не является интересным, а разбиение 9 = 1 + 3 + 5 - интересное. Помогите Дезидерию вывести все интересные разбиение числа n на слагаемые. Входные данные: На ввод подается одно целое число n (1 ≤ n ≤ 80). Исходные данные: Выведите все интересные разбиение числа n на слагаемые. Разбивку можно выводить в произвольном порядке. Следуйте формату. Пример: stdin 9 stdout 9=1+3+5 9=1+8 9=2+7 9=3+6 9=9 Алгоритм решения: Кликните здесь для просмотра всего текста Напишем функцию rek(vector <int> ans, int p, int sum), в которой vector <int> ans - вектор собраных поточных слагаемых, int p - последнее добавленное слагаемое, int sum - собранная поточная сумма. Делаем рекурсивную функцию: - если собранная сумма sum>n, то выходим: if (sum>n) return; - добавляем последнее слагаемое в вектор ans: ans.push_back(p); - если sum==n то выводим собранный набор слагаемых: if (sum==0) {out(ans); return;} - запускаем рекурсию со слагаемого p+2, чтоб каждое последующее слагаемое было больше за предыдущее, это чтоб небыло повторения согласно условия задания: for (long long i=p+2; i<=n-sum; i++) rek(ans,i,sum+i); Желательно написать программу без использования векторов (и без динамики). (использовать массивы и рекурсию можно) 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	09.01.2019, 19:55
	Дезидерий, сам не пытался чего-нибудь сделать сделать? Алгоритм-то есть. И на первый взгляд - хороший. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	09.01.2019, 23:40
	aassii, я вам предлагаю о предложении ReDoX вообще не задумываться. Добавлено через 3 минуты aassii, там все в самом деле не очень сложно. Можно и рекурсией, можно и без. И без векторов. Я как-бы уже вижу решение. Но в код пока не складывается. Вечер уже. Да и гости совсем недавно ушли... 0

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	10.01.2019, 23:34 [ТС]
	Так и сделал)) Спасибо. 0

Вывести все "интересные" разбиения числа на слагаемые

Решение