【每天进步一点点】Python解题笔记（02篇）

jerryxjr1220

今天我们继续来看“欧拉计划”的第2题，求斐波那契数列中不超过400万的偶数的和。

这题初看起来，用穷举法应该是很容易求解的，斐波那契数列的通项公式：f(n) = f(n-1)+f(n-2), f(0)=1, f(1)=1

所以可以很简单的用递归写成：

def fib(n):
    return fib(n-1)+fib(n-2) if n>1 else 1

不过其实递归的效率是很低的，因为每次调用fib函数，程序都要先去计算一下fib(n-1)和fib(n-2)，这样就会造成非常多的重复计算，导致效率变低。

我们可以用循环来改善递归中效率过低的问题。

def fib(n):
    a, b = 1, 1
    for i in range(n):
        a, b = a+b, a
    return b

其实，如果我们搜一下，可以发现斐波那契数列是有通项计算公式的：F(n)=(1/5**0.5)*(((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n)

这样，其实可以直接列式计算，比循环的效率更高，这里就不例举了。

有了斐波那契的公式，计算就自然很方便了。对了，题目还要求我们求所有偶数的和，那是不是我们需要对每一项都要进行奇偶判断？

其实是不必要的，我来看看斐波那契数列的规律，1,2,3,5,8,13,21,34...

有没有发现它是按照“奇，偶，奇，奇，偶，奇，奇，偶，奇，奇，偶..."这样的方式排列的。也就是说所有的偶数项都是出现在第2、5、8、11...这样的公差为3的项数上，我们只需要按照这个规律提取并计算就可以了。

def euler2(n):
        a, b = 1, 1
        res = []
        while b<n:
                res.append(b)
                a, b = a+b, a
        return sum(res[2::3])

同样一道题目有不同的解题方法，这就是算法的奥秘，你感觉到了吗？

最后，耍个宝，一行python代码输出：

print(sum([int((lambda n: (1/5**0.5)*(((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n))(i)) for i in range(3,1000,3) if (lambda n: (1/5**0.5)*(((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n))(i)<4000000]))

新手·ing

jerryxjr1220

新手·ing 发表于 2017-8-18 12:13

不要光冒汗啊，真要想提高，你应该在我每个解题的帖子下写下你自己的解答程序，自己要多动手做才能有提高。

如果有不清楚的，可以回帖留言，我会尽可能帮你解答。

新手·ing

jerryxjr1220 发表于 2017-8-18 12:54
不要光冒汗啊，真要想提高，你应该在我每个解题的帖子下写下你自己的解答程序，自己要多动手做才能有提高 ...

大神啊，我不是不做，是真做不出来啊

hanfeng

学习学习，支持！

发现一个小漏洞，还没想到好方法，先简单加了个if语句：
def euler2(n):
        a, b = 1, 1
        res = [1]
        while b<n:
                a, b = a+b, a
                if b < n:
                    res.append(b)
        return sum(res[2::3])

jerryxjr1220

hanfeng 发表于 2017-8-18 15:47
学习学习，支持！

发现一个小漏洞，还没想到好方法，先简单加了个if语句：

为什么还要加if？
while 后面的条件不是已经有了吗？

可以把append（）语句和 a, b = a+b, a换一下位置，如果你怕b=a以后b会超过n的话。

def euler2(n):
        a, b = 1, 1
        res = []
        while b<n:
                res.append(b)
                a, b = a+b, a
        return sum(res[2::3])

hanfeng

jerryxjr1220 发表于 2017-8-18 15:51
为什么还要加if？
while 后面的条件不是已经有了吗？

我试了一下，res列表最后一位数会大于设定的条件，如果是计算小与100的偶数和时，会把144也算进去。

jerryxjr1220

hanfeng 发表于 2017-8-18 15:56
我试了一下，res列表最后一位数会大于设定的条件，如果是计算小与100的偶数和时，会把144也算进去。

如果你发现多一位的话，你可以把最后一句改成return sum(res[2:-1:3]) 去掉最后1位

hanfeng

jerryxjr1220 发表于 2017-8-18 15:59
如果你发现多一位的话，你可以把最后一句改成return sum(res[2:-1:3]) 去掉最后1位

额额，这么简单的竟然木有想到...

jerryxjr1220

新手·ing 发表于 2017-8-18 15:07
大神啊，我不是不做，是真做不出来啊

不要说你不会计算斐波那契数列哦，你怎么对得起小甲鱼老师，你怎么对得起苍老师，你怎么对得起那么多ooxx的小兔子？

新手·ing

jerryxjr1220 发表于 2017-8-18 16:04
不要说你不会计算斐波那契数列哦，你怎么对得起小甲鱼老师，你怎么对得起苍老师，你怎么对得起那么多ooxx ...

我是不会那些精英挑战赛一类的题

jerryxjr1220

新手·ing 发表于 2017-8-18 16:56
我是不会那些精英挑战赛一类的题

我是说【每天进步一点点】这个系列的，这个系列就是面向新手而写的，题目应该都很简单，从基础开始。
可以把这里面的题目都做做，练练手。

新手·ing

jerryxjr1220 发表于 2017-8-18 17:04
我是说【每天进步一点点】这个系列的，这个系列就是面向新手而写的，题目应该都很简单，从基础开始。
可 ...

你都给答案了

pingws928

def euler(n):
    list=[1,1]
    while max(list)<n:
        list.append(list[-1]+list[-2])
    list.pop()
    return sum(list[2::3])

jerryxjr1220

新手·ing 发表于 2017-8-18 17:40
你都给答案了

同一道题有好多解法呢，你看你楼下的这位，就是很不错的写法。

新手·ing

jerryxjr1220 发表于 2017-8-18 18:39
同一道题有好多解法呢，你看你楼下的这位，就是很不错的写法。

好吧，我尽力