Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >项目Euler #2 ( Fibonacci数之和在400万以下)的更有效解决方案

项目Euler #2 ( Fibonacci数之和在400万以下)的更有效解决方案
EN

Code Review用户
提问于 2014-01-16 20:31:13
回答 4查看 2.6K关注 0票数 7

我想得到一些关于我的代码的反馈。我是在做了一些在线Python课程之后开始编程的。

你能帮助我,跟随我的思路,然后找出我可以更有效率的地方吗?(我看到了其他答案,但它们似乎比所需的复杂,尽管篇幅较短;但也许这就是关键所在)。

问题:

Fibonacci序列中的每个新项都是通过添加前两个项来生成的。从1和2开始,前10项将是:1、2、3、5、8、13、21、34、55、89、.通过考虑Fibonacci序列中值不超过400万的项,找出偶数项的和。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
fibValue = 0
valuesList = []

a = 0
b = 1

#create list

while fibValue <= 4000000:
    fibValue = a + b
    if fibValue % 2 == 0:
        valuesList.append(fibValue)
    a = b
    b = fibValue

print (valuesList) #just so that I can see what my list looks like after fully compiled

print() #added for command line neatness

print() #added for command line neatness

newTot = 0

for i in valuesList:
    newTot += i
print (newTot)
EN

回答 4

Code Review用户

发布于 2014-01-16 21:19:34

我总是向人们提出这个问题的暗示。看一看序列的前几个数字--我用粗体将偶数设置为:

1,1,2,3,5,8,13,21,34,55,89,144

你能看到间隔上的图案吗?你能解释(理想情况下,证明)吗?

既然如此,你能想出一种直接生成斐波那契数的方法吗,而不是为它们过滤?(提示:从(1,2)开始,尝试一步生成(5,8),然后(21,34)等,做一些代数,并想出如何同时应用生成规则的多次迭代。

无论如何,在用数字进行实际计算时,有更优雅的方法。我们可以编写一个生成器,而不是直接要求Python构建一个列表:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
def even_fibonacci_up_to(n):
    a, b = 1, 2
    while b <= n:
        yield b # since 2 qualifies, after all.
        # Now calculate the next value.
        # math from the first step goes here when you figure it out!

注意yield关键字的使用。这允许我们将表达式even_fibonacci_up_to(4000000)看作是一种特殊的序列,其元素是按需生成的。与普通函数不同,普通函数只能return一次。)(在生成器中使用return将在到达yielding值时终止整个过程。)

我们可以使用内置的sum函数,而不是循环遍历这个序列来累加数字:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
sum(even_fibonacci_up_to(4000000))
票数 7
EN

Code Review用户

发布于 2016-07-24 23:40:54

您的方法不错,尽管它可以被清理,我有一个更快、更直接的建议,比如使用一个简单的类。

  • Knechtel的方法似乎创造了一个近乎无限的循环。
  • Madison的递归方法超过输入40,达到"RuntimeError:最大递归深度超过“。但他们建议的第三种解决方案似乎没有错误地执行,但输出似乎不准确.我相信你只得到了最大的数字,达克。我的也一样。

我认为这是你最好的,最准确的,最简单的(也是最快的给出一个正确的解决方案):

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
def fib(n):   # return Fibonacci series up to n
    result, a, b = list(), 0, 1 # set variables
    result.append(0) # Initial Fibonacci Zero
    while b < n:
        if b % 2 == 0:
            result.append(b)
        a, b = b, a+b
    return result

def fibSum(n):
    return sum(map(int, fib(n)))

print(fibSum(4000000))

希望这能有所帮助。祝好运!

此外,我建议在打印代码清洁时使用“\n”作为新行,没有必要使用几个打印语句,但我们都是从某个地方开始的,我自己只编写了大约一年的Python程序,但我的背景中也有其他语言,我读了很多书。几个关键注意事项: map允许您轻松地总结一个in /truple列表,您可以使用sum而不是在列表中递增并将其加起来,在“几乎”所有情况下,它应该更快(字符串是一个不同的故事)。再次祝你好运!

我保留了你的国防部2模数是你的朋友。修改内置的周边不是你的朋友,如果你必须这样做,很可能你做错了什么。只是思考的食粮。

基准:

你的守则:

产出: 4613732

运行总时间: 0.000175秒( Python )

总运行时间: 0.000069秒( Pypy )

我的建议:

产出: 4613732

运行总时间: 0.000131秒( Python )

总运行时间: 0.000053秒( Pypy )

