1 Тема від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Тема: Розбиття на доданки.

Недавно на гуртку математики Дезідерій дізнався про розбиття на доданки. Розбиттям числа 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

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Розбиття на доданки.

П. 3.5 Правил бачили?

koala вебсайт

3 Відповідь від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Re: Розбиття на доданки.

koala, вже бачив )), ось напрацювання:

#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);
}

Програма виводить всі варіанти, а як змінити код, щоб програма виводила тільки варіанти відповідно до умови?

4 Відповідь від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Re: Розбиття на доданки.

Гадаю, можливо якось треба запустити рекурсію з доданку +2, щоб кожен наступний доданок був більший попереднього, це для запобігання повторення згідно умови задачі?

Подякували: koala1

5 Відповідь від koala Востаннє редагувалося koala (09.01.2019 22:00:36)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Розбиття на доданки.

Дезідерій - оригінальна людина, якщо вважає 9=9 "цікавим розбиттям".
А вам треба розглядати (яка несподіванка) не всі розбиття, а лише ті, де сусідні елементи не рівні та не різняться рівно на 1. Тобто різняться щонайменше на 2.
(поки я писав, ви додали)

aassii написав:

запустити рекурсію з доданку +2

Абсолютно точно! Я б навіть сказав - не саму рекурсію, а цикл, який викликає рекурсію.

Подякували: leofun011

koala вебсайт

6 Відповідь від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Re: Розбиття на доданки.

for(int cur_slag = summands.empty() ? 1 : summands.back(); n_cur - cur_slag >= 0; ++cur_slag)

Можете підказати як правильно написати код, щоб запустити цикл, який викликає рекурсію з +2?

7 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Розбиття на доданки.

for(int cur_slag = summands.empty() ? 1 : summands.back()    +2    ; n_cur - cur_slag >= 0; ++cur_slag)
Подякували: aassii1

koala вебсайт

8 Відповідь від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Re: Розбиття на доданки.

koala, дякую))