Chinaunix

标题: 出个题：求和为正整数n的连续整数序列 [打印本页]

作者: drakness 时间: 2015-11-06 14:23
标题: 出个题：求和为正整数n的连续整数序列
例如：
18=5+6+7
18=3+4+5+6
输出结果就是:
5 6 7
3 4 5 6

作者: huangxiaohen 时间: 2015-11-06 15:35
本帖最后由 huangxiaohen 于 2015-11-06 16:08 编辑

n = 100
s = range(1, n)
d = [s[i:i+j] for i in range(len(s)) for j in range(1, len(s)-i+1) if sum(s[i:i+j]) == n]
print d

复制代码

作者: drakness 时间: 2015-11-06 15:43
回复 2# huangxiaohen

思路不错，就是执行起来，如果数够大，效率有点低，还能再改进改进吗？

作者: substr函数 时间: 2015-11-06 15:50
[回复]

#!/usr/bin/python2
def N2S(n):
x = n / 2 + 1 + 1
s = [0]
r = []
for i in xrange(1, x): s.append(s[-1] + i)
for i in xrange(1, x):
for j in xrange(i + 1, x):
v = s[j] - s[i - 1]
if v > n: break
if v == n:
r.append(xrange(i, j + 1))
break
for i in r: print list(i)
N2S(100000)

复制代码

作者: huangxiaohen 时间: 2015-11-06 16:19
略屌回复 4# substr函数

作者: substr函数 时间: 2015-11-07 11:42
回复 5# huangxiaohen

[回复] 略能再屌

#!/usr/bin/python2
def N2S(n):
x = n / 2 + 1 + 1
s = [0]
r = []
for i in xrange(1, x): s.append(s[-1] + i)
for i in xrange(1, x):
k = n + s[i - 1]
for j in xrange(i + 1, x):
if s[j] < k: continue
if s[j] == k: r.append(xrange(i, j + 1))
break
for i in r: print list(i)
N2S(100000)

复制代码

作者: drakness 时间: 2015-11-07 12:23
第一次出题，上个，还没搞定指定的打印格式

#!/usr/bin/python
#coding:utf8
#输入一个正数n，输出所有和为n连续正数序列
#例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
import math
def calc(n):
h = int(math.sqrt(2*n))
for k in range(2,h+1):
if((2*n) % k == 0):
t1 = 2 * n - k*k + k
t2 = 2 * n + k*k - k
#print t1,t2
if t1 % (2*k) == 0 and t2 % (2*k) == 0:
s1 = t1 / (2*k)
s2 = t2 / (2*k)
print s1,"-",s2
# for i in range(s1,s2+1):
# print i,
calc(15)

复制代码

作者: drakness 时间: 2015-11-07 12:30
回复 6# substr函数

能在调调最后的输出格式是：
4 5 6
78
这样就更好了

作者: substr函数 时间: 2015-11-07 13:01
回复 8# drakness

print s1,"-",s2

复制代码

print ' '.join(str(s) for s in xrange(s1, s2 + 1))

复制代码

作者: drakness 时间: 2015-11-07 13:02
回复 9# substr函数

膜拜大牛

作者: substr函数 时间: 2015-11-07 13:06
回复 7# drakness

赞一个!
屌 !
这就更略屌了 [

]

作者: substr函数 时间: 2015-11-07 13:16
回复 10# drakness

膜拜大牛 [

]
长见识了!
能说说思路吗？
让小白开开眼界

作者: substr函数 时间: 2015-11-07 14:07
本帖最后由 substr函数于 2015-11-07 16:36 编辑

回复 7# drakness

[回复] 略能再屌 [

]

#!/usr/bin/python2
def calc(n):
N2 = n * 2
h = int(N2**0.5)
for k in xrange(2, h + 1):
if N2 % k: continue
t1 = N2 - k * k + k
t2 = N2 + k * k - k
K2 = k * 2
if t1 % K2 == 0 and t2 % K2 == 0:
s1 = t1 / K2
s2 = t2 / K2
print s1, '-', s2
# print ' '.join(str(s) for s in xrange(s1, s2 + 1))
calc(200000000000000)

复制代码

作者: drakness 时间: 2015-11-09 10:17
回复 12# substr函数

小弟不才，我利用了等差数列求和，及开平方求因子，保证i ， j 均为整数

作者: drakness 时间: 2015-11-09 10:19
回复 13# substr函数

再次膜拜大牛

作者: substr函数 时间: 2015-11-09 13:56
本帖最后由 substr函数于 2015-11-09 14:04 编辑

回复 14# drakness

膜拜大牛 [

]
长见识了! 谢谢大牛的帮助
我的理解

i = (n2 / k - k + 1) / 2.0

def N2S(n):
n2 = n * 2
z = int(n2**0.5)
for k in xrange(z, 1, -1):
if n2 % k: continue
i = (n2 / k - k + 1) / 2.0
if int(i) == i: print int(i), '-', k + int(i) - 1

复制代码

如果 i 为整数
可以保证 j 为整数 ( j = i + k - 1 )

所以可以

def A2(n):
N2 = n * 2
h = int(N2**0.5)
for k in xrange(h, 1, -1):
if N2 % k: continue
T = N2 - k * k + k
K = k * 2
if T % K == 0:
i = T / K
j = i + k - 1
print i, '-', j

复制代码

作者: icymirror 时间: 2015-11-10 13:51
可以比较简单的做到：

def NumberSequence(number):
base = 2
while (number - base * (base + 1) / 2) >= 0 :
if (number - base * (base + 1) / 2) % base == 0:
start = (number - base * (base + 1) / 2) / base
print range(start + 1, start + base + 1)
base += 1

复制代码

基本上，去除等差数列导致的差之和之后，如果可以整除当前的数字个数，那么就可以求得解，不用开方的。
另：为了偷懒，没有把打印部分单独出来，从代码风格来说，反而紧耦合了，不好。

作者: drakness 时间: 2015-11-10 14:20
回复 17# icymirror

学习了

作者: ragkk 时间: 2015-11-10 16:19

#coding:utf-8
'''
题目：输入一个正数n，输出所有和为n连续正数序列
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
'''
n = 100
i = m = 1
results = []
while i <= n/2 + 1 :
results.append(m)
if sum(results) > n :
i += 1
m = i
results = []
elif sum(results) == n :
print results
i += 1
m = i
results = []
else :
m += 1

复制代码

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)