编辑:或者,您可以只使用以下内容:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
def fib2(n):
    result, a, b = 0, 0, 1
    while b < n:
        if b % 2 == 0:
            result += b
        a, b = b, a+b
    return result

print(fib2(4000000))

我个人更喜欢让Fibonacci自己来构建一个单一用途类,不管是出于什么原因。显然,它应该稍微快一点,但我还没有测试它。

票数 2
EN

Code Review用户

发布于 2014-01-16 20:51:39

Fibonacci序列是一个非常适合递归解决方案的问题。如果您还没有了解递归,我强烈推荐它,因为它提供了一种全新的方法来看待问题。

要找到第n个Fibonacci数,您可以使用如下所示的内容。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n-1)+fibonacci(n-2)

fibonacci(10) # returns 55

这个答案之所以如此清晰,是因为它的框架方式和斐波纳契序列是一样的。要找到一个斐波那契数,只需知道前两个。

尽管如此,递归确实引入了一些有趣的问题。要找到第100个斐波那契数,需要花费惊人的时间。这样的问题通常需要缓存才能提高递归的效率。

如果我们从相反的方向来处理这个问题呢?我们可以从底层开始,从上往上爬,而不是从上开始往下走。然后,状态存储在函数的参数中。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
def fibonacci(a, b, n):
    if n < 3: return a + b
    return fibonacci(b, a+b, n-1)

fibonacci(0, 1, 10) # returns 55

我希望你喜欢这种递归的味道。如果有什么不清楚的话请告诉我,我很乐意帮忙把事情弄清楚。但是,如果效率是您的目标,那么Python的递归可能不是最好的。

如果递归不是您的问题,或者您打算计算非常大的fibonacci数,您可能需要一个迭代解决方案(实际上,您自己的解决方案非常好)。如果您在寻找小于n的最大fibonacci数,则迭代解决方案工作得特别好。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
def fibonacci(n):
    # finds the largest fibonacci number less than n
    a, b = 0, 1
    while(a+b) < n:
        a, b = b, a+b
    return b
票数 1
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/39493

复制
相关文章
asp.net中显示DataGrid控件列序号的几种方法
在aps.net中多数据绑定的控件很多,论功能来说,应该属DataGrid最为齐全,但它没有提供现成的显示记录序号的功能,不过我们可以通过它所带的一些参数来间接得到序号,下面来看看怎样得到和显示序号值计算方式如下:
Java架构师必看
2021/03/22
1.6K0
PHP错误提示open_basedir restriction in effect的解决方案
前几天收到一个网友反馈,出现了一个错误提示“open_basedir restriction in effect. File(/opt/rasp_php70/logs/alarm/alarm.log.2022-01-01) is not within the allowed path(s)”,看过之后一头雾水,没遇到过,今天做zblog搜索伪静态的时候突然想起来这个错误了,是的,十天了,我才想起来,没办法啊记性不好。百度了一下,应该是宝塔“防跨站攻击(open_basedir)”引起的错误,一般来说是Apache环境引起的。
李洋博客
2022/01/18
8.6K0
PHP错误提示open_basedir restriction in effect的解决方案
随机日志:两列显示
  看到别人的随机日志都是现实两列,我这一直显示一列,一是因为显示一列不好看,二是提供的信息量太低。因此改成两列还是很有必要的,于是自己写了些css样式,添加到主题的style.css文件的最下面。
