1 2 5三个数相加等于1000，共有多少种情况？要求行数

liuke432

1  2  5三个数相加等于1000，共有多少种情况？
要求行数。

写了一个三行的

for(i=1;i<500;i++)
  for(j=1;j<200;j++)
    if((i*2+j*5)<1000)count++;

面试官说可以两行实现，请各位高手指点指点！

langue

.

for(i=1;i<500;i++) for(j=1;j<200;j++) if((i*2+j*5)<1000) count++;

这是一行的。

.

cugb_cat

原帖由 langue 于 2007-3-23 22:36 发表
.

for(i=1;i<500;i++) for(j=1;j<200;j++) if((i*2+j*5)<1000) count++;

这是一行的。

.

哈哈，是这么回事～～～～
C代码都可以写在一行里的

liuke432

原帖由 langue 于 2007-3-23 22:36 发表
.

for(i=1;i<500;i++) for(j=1;j<200;j++) if((i*2+j*5)<1000) count++;

这是一行的。

.

不是这个意思。  ：）

好像可以再去掉一个for循环

飞灰橙

原帖由 liuke432 于 2007-3-23 22:46 发表


不是这个意思。  ：）

好像可以再去掉一个for循环

for改while, 再去两个都没问题

liuke432

不好意思，我没有表达明白意思。
我的意思其实是要求效率再高一点。

ArXoR

1. 
   
2. 一般化一下, 设求的和为n
   
3. 枚举5的个数就行了
   
4. 设i个5, 则剩下的n - 5 * i 由2和1组成的种数为floor((n - 5 * i) / 2)
   
5. 所求为
   
6. y = sigma{floor((n - 5 * i) / 2), 0 <= i <= floor(n / 2)}.
   
7. 然后按i和n的奇偶性异同分类求和就可以得到close form了, 一个关于n的2次多项式.
   

复制代码

[ 本帖最后由 ArXoR 于 2007-3-25 10:16 编辑 ]

liuke432

原帖由 ArXoR 于 2007-3-24 08:48 发表
一般化一下, 设求的和为n
枚举5的个数就行了
设i个5, 则剩下的n - 5 * j 由2和1组成的种数为floor((n - 5 * j) / 2)
所求为
y = sigma{floor((n - 5 * j) / 2), 0 <= i <= floor(n / 2)}.
然后 ...

恩 明白了   厉害！

这样就可以了

1. 
   
2. 
   
3.       for(i=1;i<200;i++)
   
4.          count+=(1000 - 5i)/2+1;
   
5. 
   

复制代码

[ 本帖最后由 liuke432 于 2007-3-24 19:17 编辑 ]

converse

保留本帖，方便查找。

liuke432

感谢converse版主！    ：）