获取总和与给定数字匹配的连续数字

Question

我正在通过一个简单的程序,它接受一个数字并找到与给定数字匹配的连续数字的出现次数.

例如:

if input is 15, then the consecutive numbers that sum upto 15 are:

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

So the answer is 3 as we have 3 possibilities here.

当我在寻找解决方案时,我在下面找到答案:

static long process(long input) {
    long count = 0;
    for (long j = 2; j < input/ 2; j++) {
        long temp = (j * (j + 1)) / 2;
        if (temp > input) {
            break;
        }

        if ((input- temp) % j == 0) {
            count++;
        }
    }
    return count;
}

我无法理解这是如何解决这个问题的,因为这个程序正在使用一些我无法正确理解的公式,下面是我的疑惑:

• for循环从2开始,这是什么原因？
• long temp = (j * (j + 1)) / 2;这个逻辑表明了什么？这对解决问题有什么帮助？
• if ((num - temp) % j == 0) 这又表明了什么？

请帮助我理解这个解决方案.

Answer 1

我将尝试尽可能简单地解释这一点.

如果输入为15,那么总计15的连续数字是:

{1,2,3,4,5} -> 5 numbers
{4,5,6} -> 3 numbers
{7,8} -> 2 numbers

在最坏的情况下,这必须小于第1 n个自然数的和=(n*(n + 1)/ 2).

因此,对于数字15,永远不会有6个连续数字的总和达到15的组合,因为前6个数字的总和= 21,大于15.

计算温度:这是(j*(j + 1))/ 2.

举个例子.设输入= 15.设j = 2.

temp = 2*3/2 = 3; #Meaning 1 + 2 = 3

对于2数字对,让2个项为'a + 1'和'a + 2'.(因为我们知道这些数字是连续的.)

现在,根据这个问题,总和必须加起来.

这意味着 2a+3 =15;

如果(15-3)可以被2整除,则可以找到'a'.a=6 - > a + 1 = 7和a + 2 = 8

类似地,令a+1,a+2和a+3 一个+ 1 + A + 2 + A + 3 = 15 3A + 6 = 15(15-6)必须被3整除.

最后,连续5号a+1,a+2,a+3,a+4,a+5,我们有图5a + 15 = 15; (15-15)必须可被5整除.

因此,当输入为15时,计数将在j = 2,3和5时更改

如果循环从1开始,那么我们也会计算1个数字集 - > {15}这是不需要的

总结一下:

1)for循环从2开始,这是什么原因？

我们并不担心这里设置的1号码.

2)long temp = (j * (j + 1)) / 2;这个逻辑表示什么？这对解决问题有什么帮助？

这是因为我已经通过采用a+1并且a+2作为2个连续数字解释了上述n个自然数属性的总和.

3)if ((num - temp) % j == 0)这又表明了什么？

这表示从第1 j个自然数之和中减去的输入必须可被整除的逻辑j.

Answer 2

我们需要找到所有as 和ns，对于给定的b以下情况为真：

a + (a + 1) + (a + 2) + ... (a + (n - 1)) = b

左边是等差数列，可以写成：

(a + (n - 1) / 2) * n = b         (*)

要找到 n 的极限值，我们知道 ，a > 0因此：

(1 + (n - 1) / 2) * n = n(n + 1) / 2 <= b
n(n + 1) <= 2b
n^2 + n + 1/4 <= 2b + 1/4
(n + 1/2)^2 <= 2b + 1/4
n <= sqrt(2b + 1/4) - 1/2

现在我们可以重写(*)以获得公式a：

a = b / n - (n - 1) / 2

b = 15 且 n = 3 的示例：

15 / 3 - (3 - 1) / 2 = 4 => 4 + 5 + 6 = 15

现在是代码：

double b = 15;
for (double n = 2; n <= Math.ceil(Math.sqrt(2 * b + .25) - .5); n++) {
    double candidate = b / n - (n - 1) / 2;
    if (candidate == (int) candidate) {
        System.out.println("" + candidate + IntStream.range(1, (int) n).mapToObj(i -> " + " + (candidate + i)).reduce((s1, s2) -> s1 + s2).get() + " = " + b);
    }
}

结果是：

7.0 + 8.0 = 15.0
4.0 + 5.0 + 6.0 = 15.0
1.0 + 2.0 + 3.0 + 4.0 + 5.0 = 15.0

Answer 3

我们正在寻找总和等于给定数字的连续数字。很明显，最多可能有一个给定长度的系列，所以基本上我们正在寻找那些可能是这样一个系列的长度的值。变量“j”是测试的长度。它从 2 开始，因为该系列的长度必须至少为 2。变量“temp”是从 1 到“j”的算术级数之和。

如果存在适当的级数，则设 X 为第一个元素。在这种情况下，“输入”= j*(X-1) + 温度。（所以如果 temp> 输入那么我们就完成了）

在最后一行，它检查方程是否存在整数解。如果有，则增加计数器，因为存在一个包含 j 个元素的序列，它是一个解。

实际上这个解是错误的，因为如果 input = 3，它就找不到解。（它会立即终止。）循环应该是：

for(long j=2;;j++)

无论如何，另一个条件会更快地终止循环。