Представить число N в виде слагаемых, где разница между двумя числами между -1 и 1

Question

На вход подается число N и К;

необходимо вывести все возможные сочетания N в виде слагаемых, но разница между последующими числами не более единицы;

кол-во слагаемых - K;

пример:

>> 2 4
-1+0+1+2
0+0+1+1
0+1+0+1
0+1+1+0
1+0+0+1
1+0+1+0
1+1+0+0
2+1+0-1

я думал насчет рекурсии, подобной ниже, но не смог реализовать..

Answer 1

На каждом шаге запускаем ветвления вниз, на месте и вверх от текущего значения.

Как найти начальные значения? Да по формуле суммы арифметической прогрессии

N = k * (2*a1 + d * (k-1)) / 2

Взяв d = +1, найдём минимальный начальный член для возрастающей прогрессии, сумма k членов которой может достигнуть N. Аналогично для d = -1 и убывающей.

Ideone

#include <iostream>
#include <string>

void  composition(int n, int k, int last, std::string s) {
    if (k == 0) {
        if (n == 0)
            std::cout << s << std::endl;
        return;
    }
    composition(n - last + 1, k - 1, last - 1, s + ' ' + std::to_string(last - 1));
    composition(n - last, k - 1, last, s + ' ' + std::to_string(last));
    composition(n - last - 1, k - 1, last + 1, s + ' ' + std::to_string(last + 1));
}

int main()
{
    int n = 2;
    int k = 4;
    for (int l = (2 * n -  k * (k - 1)) / (2 * k); 
             l <= (2 * n + k * (k - 1) + 2 * k - 1) / (2 * k); l++)
        composition(n - l, k - 1, l, std::to_string(l));
}

Кроме того, для оптимизации можно проверять аналогичные условия внутри функции composition, чтобы не генерировать заведомо тупиковые ветви.

БЛОГ НА HUSL

Представить число N в виде слагаемых, где разница между двумя числами между -1 и 1

Ответы (1 шт):