l********y
发帖数: 1327 | 1 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
比如：9=4+5 或者9=2+3+4, 但是8就不可以
奇数都可以，但是偶数怎么判断？ |
E********a
发帖数: 124 | 2
这还要“算法”? 所有非2^n的数都可以
【在 l********y 的大作中提到】
: 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以
: 奇数都可以，但是偶数怎么判断？
|
l********y
发帖数: 1327 | |
m******n
发帖数: 1691 | 4 10=1+2+3+4
任何一个数sum，如果 sum/奇数=整数，那么可以；
如果 sum/偶数=整数+0.5，也是可以。
除此以外都不行。
【在 l********y 的大作中提到】
: 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以
: 奇数都可以，但是偶数怎么判断？
|
d*****t
发帖数: 41 | 5 设一个数n是从a开始k个连续正整数的和，有
n = (a+a+k-1)/2*k = (2a+k-1)*k/2
i.e. 2*n = (2a+k-1)*k
不管k是奇是偶，(2a+k-1)*k 都是一个奇数*偶数,所以n不能是2^m |
w***g
发帖数: 5958 | 6 这个牛. 你是对的.
【在 E********a 的大作中提到】
:
: 这还要“算法”? 所有非2^n的数都可以
|
m******n
发帖数: 1691 | 7 你只证明2^m 不可能是k个数相加
没证明非2^m就一定是k个数相加
【在 d*****t 的大作中提到】
: 设一个数n是从a开始k个连续正整数的和，有
: n = (a+a+k-1)/2*k = (2a+k-1)*k/2
: i.e. 2*n = (2a+k-1)*k
: 不管k是奇是偶，(2a+k-1)*k 都是一个奇数*偶数,所以n不能是2^m
|
s*******e
发帖数: 93 | 8 我一开始是想写成这样
for(i=2;i<=n/2;i=i*2)
{
if( n%i == i/2 && n/i-i/2>=1)
return true;
}
for(i=3;i<=n/3;i=i+2)
{
if( n%i == 0 && n/i-(i-1)/2>=1)
return true;
}
return false;
感觉2^m的方法是正解。上面用code的方法不知道能不能帮助证明为什么只要不是2^m就
行？
btw有没有谁可以检查下这个code有无漏洞？ |
D***h
发帖数: 183 | 9 n为奇数，n = (n-1)/2+ (n+1)/2
n为偶数， 已经证明n = 2^s (s>0) 不能
假设 n = 2^s * (2t+1) (s>0, t>0)
n= (1+2+...+m)-(1+2+...+k)
=(m-k)(m+k+1)/2
令 m-k = 2^(s+1)
m+k+1 = 2t+1
可以得到 m = 2^s +t
k = -2^s +t
如果k<0
m+k+1 = 2^(s+1)
m-k = 2t+1
得到m = 2^s+t
k = 2^s-t-1
总是有解。
所以除了2^s以外的所有大于2得数都是可以的.
【在 m******n 的大作中提到】
: 你只证明2^m 不可能是k个数相加
: 没证明非2^m就一定是k个数相加
|
D***h
发帖数: 183 | 10 见我上面的证明
【在 s*******e 的大作中提到】
: 我一开始是想写成这样
: for(i=2;i<=n/2;i=i*2)
: {
: if( n%i == i/2 && n/i-i/2>=1)
: return true;
: }
: for(i=3;i<=n/3;i=i+2)
: {
: if( n%i == 0 && n/i-(i-1)/2>=1)
: return true;
|
