ProjectEuler做题笔记(第1,2题)

第一题:找出1000内能被3或5整除的所有数的总和。

第一反应是,循环,判断是否能被3或5整除,能的话就加到一个变量中,代码如下:

        static void p1_1()
        {
            int max = 1000;
            int sum = 0;
            for (int i = 1; i < max; i++) 
            {
                if (i % 3==0 || i % 5==0) 
                {
                    sum += i;
                } 
            }
            Console.WriteLine(sum);
        }

接着考虑到%取模运算比较消耗性能,便另想办法。其实就是把3的倍数都加起来,把5的倍数

也都加起来,两者相加再减去15的倍数之和,代码如下:

        static void p1_2()
        {
            int max = 1000;
            int sum = 0;
            for (int i = 3; i < max; i += 3)
            {
                sum += i;
            }
            for (int i = 5; i < max; i += 5)
            {
                sum += i;
            }
            for (int i = 15; i < max; i += 15)
            {
                sum -= i;
            }
            Console.WriteLine(sum);
        }

经测试,当计算1000000内的结果时,方法二比方法一要快将近10倍,数据量越大差距越明显。

当然最逆天的算法是用等差数列求和,3+6+9+。。。。+999+5+10+15+。。。。+995-15-30-....-990

大致浏览了下官方答案和老外的留言,没有特别的解法。

 最后答案是233168

第二题:计算斐波那契数列不超过400万的数中,所有偶数的总和。

斐波那契数列就是1 2 3 5 8 13 21 34 55 89 144。。。。。每项等于前2项之和。

首先想到的是用递推,将值都存到数组中,同时将偶数累加到一个变量,代码如下:

        static void p2_1()
        {
            int sum = 0;
            List<int> list = new List<int>(20000);
            list.Add(1);
            list.Add(2);
            sum += 2;
            while (true)
            {
                //每次将最后两项相加最为新项
            int n = list[list.Count - 1] + list[list.Count - 2];
                //大于400万就跳出死循环
            if (n > 4000000)
                {
                    break;
                }
                list.Add(n);
                //是偶数就累加
            if (n % 2 == 0)
                {
                    sum += n;
                }
            }
            Console.WriteLine(sum);
        }

官方给出的第一种解法没有用数组,只存储最后2项,效率提高不少,代码如下:

        static void p2_2()
        {
            int sum = 0;
            int a = 1, b = 2;
            sum += 2;
            while (b<4000000)
            {
                int c = a + b;
                a = b;
                b = c;
                if (c % 2 == 0) 
                {
                    sum += c;
                }
            }
            Console.WriteLine(sum);
        }

同事提出的一种算法是:观察该数列可以得到

1    2   3    5    8   13 21 34 55 89 144

奇   偶  奇   奇   偶   奇 奇  偶  奇  奇  偶

除了1与2,后面的数都是奇奇偶,这不难证明,因为奇+偶=奇,奇+奇+偶

于是3以后的所有偶数之和等于3以后所有数(最后一个数也要是偶数)之和除以2

比如:8+34+144=(3+5+8+13+21+34+55+89+144)/2

结合方法2,可以省掉循环中取模的操作,提高一点效率,代码如下:

        static void p2_3()
        {
            int sum = 0;
            int a = 1, b = 2;
            while (b < 4000000)
            {
                int c = a + b;
                a = b;
                b = c;
                sum += c;
            }
            //最后2个数如果是奇数,要去掉
            if (a % 2 == 1) 
            {
                sum -= a;
            }
            if (b % 2 == 1)
            {
                sum -= b;
            }
            //除以2以后还要加上最开始被跳过去的2
            sum = sum / 2 + 2;
            Console.WriteLine(sum);
        }

通过方法3,知道了奇奇偶奇奇偶的规律,我们把所有偶数看成一个新的数列,找找它的递推公式。

2  8  34  144.。。分别是原数列的第1  4   7   10项(从0开始算),

记原数列为A(n),    A(n)=A(n-1)+A(n-2)

那么新数列B(n)=A(3n+1)=A(3n)+A(3n-1)=A(3n-1)+A(3n-2)+A(3n-2)+A(3n-3)=

A(3n-2)+A(3n-3)+2A(3n-2)+A(3n-4)+A(3n-5)=

3A(3n-2)+A(3n-3)+A(3n-4)+A(3n-5)=

4A(3n-2)+A(3n-5)=

4A(3(n-1)+1)+A(3(n-2)+1)=

4B(n-1)+B(n-2)

公式出来了,接下来就是循环相加了,代码如下:

        static void p2_4()
        {
            int sum = 0;
            int a = 2, b = 8;
            sum = a;
            while (b < 4000000)
            {
                sum += b;
                int c = 4 * b + a;
                a = b;
                b = c;
            }
            Console.WriteLine(sum);
        }

当然斐波那契数列有通项公式,这个数列当然也能算出通项公式,最后算出求和公式,这是最逆天的做法了。

通项公式解法如下:

B(n)=4B(n-1)+B(n-2)

算了半小时才算出来,快算疯了!!!!!求和公式实在不知道怎么算了,不算了!!

这道题最后答案是4613732

我的网站:http://i.goto327.top:85/
原文地址:https://www.cnblogs.com/jintianhu/p/1936478.html