the5fire
2019/02/28
9690
点击显示错误
双折线点击一个,另一显示a b 错误.PNG 正确.PNG 隐藏一条线 tooltip: { // 气泡 trigger: "axis"
用户4344670
2019/08/28
1.2K0
点击显示错误
在Ubuntu中配置ASP.NET站点
mono是.NET在Linux等非Windows平台上的第三方实现,借助它就可以实现.NET的跨平台应用。虽然mono还不能支持所有的.NET应用,但对于普通的小型程序,mono已经足够胜任了。更让人鼓舞的是当前最为流行的桌面Linux系统Ubuntu已经集成了mono的运行环境,只要手上有一个.net应用程序,拷贝到Ubuntu中,然后就可以运行了。实际上,在Ubuntu中,已经有一些应用程序是用C#完成的,例如附件中的便签程序Tomboy就是用C#写的,打开Tomboy的文件目录,就会发现很多在Windows中常见的dll程序集,所以,跨平台也不是不可以的。
用户1685462
2021/07/28
1.7K0
Ext根据条件显示隐藏列
  写在ExtonReady函数里面,并在表格成功渲染之后,可以添加判断是否隐藏或者显示某一列
河岸飞流
2019/08/09
2.7K0
IIS发布站点错误收集
转载:http://www.cnblogs.com/hangwei/p/4249406.html
跟着阿笨一起玩NET
2018/09/20
1.6K0
IIS发布站点错误收集
FineUI Grid 缓存列显示隐藏状态
当列表字段过多时,需要隐藏掉一些,但是再次打开页面又显示出来了,FineUI没有提供缓存功能,那么自己动手,打开【ext-part2.js】找到
冰封一夏
2019/09/11
8150
「R」显示英文错误
中文使用 R 经常看到各种乱码文字,让人看不懂意思,特别是在 Windows 系统上。
王诗翔呀
2020/07/02
1.8K0
安装SSL检查提示“错误: 服务器缺少中间证书”
首先检测下证书是不是中间证书缺失,以下两个网站都可以检测。 https://www.ssllabs.com/ssltest/index.html https://www.myssl.cn/tools/
咻一咻
2020/05/29
4.2K0
调查显示编程语言 Ruby 在缓慢衰落,缺少爆发点
Ruby 虽然仍然是 Engine Yard 和 Heroku 等产品的核心,以及 Discourse、Homebrew 和 Vagrant 等项目背后的语言,但你知道吗?Ruby 的走势并不乐观。 Redmonk 近日针对 Ruby 的发展做了一些总结,在其最近的排名中,Ruby 位居第八,落后于 JavaScript、Python 和 PHP 等语言,但领先于 C、Swift 和 Go 。尽管排名不低,但第八名其实是 Ruby 在 redmonk 排名中排名最差的一次。自2012年以来,该语言的排名
企鹅号小编
2018/02/08
1.2K0
调查显示编程语言 Ruby 在缓慢衰落,缺少爆发点
出现“内部错误,无法显示”
This page contains the following errors: error on line 2 at column 6: XML declaration allowed only at the start of the document Below is a rendering of the page up to the first error. 提示信息是头部有错误,我登录后台查看我修改过的页面,然后找到home.php我看了十几分钟没有发现那里有错误~~ 莫非头部不能有空格? 去掉试试
苦咖啡
2018/05/07
3.2K0
linux python 中文显示错误
UnicodeEncodeError: ‘ascii’ codec can’t encode characters in position 20-25: ordinal not in range(128)
py3study
2020/01/07
5.4K0
DataGridView 密码列(显示为*号)的设置
曾经为在DataGridView中设置密码列(显示为*号)而发愁,如何把Windows 窗体 DataGridView 的某一列的数据显示为“*”。
Java架构师必看
2021/03/22
2.3K0
gridview列 数字、货币和日期 显示格式
在设置gridview等数据绑定控件的模版列时,总要设置显示的格式,这里是我查询一些资料后统计出来的。
Java架构师必看
2021/03/22
1.3K0
如何设置Element表格显示或者隐藏列
Element 表格点击复选框显示或隐藏列,效果如下: 主要步骤: 一、渲染复选框 <el-checkbox-group v-model="checkboxVal"> <el-ch
tianyawhl
2020/10/14
6.1K0
Winforms Cefsharp应用通过Vs Installer安装,应用崩溃,缺少文件错误
          本文主要分析winforms cefsharp应用通过Vs Installer做成安装包后,安装程序后,启动程序导致应用崩溃,提示System.IO.FileNotFoundException
郑小超.
2022/12/21
9020
Element Table 动态生成列并且不同的列显示不同的样式
我们在使用表格控件时,经常需要动态生成表格的列,并且某些列要求特殊的样式(如右对齐)
tianyawhl
2020/02/25
5.3K0
在ASP.NET 2.0中建立站点导航层次
站点导航提供程序--ASP.NET 2.0中的站点导航提供程序暴露了应用程序中的页面的导航信息,它允许你单独地定义站点的结构,而不用考虑页面的实际物理布局。默认的站点导航提供程序是基于XML的,但是你也可以通过编写自定义的提供程序,从任何后端位置暴露这些信息。
Java架构师必看
2021/03/22
7.1K0
点击加载更多

相似问题

错误"open_basedir restriction in effect“

12

get_extra_restriction()缺少一个必需的位置参数:'related_alias‘错误django

210

NHIbernate: Restriction.In和Restriction.InG之间的区别

20

内部托管Nuget站点上缺少类型错误

13

Asp.net图多列显示错误数据

11
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文