由1、2、5三个数(个数不限)相加等于1000,共有多少种情况?

作者在 2008-10-31 21:18:17 发布以下内容
直觉:
for
(i=0;i<=500;i++)
  for(j=0;j<=200;j++)
    if((i*2+j*5)<=1000)count++;

优化:
一般化一下, 设求的和为n
枚举5的个数就行了
设i个5, 则剩下的n - 5 * i 由2和1组成的种数为floor((n - 5 * i) / 2)
 for (i = 0; i <= 200; i++)
     count+=(1000-5*i)/2+1;
讲讲,3=1+1+1=1+2,2种
4=1+1+1+1=1+1+2=2+2,3种
也就是一数字n由1和2组成共有n/2+1种


zj@zj:~/C_pram/practice/1_100$ cat 1.c
#include<stdio.h>

int
main ()
{
  int i, j;
  int count = 0;
  for (i = 0; i <= 500; i++)
    for (j = 0; j <= 200&&(i*2+j*5<=1000); j++)
    count++;
  printf ("count=%d\n", count);
  return 0;
}
zj@zj:~/C_pram/practice/1_100$ cat 2.c
#include<stdio.h>

int
main ()
{
  int i, j;
  int count = 0;
  for (i = 0; i <= 200; i++)
    count+=(1000-5*i)/2+1;
  printf ("count=%d\n", count);
  return 0;
}

zj@zj:~/C_pram/practice/1_100$ time ./1
count=50401

real    0m0.003s
user    0m0.000s
sys    0m0.004s
zj@zj:~/C_pram/practice/1_100$ time ./2
count=50401

real    0m0.002s
user    0m0.000s
sys    0m0.000s
看看效率还是改进了不少

算法 | 阅读 3589 次
文章评论,共0条
游客请输入验证码
浏览1936561次