我原来错误地编写了程序 . 我没有在一个范围(即startNumber 1,endNumber 20应该=只有1和20之间的数字)之间返回Fibonacci数,而是为程序编写了显示范围之间的所有Fibonacci数(即startNumber 1,endNumber 20)显示=前20个斐波纳契数) . 我以为我有一个确定的代码 . 我也不明白为什么会这样 .
startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
print map(fib, range(startNumber, endNumber))
有人在我的第二部分中指出(因为重复而被关闭 - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii),我需要使用while循环将startNumber和endNumber传递给生成器 . 有人可以指点我如何做到这一点?欢迎任何帮助 .
我是一名学习程序员,而且我遇到了一些混乱 . 我被要求编写一个程序,它将通过用户输入的起始编号和结束编号来计算和显示斐波那契序列(即startNumber = 20 endNumber = 100,它将仅显示该范围之间的数字) . 诀窍是包含它(我不知道如何在Python中使用它? - 我假设这意味着使用包含范围?) .
到目前为止我所拥有的不是实际编码,而是:
-
将Fib序列公式写为无穷大
-
仅从Fib序列显示startNumber到endNumber .
我不知道从哪里开始,我正在寻求有关如何写这个的想法或见解 . 我也尝试过编写Fib序列论坛,但我也迷失了 .
30 回答
在wikipedia和wolfram上有很多关于斐波纳契数列的信息 . 比你可能需要的要多得多 . 无论如何,学习如何使用这些资源来找到(如果可能的话)你需要的东西是一件好事 .
将Fib序列公式写为无穷大
在数学中,它以递归形式给出:
在编程中, infinite 不存在 . 您可以使用递归表单直接在您的语言中翻译数学表单,例如在Python中它变为:
用你最喜欢的语言尝试它,看到这个形式需要 a lot 的时间随着n变大 . 事实上,这是O(2n)及时 .
继续我链接到你的网站,并会看到这个(在wolfram上):
在Python中,这个非常容易实现并且非常非常快速地计算:
另一种方法是遵循定义(来自wikipedia):
如果您的语言支持迭代器,您可以执行以下操作:
仅从Fib序列显示startNumber到endNumber .
一旦你知道如何生成Fibonacci数字,你只需要循环数字并检查它们是否验证了给定的条件 .
假设你现在写了一个f(n),它返回Fibonacci序列的第n项(就像sqrt(5)那样)
在大多数语言中,您可以执行以下操作:
在python中我会使用迭代器形式并转到:
我的提示是学会阅读你需要的东西 . 项目欧拉(google for it)将训练你这样做:P祝你好运,玩得开心!
Fibonacci序列的高效Pythonic发生器
我试图获得这个序列中最短的Pythonic代数时发现了这个问题(后来发现我在_787358中看到了类似的一个),我没有注意到其他人提出我的具体解决方案(尽管最佳答案接近了) ,但仍然不那么优雅,所以这里是,用评论描述第一次迭代,因为我认为这可以帮助读者理解:
和用法:
打印:
(出于归因目的,我最近在模块的Python文档中注意到similar implementation,甚至使用变量
a
和b
,我现在回想起在写这个答案之前已经看过 . 但我认为这个答案证明了该语言的更好用法 . )递归定义的实现
Online Encyclopedia of Integer Sequences以递归方式定义Fibonacci序列
在Python中以递归方式简洁地定义这个可以如下完成:
但是,对于远大于30的数字,数学定义的这种精确表示非常低效,因为计算的每个数字也必须计算低于它的每个数字 . 您可以通过使用以下内容来演示它有多慢:
记忆效率递归
它可以被记忆以提高速度(这个例子利用了每次调用函数时默认关键字参数是同一个对象的事实,但通常你不会因为这个原因而使用可变的默认参数):
您会发现记忆版本的速度要快得多,并且在您甚至可以考虑起床喝咖啡之前会快速超过最大递归深度 . 您通过这样做可以看到它在视觉上的速度有多快:
(看起来我们可以只执行下面的操作,但实际上它并没有让我们利用缓存,因为它在调用setdefault之前调用自身 . )
递归定义的生成器:
在我学习Haskell的过程中,我在Haskell中遇到了这个实现:
我认为我目前在Python中最接近的是:
这证明了这一点:
但它只能达到递归限制 . 通常,1000,而Haskell版本可以达到100万,虽然它使用笔记本电脑的所有8 GB内存来执行此操作:
为什么不简单地做以下事情呢?
好的..在厌倦了所有冗长的答案后,现在找到以下排序和甜蜜,非常直接的方式在python中实现斐波那契 . 您可以通过获取参数或获取用户输入来以您想要的方式增强它...或者从10000更改限制 . 正如您所需......
这种方法也表现良好 . 在下面找到运行分析
Fibonacci序列背后的想法显示在以下Python代码中:
这意味着fib是一个可以做三件事之一的函数 . 它将fib(1)== 1,fib(0)== 0和fib(n)定义为:
fib(n-1)fib(n-2)
其中n是任意整数 . 这意味着例如fib(2)扩展为以下算法:
我们可以用下面的算法以相同的方式计算fib(3):
这里要认识到的重要一点是,在不计算fib(2)的情况下无法计算fib(3),这是通过知道fib(1)和fib(0)的定义来计算的 . 像fibonacci函数一样调用函数就叫做递归,这是编程中的一个重要主题 .
这听起来像是家庭作业,所以我不打算为你做开始/结束部分 . Python虽然是一种非常富有表现力的语言,所以如果你理解数学,这应该是有意义的,并且希望能教你递归 . 祝好运!
编辑:我的代码的一个潜在批评是它没有使用超级方便的Python函数yield,这使得fib(n)函数缩短了很多 . 我的例子有点更通用,因为Python以外的很多语言实际上并没有产生 .
Time complexity :
缓存功能通过消除Fibonacci系列的递归树中的重复,减少了从 O(2^n) 到 O(n) 计算Fibonacci级数的正常方法:
Code :
使用O(log n)基本算术运算非常有效 .
这个使用O(1)基本算术运算,但中间结果的大小很大,因此效率不高 .
这个通过平方求幂来计算多项式环Z [X] /(X ^ 2 - X - 1)中的X ^ n . 该计算的结果是多项式Fib(n)X Fib(n-1),从中可以读取第n个Fibonacci数 .
同样,这使用O(log n)算术运算并且非常有效 .
Canonical Python代码打印Fibonacci序列:
对于问题“打印长度超过1000位的第一个Fibonacci数”:
使用递归:
我们知道
并且该矩阵的n次幂给了我们:
因此,我们可以实现一个简单地计算该矩阵对第n-1次幂的功率的函数 .
因为我们都知道a ^ n等于的功率
所以最后斐波纳契函数将是O(n)......如果不是因为我们也知道
x^n * x^n = x^2n
而且x^n
的评估可以用复杂度O(记录n)这是我使用swift编程语言的fibonacci实现:
这具有复杂度O(log n) . 我们用指数n-1计算Q的幂,然后我们得到元素m00,它是Fn 1,在幂指数n-1正好是我们想要的第n个斐波纳契数 .
一旦你有了快速的fibonacci函数,你可以从起始编号和结束编号迭代,得到你感兴趣的Fibonacci序列的一部分 .
当然首先要对开始和结束进行一些检查,以确保它们可以形成有效范围 .
我知道问题是8岁了,但无论如何我都很乐意回答 . :)
这些看起来都比他们需要的要复杂得多 . 我的代码非常简单快速:
另一种方法:
将列表分配给'a',将整数分配给'n'Map和reduce是python中三个最强大的函数中的两个 . 这里map仅用于迭代'n-2'次 . a [-2:]将获得数组的最后两个元素 . a.append(x y)将添加最后两个元素并将附加到数组
使用for循环并打印结果
结果
打印包含所有数字的
list
结果
结果
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368 ,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102325155,165580141,267914296,433944437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049 ,12586269025,20365011074,32951280099,53316291173,86267571272,135583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,101010209857723,17167680177565,27777890035288,44945570212853]
运行时间: 0.04298138618469238
there is a very easy method to realize that!
您可以使用http://www.learnpython.org/在线自由运行此代码
基本上从Ruby翻译:
...
斐波那契序列是:
1, 1, 2, 3, 5, 8, ...
.那是
f(1) = 1
,f(2) = 1
,f(3) = 2
,...
,f(n) = f(n-1) + f(n-2)
.我最喜欢的实现(最简单但与其他实现相比实现了轻量级)是这样的:
Test
Timing
编辑:[an example visualization](http://www.pythontutor.com/visualize.html#code=def+fibonacci(n%29%3A%0A++++a,+b+%3D+0,+1%0A++++for+_+in+range(1,+n%29%3A%0A++++++++a,+b+%3D+b,+a+%2B+b%0A++++return+b%0A++++%0Afibonacci(10%29&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=3&rawInputLstJSON=%5B%5D&curInstr=0)用于此实现 .
递归增加了时间 . 要消除循环,首先要
import math
. 然后在函数中使用math.sqrt
和黄金比例:参考:Fibonacci Numbers in Python
这是对亨利亨利答案的改进:
代码应该打印b而不是打印c
输出:1,1,2,3,5 ....
这是斐波纳契系列python中最简单的一个,但是通过append()在输出数组中调整[0],得到结果列表第二个变量
result.append(second)
OUTPUT
去了解如何将递归问题转换为迭代问题 . 应该可以从那里计算出来 .
这可能是他们试图让你学习的原则,特别是如果这是一个算法课程 .
在学习Python时使用的教程15分钟后,它要求读者编写一个程序,该程序将根据3个输入数字(第一个Fibonacci数,第二个数和停止序列的数字)计算Fibonacci序列 . 本教程仅涵盖了变量,if / thens和循环到那一点 . 还没有功能 . 我想出了以下代码:
正如您所看到的,它效率非常低,但它确实有效 .
刚刚经过http://projecteuler.net/problem=2这是我的看法
这是我在Khan Academy的Sal on Python Programming上看到的练习作业:https://www.khanacademy.org/science/computer-science-subject/computer-science/v/exercise---write-a-fibonacci-function
他可能不是第一个将其作为一些工作要做的人 . 但是你自己搞清楚它真是棒极了 . 实际上我学到了很多东西,这是一个爆炸 .
我建议您在尝试复制其他人的代码进行作业之前自己弄清楚 .
在上面的视频中,讲师Sal展示了Fibonacci数字背后的整个理论,考虑到这一点,你应该能够弄明白 .
我花了大约10分钟,这是我制作的代码(我在3天前开始学习Python,这是我学习的第一种编程语言) . 如果不是以前教程中的视频,我就无法编写代码:https://www.khanacademy.org/science/computer-science-subject/computer-science/v/comparing-iterative-and-recursive-factorial-functions那个给出了一个Sal做一个递归阶乘方程的例子,给你一个解决这个问题的思维模式 .
这是我的代码:
您可以看到,如果数字是1或0,那么您只需返回该数字 .
我发现这比说清楚,如果数字是1返回1,如果数字是0返回0 .
也许这会有所帮助
试试这个:
基于经典的斐波纳契序列,仅仅是为了单行
如果你只需要索引的数量,你可以使用减少(即使减少它不是最适合这个它可以是一个很好的练习)
并获得完整的数组只需删除or(r.pop(0)和0)