Как получить все наборы последовательных чисел, которые в сумме образуют число?

Вот предложение:

Для входного числа N:

• вам нужно рассматривать только числа от 1 до N.
• вы можете поддерживать интервал, который представляет текущее подмножество [1, ..., N]. Сохраните сумму текущего интервала. Первый интервал будет [1,1], а его сумма равна 1.
• Пока сумма <N, увеличивайте правый конец интервала на единицу (например, вы начинаете с интервала [1,1]. Поскольку 1 <N, вы расширяете его до [1,2].
• Если сумма текущего интервала равна N, вы добавляете этот интервал к выходным данным, удаляете левый конец интервала (также удаляя его из текущей суммы) и продолжаете.
• Если сумма превышает N, вы также удаляете левый конец интервала (также удаляя его из текущей суммы) и продолжаете.
• Вы закончите, когда интервал станет [N, N] (это последний интервал, который вы должны добавить к выходным данным).

Для входа 15 интервал будет меняться со временем следующим образом:

Interval        Sum

[1]             1
[1,2]           3
[1,2,3]         6
[1,2,3,4]       10
[1,2,3,4,5]     15 -> output [1,2,3,4,5]
[2,3,4,5]       14
[2,3,4,5,6]     20
[3,4,5,6]       18
[4,5,6]         15 -> output [4,5,6]
[5,6]           11
[5,6,7]         18
[6,7]           13
[6,7,8]         21
[7,8]           15 -> output [7,8]
[8]             8
[8,9]           17
[9]             9
[9,10]          19
[10]
...
[15]            15 -> output 15

Вы, вероятно, сможете провести некоторую оптимизацию, как только сумма двух последовательных чисел станет выше целевой суммы, после чего вы можете завершить цикл и просто добавить окончательный набор (который содержит только целевую сумму).

Считайте, что int input - это ваш входной номер (например, 15), а List<int[]> list - как хранилище последовательных чисел результата, вот вам:

List<int[]> list = new ArrayList<>();                          

int lower = 1;                               // Start searching from 1
int upper = (int) Math.floor(input + 1 / 2); // Up to the half of input (8+9 > 15)
while (lower < upper) {                      // Iterate between the bounds
    int sum = 0;
    for (int i = lower; i <= upper; i++) {   // Iterate and sum the numbers
        sum += i;
        if (sum == input) {                  // If it matches the input
                                             // Add the range to the List
                                             // You have to loop them by one and add to the
                                             // List before version Java-8
            list.add(IntStream
                         .range(lower, i + 1)
                         .toArray());
            break;                           // Found, no reason to continue 
        }
        if (sum > input) {                   // Terminate the loop if the sum overlaps
            break;
        }
    lower++;                                 // Increment and try the sums from 
                                             // a higher starting number
    sum = 0;                                 // Reset the sum
}

Результатом для входного 15 является List этих массивов:

[1, 2, 3, 4, 5]
[4, 5, 6]
[7, 8]

Он использовал Window Sliding Technique/Algorithm. Вы также можете погуглить sliding window algorithm sum.

Скажем, ваш ввод - N. Вы знаете, что каждый набор из k последовательных чисел будет сосредоточен вокруг N / k. Решение существует для четного k, если N / k заканчивается на 0,5, и для нечетного k, если N / k является целым числом. Решение, если оно существует, - это k целых чисел с центром вокруг N / k.

k=1: 15/1 = 15, so 15 (trivial; may want to omit)
k=2: 15/2 = 7.5, so 7,8
k=3: 15/3 = 5, so 4,5,6
k=4: 15/4 = 3.75, so no solution
k=5: 15/5 = 3, so 1,2,3,4,5
k=6: 15/6 = 2.5, so 0,1,2,3,4,5 
etc...
k=15: 15/15 = 1, so -6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8

Вы можете легко изменить это, чтобы ограничиться положительными или неотрицательными решениями.

Последовательные числа образуют арифметическую прогрессию. Если он начинается с номера a и имеет членов n, его сумма равна

S = n * (2 * b + (n-1)) / 2
so
P = 2 * S = n * (2 * b + (n-1))

Таким образом, для данного ввода S мы можем разложить 2*S на все возможные пары целочисленных множителей P = n * q, где n<=q, а затем получить начальный номер

a = (q - n + 1) / 2

Если a - целое число (нечетность q и n отличается), то пара (a, n) представляет действительную последовательность, начиная с a с членами n.

Пример для S = 15, 2S = 30:

30 = 2 * 15 => n = 2, a = 7  => (7,8)
30 = 3 * 10 => n = 3, a = 4  => (4,5,6)
30 = 5 * 6 =>  n = 5, a = 1  => (1,2,3,4,5)

Простой пример Python:

import math
def getseqs(s):
    print(s)
    p = 2 * s
    for n in range(2, math.ceil(math.sqrt(p))):
        if (p % n == 0):
            q = p // n
            if (((q - n) & 1) == 1):  #compare parity
                a = (q - n + 1) // 2
                seq = list(range(a, a+n))
                print(seq, sum(seq))

getseqs(17)
getseqs(15)
getseqs(72)

17
[8, 9] 17
15
[7, 8] 15
[4, 5, 6] 15
[1, 2, 3, 4, 5] 15
72
[23, 24, 25] 72
[4, 5, 6, 7, 8, 9, 10, 11, 12] 72

Пишу Реализация решения @Dave. Попробуйте решить, прежде чем спрашивать ... Вот как мы учимся. (только если мы не можем получить, тогда спросите)

    Scanner s = new Scanner(System.in);
    int inputNumber = s.nextInt();
    int k = 1;
    while(inputNumber/k >= .5){
        Float sequenceMid = (float) inputNumber/k;

        if ( k%2 == 0 && (sequenceMid *2 == Math.ceil(sequenceMid *2)) ){
            for(int i = ((int)Math.floor(sequenceMid) - (k/2)),count=0 ; count < k ; count++,i++ ){
                System.out.print(i + " ");
            }
            System.out.println();
        }else if ( (k%2 == 1) && (sequenceMid == Math.ceil(sequenceMid))){
            for(int i = (Math.round(sequenceMid) - ((k-1)/2)),count=0 ; count < k ; count++,i++ ){
                System.out.print(i + " ");
            }
            System.out.println();
        }
        k++;
    }

Я расширю ответ @ MBo, поскольку он передает очень чистый алгоритм. Вики представляет собой хорошее введение в арифметические прогрессии, скопированное ниже для вашего удобства.

Сумма

Вывод

Сумма последовательности, начинающейся с номера a и состоящей из последовательных номеров n:

S = (n / 2) * [2 * a + (n-1) * d]

Для последовательных номеров шаг d равен 1.

S = (n / 2) * [2 * a + (n-1)]

Здесь мы можем перейти к сообщению @ MBo.

P = 2 * S = n * [2 * a + (n-1)]

Мы можем перебрать все возможные подсчеты последовательных чисел n и проверить, действителен ли полученный a (то есть a является целым числом).

Давайте исключим a.

Скажем, P = n * q => q = 2 * a + (n-1) => 2 * a = q - n + 1 => a = (q - n + 1) / 2

Фильтры

1) мы упоминали, что можем перебрать все возможные подсчеты последовательных чисел n, но, учитывая p = n * q, можно с уверенностью сказать, что n должен быть делителем p.

• p % n == 0
• nMax = (int)Math.sqrt(p)

2) a - целое число, а a = (q - n + 1) / 2 => (q - n + 1) - четное => q - n - нечетное.

