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

algorithm for-loop math if-statement java

2022-09-03 04:48:46

我正在经历一个简单的程序，它取一个数字并找到与给定数字匹配的连续数字的出现次数。

例如：

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)这也意味着什么？

请帮助我理解此解决方案。

答案 1

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

如果输入为 15，则总和为 15 的连续数字为：

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

在最坏的情况下，这必须小于第一 n 个自然数的总和 = （n*（n+1） /2。

因此，对于数字15，永远不可能有6个连续数字的组合，这些数字的总和高达15，作为第1个6个数字=21的总和，大于15。

计算温度：这是（j*（j+1））/2。

举个例子。让输入 = 15。设 j =2。

温度 = 2*3/2 = 3;#Meaning 1+2 =3

对于 2 个数字对，让 2 个项为 'a+1' 和 'a+2'。（因为我们知道这些数字是连续的。

现在，根据这个问题，总和必须加起来就是数字。

这意味着2a+3 =15;

如果（15-3）可以被2整除，则可以找到“a”。 -> a+1=7 和 a+2=8a=6

类似地，设 a + 1 + a + 2 + a + 3 = 15 3a + 6 = 15 （15-6）必须可被 3 整除。a+1a+2a+3

最后，对于5个连续的数字,,,, ,我们有5a + 15 = 15;（15-15）必须可被 5 整除。a+1a+2a+3a+4a+5

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

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

总结一下：

1） for 循环从 2 开始，这是什么原因？

我们不担心这里设置的1个数字。

2）这个逻辑意味着什么？这对解决问题有何帮助？long temp = (j * (j + 1)) / 2;

这是因为1st n自然数属性的总和，因为我通过取和作为2个连续数字来解释上述内容。a+1a+2

3）这也意味着什么？if ((num - temp) % j == 0)

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

答案 2

我们需要找到所有的s和s，对于给定的，以下内容是正确的：anb

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