Представить число в виде суммы последовательных слагаемых

#cpp #алгоритм

Есть переменная a,
а может быть любым числом. Допустим a = rand()%10+1;
И надо найти все возможные варианты сложения.
Представить целое число a в виде суммы как минимум двух последовательных натуральных
чисел. 

Например:

10 = 1 + 2 + 3 + 4
24 = 7 + 8 + 9


Помогите найти и придумать алгоритм поиска. Спасибо.
    

Ответы

Ответ 1

Смотрите, всё не так сложно. Это простое диофантово уравнение.

Вспомним формулу суммы арифметической прогрессии (у нас разность d = 1, n — неизвестное
количество слагаемых, a_1 — неизвестное первое слагаемое):

S = n * (2 * a_1 + (n - 1)) / 2


Отсюда 2S делится на n.

Дальше легко найти кандидатуры на n перебором как делители 2S. Например, для S =
10 это будут 2, 4, 5, 10, 20, n = 1 отбрасываем, у нас должно быть больше одного слагаемого.
Для каждого из них находим 2S / n = 2 * a_1 + (n - 1), а потом и a_1 (у нас получится
соответственно 4.5, 1, 0, -3.5, -9). Отбрасываем дробные результаты, и получаем ответы:

1 + 2 + 3 + 4
0 + 1 + 2 + 3 + 4
-9 + -8 + -7 + -6 + -5 + -4 + -3 + -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10


Если нужно только натуральные числа, оставляем только варианты с a_1 > 0, это будет 

1 + 2 + 3 + 4




Асимптотическая сложность: простейшее разложение на множители перебором до корня
O(sqrt(n)), проверка каждого кандидата O(1).


Ответ 2

Вот ещё одно решение. Оно, в сущности, основано на таком же принципе, что и у VladD,
и даже имеет такую же асимптотическую сложность (хотя объяснение этого не тривиально):
O(sqrt(a)).

Поскольку речь о натуральных числах, их легко представить себе по количеству некоторых
предметов. Например, квадратиков. Итак, у нас есть N квадратиков и нам надо из них
выложить фигуру вот такого вида:



Т. е. на треугольник и прямоугольник. Заметим, что общая сумма элементов в подобной
фигуре состоит из треугольного числа и произведения двух натуральных чисел.

Что мы можем наверняка сказать о результате?


a не больше T_t — это даёт условие завершения алгоритма
r целое — это устраняет возможность более чем одного решения для каждого t


Алгоритм построчно описывать не буду, опишу важные части:


Решение будет удовлетворять выражению a = T_t + (t+1)*r
Подберите начальные данные: считаете ли вы 0 натуральным числом? Если нет, то вам
может быть интереснее рассматривать числа от r + 1 до r + t (убрать верхний ряд зелёных
квадратиков). Поскольку вам нужно как минимум два натуральных числа t будет сначала
равно 1, как и T_t (вырожденный треугольник).
Проверяйте, не делится ли a - T_t на t+1. Если делится — найдено решение: это числа
от r = (a - T_t)/(t+1) до r + t.
Каждый шаг алгоритма t увеличивается на 1, а затем T увеличивается на t.
Алгоритм прекращается, как только a становится меньше T_t.


Анализ фигуры для каждого t это O(1): константное число операций. Проводится t раз.
Какое для нашего алгоритма максимальное t? Минимальное из тех, для которых:

a < T_t
a < t^2 / 2 + t/2


T_t растёт квадратично при линейном росте a. Значит, число итераций асимптотически
определяется функцией, обратной t^2 / 2 + t/2, и её асимптотика O(sqrt(a)).
Развлечения ради можете её вывести!


Ответ 3

Код:

bool PrintFragments (unsigned num, unsigned max, unsigned& nTry, unsigned lvl){
   unsigned n = num;
   while (n){
      if (n <= max){
        bool found = false;
        if (n == num && !--nTry)
            found = true;
        else if (PrintFragments (num - n, n, nTry, lvl + 1))
            found = true;
        if (found){
            printf("%d ",n);
        if (!lvl)
            puts("");
        return true;
        }
    }
    --n;
  }
  return false;
}

void PrintNumFragmentsInfo (unsigned num){
  unsigned counter = 0;
  while (1){
    unsigned nTry = counter + 1;
    if (PrintFragments (num, num - 1, nTry,0))
        ++counter;
    else
        break;
  }
  printf("\n количество сумм = %d\n",counter);
}

int main (){
   int n;
   puts("Enter number");
   scanf("%d",&n);
   PrintNumFragmentsInfo (n);
   system("pause");
}