作者在 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
看看效率还是改进了不少