设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和# JobHunting - 待字闺中
l*y
1 楼
设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
比如：9=4+5 或者9=2+3+4, 但是8就不可以
奇数都可以，但是偶数怎么判断？
比如：9=4+5 或者9=2+3+4, 但是8就不可以
奇数都可以，但是偶数怎么判断？
E*a
2 楼
这还要“算法”? 所有非2^n的数都可以
【在 l********y 的大作中提到】
: 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以
: 奇数都可以，但是偶数怎么判断？
l*y
3 楼
why?
m*n
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就不可以
: 奇数都可以，但是偶数怎么判断？
任何一个数sum，如果 sum/奇数=整数，那么可以；
如果 sum/偶数=整数+0.5，也是可以。
除此以外都不行。
【在 l********y 的大作中提到】
: 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 比如：9=4+5 或者9=2+3+4, 但是8就不可以
: 奇数都可以，但是偶数怎么判断？
d*t
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
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
6 楼
这个牛. 你是对的.
【在 E********a 的大作中提到】
:
: 这还要“算法”? 所有非2^n的数都可以
【在 E********a 的大作中提到】
:
: 这还要“算法”? 所有非2^n的数都可以
m*n
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
没证明非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
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有无漏洞？
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
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个数相加
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
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;
【在 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;
相关阅读
trading firm为什么都要c加加？Amazon L5 research scientist 包裹范围？如何复习系统设计？请问有推荐的讨论管理职位之后发展方向的帖子/书么?leetcode比赛排名怎么回事YouTube 公司有枪杀？运气好碰到好老板？？硅谷公司歧视微软全家桶技术吗Re: 高清地图自动驾驶公司HERE Chicago 诚聘 Lead/Senior/Entr4个小时onsite，5个烙印。刷题都没有用这道面试题要是ONSITE这种情况可以直接跟公司提出来吗H1B transfer 终于过了LC 387 怎么优化Google specialized recruiting team 是啥？前女同事经常做好吃的分我，可惜缘分你说如果我搞个付费辅导面试 有客户吗很多公司都签协议3年内不让离职防止跳槽为什么华人在美国的地位如此低下？ (转载)加州真难混