设计一个算法，判断一个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;
相关阅读
昨天onsite 之后HR没消息了是不是可以考虑move on了求教140批了以后多久可以离职Biostatistician opening西雅图是一座怎样的城市！穆斯林难民云集的庇护城市！ (转载)任大炮明目张胆清理35岁的后果 (转载)phd quit的话不转master是不是就黑了？H1B还剩一年半跳槽办卡来得及吗？Snap 市值$30bn 了uber 最近发生的可以拍成电影了。大公司招人普遍看不起小公司出来的吗？Turn was acquired招一名Financial Analyst 实习生一名任正非：华为没有退休金 大家如果不奋斗就垮了zt (转载)求指点ic layout转CAD过了google hiring committee 却没拿offer现在uber内部的女生什么状态？其实魏天冰是给华人长脸的uber那白牛张得很大众啊 (转载)跪求amazon new grad team match我同学在成都华为，刚给他打电话，结果他说。。。 (转载)