• ((q - n) & 1) == 1

Выполнение

import java.util.*;
import java.lang.Math;
import java.util.stream.IntStream;
import static java.util.stream.Collectors.toList;

public class Progressions
{
    public static void main(String[] args)
    {
        List<List<Integer>> list = Calculate(15);
        System.out.print(list);
    }

    public static List<List<Integer>> Calculate(int s)
    {
        List<List<Integer>> list = new ArrayList<>();
        int p = 2*s;
        int nMax = (int)Math.sqrt(p);
        for (int n=2; n<=nMax; n++) {
            if (p % n == 0) {
                int q = p / n;
                if (((q - n) & 1) == 1) {          
                    int a = (q - n + 1) / 2;
                    list.add(range(a,n));
                }
            }
        }
        return list;
    }

    public static List<Integer> range(int a, int n) {
        return IntStream.range(a, a+n)
            .boxed()
            .collect(toList());
    }
}

Вот идея, аналогичная решению Эрана.

Поскольку мы имеем дело с последовательными числами, обычно может помочь накопительная сумма (cumsum). Основная идея состоит в том, что мы хотим найти разницу между двумя совокупными суммами, которая дает точно K, где K в вашем примере равно 15.

number:    1, 2, 3,  4,  5,  6,  7,  8,  9, 10
cumsum: 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55

