[Project Euler] 来做欧拉项目练习题吧: 题目001

时间:2023-02-22 22:16:17

                            [Project Euler] 欧拉项目练习题001

                                                周银辉 

 

关于Project Euler的一点介绍: 

哈哈,两个月没更新博客了,因为跑去做Project Euler上的练习题了,非常非常乐意向大家推荐这个网站:http://projecteuler.net/  上面有很多题,由浅入深,基本上是由数学与计算机程序相结合来解决问题,非常有意思。另外建议大家在编程时选用C语言,以及尽量不要用库函数(malloc之类少数函数还是必须得使用的)以更好地提高自己的编程能力。当然肯定会有同学会提ACM之类的,恩,萝卜白菜各有所爱啦,反正我更爱Project Euler. 还有就是要持之以恒,我看了下,有十多万注册,但从level 0(没有级别)到level 1就只有20%人的坚持下来,更不要说level 6啦,不过还是很多大牛到达了这个级别,并且也不乏中国红旗哈,很值得骄傲。

 

第一题:

描述:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000. 

(先思考,如果有兴趣先编程试试,然后才看下面的内容) 

 

分析: 

由于是第一题,所以非常简单,我稍稍分析一下

我们可以看看不超过20的数中3,5的倍数列表:3, 5, 6, 9, 10, 12, 15, 18, 20

很明显其可以撤成两类 3, 6, 9, 12, 15, 18 和 5, 10, 15, 20

他们分别是以3为首项3为等差的等差数列 以及 以5为首项5为等差的等差数列。或者理解成3的倍数的数列,以及5的倍数的数列。

哦,原来题目要求是两个等差数列求和,然后再将两个和相加。如果用S(n)表示由n的倍数构成的数列元素之和的话,那么前面的分析就可以写成S = S(3) + S(5)

同时我们会发现两个数列有重叠,因为3的倍数的数列和5的倍数的数列必然重叠上15的倍数的数列,也就是说 15,30, 45...  会被加两遍。

那么我们在S中减去被重复累加的就可以了,所以最终公式可以写成 S = S(3) + S(5) - S(15) 

此时,其实我们在草稿纸上就能得出答案了,但如要写成代码的话,参考下面:

 

参考代码

#include <stdio.h>
int s(int a1, int d, int max)
{
int N  = max/d;
int an = a1 + (N-1)*d;
return (a1+an)*N/2;
}
int main()
{
int n = 999; //1000-1
int i;
i = s(3, 3, n) + s(5, 5, n) - s(15, 15, n);
printf("%d\n",i);     
return 0;

 

不要写成下面的代码,那有点没动脑筋和浪费计算机资源的表现 

int test(int n)
{
int i;
int sum = 0;
for(i=1; i<=n; i++)
{
      if(i%3==0 || i%5==0)
      {
        sum += i;
       }
}

 

return sum;
}

 

扩展:
提一个可以采用相同解法的题目: 从元年开始到第N年(比如1998)时共经过了多少天?

 

注:当完成题目后,对于某些题,官方网站会给出参考答案,在我的博客里不会将官方答案贴出来,仅仅会写下我自己当时的思路,除非两者不谋而合。另外,如果你有更好的思路,请留言告诉我,我非常乐意参与到讨论中来。