我想创建一个程序，可以生成一系列连续的数字，使它们相加等于给定的数值。例如，如果输入的数值为15，应该得到以下结果 -
7, 8
4, 5, 6
1, 2, 3, 4, 5
有一些公式/算法/循环可以完成某些任务，例如生成数组或打印它。这可能看起来像是一个数学问题或愚蠢的问题，但我实际上无法想象如何在Java中以编程方式完成。
请尝试给出确切的代码来完成这件事。
如何获取所有连续的数字集合，使它们加起来等于一个给定的数字？
6
- v_ag
6
2你尝试了什么？ - Ashishkumar Singh
@AshishSingh 我试图制作一个循环，但我不知道如何使用它... - v_ag
1@VaibhavAgrawal：为什么不让我们看看你的尝试呢？我们应该如何帮助你呢？ - Nikolas Charalambidis
@Nikolas，我并没有尝试过，只是无法想出解决它的算法。我可以自己编写代码，但我需要的只是一个解决该问题的思路或算法。我花了几个小时思考，但最终一无所获！ - v_ag
连续的数字形成等差数列。你知道它们的和吗？ - MBo
@VaibhavAgrawal Dave提供了解决方案的理想逻辑。我已经用Java实现了它。请检查代码并尝试运行它。 - Akhil Surapuram
8个回答
9
假设你的输入为N，你知道每组k个连续数字将围绕N/k居中。如果N/k以0.5结尾，则偶数k存在解决方案，如果N/k是整数，则奇数k存在解决方案。如果有解决方案，则解决方案是围绕N/k居中的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
您可以轻松修改此代码以限制为正数或非负数解。
- Dave
1
请注意，对于有效的k值，您只需要检查N * 2的除数（除了N * 2本身太大和1太简单）。例如，对于N = 15，30的除数为1、2、3、5、6、10、15。 - Dave
6
我将扩展@MBo的答案，因为它提供了一个非常简洁的算法。Wiki提供了关于等差数列的良好介绍，以下是为您复制的内容。
总和
推导
从数字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 == 0nMax = (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());
}
}
- ingen
4
连续数字形成等差数列。如果从数字
如果a是整数（q和n的奇偶性不同），那么对于从a开始且有n个成员的有效序列，配对(a, n)表示该序列。
以S = 15，2S = 30为例：
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
- MBo
3
假设 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]
- Nikolas Charalambidis
4
不错，我喜欢！+1 - Soutzikevich
@Nikolas，您可以优化
sum += i。由于它是一系列连续的数字，因此它形成了一个等差数列。因此，我们只需要找出在该等差数列中有多少个项以获得总和。因此，在 lower 和 upper 之间进行二分查找即可。 - nice_dev@vivek_23：谢谢你的提示。我一直没有寻找最优解，而是从头开始组装了一个天真而有效的解决方案。 - Nikolas Charalambidis
@Nikolas，“list”的大小为1，只有一个数字15，如果输入15，我该怎么办？ - v_ag
2
这里有一个建议：
对于输入的数字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
当连续两个数字的和大于目标值时，您可以进行一些优化，此时可以终止循环，并仅添加最终集合（其中仅包含目标值）。
- Eran
1
我正在编写 @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++;
}
- Akhil Surapuram
1
这里有一个与Eran的解决方案类似的想法。由于我们正在处理连续的数字，累积和（cumsum）通常是有帮助的。基本思路是我们要找到两个累积和之间的差恰好为K，其中K是您示例中的15。
累积和从0开始，所以我们可以进行
下一个任务是创建一个算法，对累积总和进行一些具有不同宽度的滑动窗口。想法是搜索与K的确切值的差异。我们可以从左右窗口指向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
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
- Magdrop
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接