给定一个数N,生成一个公差为1的等差数列,使得有限元素求和后得到数字N。 例如:
For Example:
N=10
1 + 2 + 3 + 4 =10
N=20
2+3+4+5+6 = 20
N=30
4+5+6+7+8 = 30
N < 1000000
将sum的初始值设为0。
将当前数字设置为1。
将当前数字加到sum中。
如果sum > N
,从被加到sum中的第一个数字开始减去数字,直到sum <= N
。
如果sum = N
,停止(成功)。
增加当前数字。
回到步骤 3。
你只需要记住被加到sum中的第一个数字,在步骤 4 中将其逐一从sum中减去(感谢 Niko)。
作为优化,你还可以使用公式 (n(n+1)/2
) 批量添加数字,而不是一个一个地添加(在N
很大的情况下)。
示例:
N = 30
Sum = 0
Add 1 -> 1
Add 2 -> 3
Add 3 -> 6
Add 4 -> 10
Add 5 -> 15
Add 6 -> 21
Add 7 -> 28
Add 8 -> 36
36 > 30, so:
Subtract 1 -> 35
Subtract 2 -> 33
Subtract 3 -> 30
Done.
log n
操作,那么它就是O(n log n)
。 - Bernhard Barker让T表示数字
所以在第一种情况下,即N=4时,N(N+1)/2 = T
所以在第二种情况下,即N=6且K=1时,N(N+1)/2 - K(K+1)/2 = T
所以在第三种情况下,即N=8且K=3时,N(N+1)/2 - K(K+1)/2 = T
因此,你需要解决基本的N问题,这可以通过乘法和简化得到:
N^2 + N - (2T + K^2 + K) = 0
对于N的二次公式应用如下:
N= (-b + sqrt(b^2 - 4ac))/2a
即可得:
N = (-1 +- sqrt(1 + 8T + 4K^2 + 4K))/2
N必须为正数,我们可以去掉负面的情况
因此,N必须等于
N = (sqrt(8T + (2k+1)^2) - 1)/2
您可以从K=0开始迭代,直到获得一个自然数N为止,这将是您的答案
希望有所帮助,我正在尝试找到更好的方法(感谢这个有趣的问题)
int NumSum(int val)
{
int n = 0, i = 0, j;
while (n != val)
{
n = 0;
j = ++i;
while (n < val)
n += j++;
}
return i;
}
设 N = pq
,其中 p
是一个正奇整数,q
是任意正整数。
(1) 你可以将 N
写成 p
个连续整数的和,且其中 q
是中间值。
(2) 如果 p
和 q
都是奇数(比如说,q = 2k+1
),那么你还可以将 N
写成 2p
个连续整数的和,且其中 k
和 k+1
是中间值。
例如,令 N = 15 = 5 x 3
。
如果我们选择 p=5
,那么按照规则 (1),可以得到 1+2+3+4+5 = 15
。
或者按照规则 (2),也可以得到 (-3)+(-2)+(-1)+0+1+2+3+4+5+6 = 15
。
我们还可以选择 p = 3
,得到 4+5+6 = 15
和 0+1+2+3+4+5 = 15
。
这更像是一个技巧性的方法,我认为它可能有效。
假设数字是10,则从n/2即5开始一个序列。 现在序列不能是
5 + 6,因为10 > 11,所以我们还要向后计算,同时5是我们需要考虑的数字的上限,因为像6 + 7等数字将超过10,所以序列的最后一个(最高)数字将是5。 向后移动5 + 4 = 9 < 10
5 + 4 + 3 = 12 > 10,因此删除第一个元素,有点像队列。
因此,对于20,我们有 start = 20/2 = 10
我猜这是对已接受答案的变体,但仍然认为我可以添加这个作为替代解决方案。
首先,每个奇数都是长度为2的等差数列的和,因为 n = floor(n/2) + ceil(n/2)
。
更有趣的是,一个有奇数因子d的数字是围绕着n/d
的长度为d的等差数列(差为1)的和。例如,30可以被5整除,因此它是围绕6的等差数列之和:30 = 4 + 5 + 6 + 7 + 8
。
没有奇数因子的数字是2的幂。虽然1 = 0 + 1
和2 = -1 + 0 + 1 + 2
,但更大的幂不是任何(非平凡的)等差数列的和。为什么?假设2**m = a + (a+1) + .. + (a+k-1)
。求和系列= k (2a + k-1) / 2
。k必须是奇数或偶数,但任何一种选择都会与总和为2的幂矛盾。
2 = 2
和4 = 4
(即N
可以被视为仅有一个数字的等差数列)。 - Bernhard BarkerN
本身。因此,我认为总和中最大的数字必须小于N
(在这种情况下,并不总是存在解决方案)。或者也许我们正在寻找最长的序列? - Dennis JaheruddinN mod 2 == 1
,那么对于非一数序列,你可以直接返回(n+1)/2, (n-1)/2
。我真的认为我们应该寻找最长的序列。例如,对于N = 15
,我们应该返回[1,2,3,4,5]
还是[7,8]
? - Geobits