differences:
15 - 0  = 15 -> [1, 2, 3, 4]
21 - 6  = 15 -> [4, 5, 6]
36 - 21 = 15 -> [7, 8]

Кумулятивная сумма начинается с 0, поэтому мы можем выполнить вычитание 15 - 0. Число, включенное в качестве решения, будет исключающим слева и включающим вправо. Это просто означает прибавление 1 к левому индексу (индекс начинается с 0). Надеюсь, картина достаточно ясна.

Следующая задача - создать алгоритм, который будет выполнять какое-то скользящее окно различной ширины по совокупной сумме. Идея состоит в том, чтобы найти разницу с точным значением K. Мы можем начать с начала, когда левая и правая сторона окна указывают на 0. Хотя разница - это <= K, мы хотим увеличить правую часть окна. , увеличивая окно и разницу.

number:     1, 2, 3,  4,  5,  6,  7,  8,  9, 10
cumsum:  0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55
   1st: (]       -> 0 - 0 = 0
   2nd: (---]    -> 3 - 0 = 3
   3rd: (------] -> 6 - 0 = 0

Как только алгоритм достигнет 15, он распечатает первый ответ, а затем увеличит его еще раз. Однако, как только у нас есть разница > K, мы хотим увеличить левое число, уменьшив разницу.

number:     1, 2, 3,  4,  5,  6,  7,  8,  9, 10
cumsum:  0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55
   1st: (-----------------]     -> 15 - 0 = 15 <print>
   2nd: (---------------------] -> 21 - 0 = 21
   3rd:     (-----------------] -> 21 - 1 = 20

Обратите внимание, что левая часть ограничена < K/2, начиная с K//2 + (K//2 + 1) >= K (где равенство возможно благодаря целочисленному делению, обозначенному //). Таким образом, мы можем остановить цикл раньше, когда левая сторона достигнет K//2 (из-за исключения слева).

public static int cumsum(int index) {
    return index * (index + 1) / 2;
}

public static String printRange(int left, int right) {
    StringBuilder buffer = new StringBuilder();
    buffer.append('[');
    for (int i=left+1;i<=right;i++) {
        buffer.append(i);
        buffer.append(',');
    }
    buffer.deleteCharAt(buffer.length()-1);
    buffer.append(']');
    return buffer.toString();
}

public static void main(String[] args) {
    int K = 15;

    int K_ov_2 = K/2;
    int left_index = 0;
    int right_index = 0;
    int diff;
    while (left_index < K_ov_2) {
        diff = cumsum(right_index) - cumsum(left_index);
        System.out.println("diff = " + diff + ", left = " + left_index + ", right = " + right_index);
        if (diff == K) {
            System.out.println(printRange(left_index,right_index));
        }

        if (diff <= K) {
            right_index++;
        } else {
            left_index++;
        }

    }

}

Я добавил строку отладки, чтобы вывод стал более очевидным.

diff = 0, left = 0, right = 0
diff = 1, left = 0, right = 1
diff = 3, left = 0, right = 2
diff = 6, left = 0, right = 3
diff = 10, left = 0, right = 4
diff = 15, left = 0, right = 5
[1,2,3,4,5]
diff = 21, left = 0, right = 6
diff = 20, left = 1, right = 6
diff = 18, left = 2, right = 6
diff = 15, left = 3, right = 6
[4,5,6]
diff = 22, left = 3, right = 7
diff = 18, left = 4, right = 7
diff = 13, left = 5, right = 7
diff = 21, left = 5, right = 8
diff = 15, left = 6, right = 8
[7,8]
diff = 24, left = 6, right = 9