如何写斐波那契数列? [英] How to write the Fibonacci Sequence?

问题描述

我最初对程序进行了错误编码.我没有为程序返回范围内的斐波那契数(即startNumber 1，endNumber 20应该仅= 1和20之间的那些数)，而是为程序编写了显示范围内的所有斐波那契数(即startNumber 1，endNumber) 20个显示=前20个斐波那契数字).我以为我有一个确定的代码.我也不明白为什么会这样.

I had originally coded the program wrongly. Instead of returning the Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 should = only those numbers between 1 & 20), I have written for the program to display all Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 displays = First 20 Fibonacci numbers). I thought I had a sure-fire code. I also do not see why this is happening.

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))

有人在我的第二部分中指出了这一点(由于重复而被关闭-

Someone pointed out in my Part II (which was closed for being a duplicate - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) that I need to pass the startNumber and endNumber through a generator using a while loop. Can someone please point me in the direction on how to do this? Any help is welcome.

我是一名学习型程序员，现在遇到了一些麻烦.我被要求编写一个程序，该程序将通过用户输入的开始编号和结束编号来计算和显示斐波那契数列(例如，startNumber = 20 endNumber = 100，并且它将仅显示该范围内的数字).诀窍是将其包含在内(我不知道如何在Python中使用它?-我假设这意味着要使用包含范围?).

I'm a learning programmer and I've run into a bit of a jumble. I am asked to write a program that will compute and display Fibonacci's Sequence by a user inputted start number and end number (ie. startNumber = 20 endNumber = 100 and it will display only the numbers between that range). The trick is to use it inclusively (which I do not know how to do in Python? - I'm assuming this means to use an inclusive range?).

到目前为止，我所没有的只是实际的编码，而是:

What I have so far is no actual coding but rather:

• 将Fib序列公式写成无穷大
• 仅显示Fib序列中的startNumber到endNumber.

我不知道从哪里开始，我想提出想法或了解如何编写此内容.我也曾尝试写过Fib序列论坛，但我也对此一无所知.

I have no idea where to start and I am asking for ideas or insight into how to write this. I also have tried to write the Fib sequence forumla but I get lost on that as well.

推荐答案

wolfram 上.比您可能需要的要多得多.无论如何，学习如何使用这些资源来查找(如果可能的话)您需要的东西是一件好事.

There is lots of information about the Fibonacci Sequence on wikipedia and on wolfram. A lot more than you may need. Anyway it is a good thing to learn how to use these resources to find (quickly if possible) what you need.

在数学上，它以递归形式给出:

In math, it's given in a recursive form:

在编程中，无限不存在.您可以使用递归形式直接用您的语言翻译数学形式，例如在Python中，它将变为:

In programming, infinite doesn't exist. You can use a recursive form translating the math form directly in your language, for example in Python it becomes:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

尝试使用您喜欢的语言尝试一下，随着n变大，此表单需要很多的时间.实际上，这就是时间O(2 ⁿ ).

Try it in your favourite language and see that this form requires a lot of time as n gets bigger. In fact, this is O(2ⁿ) in time.

在我链接到的网站上继续进行下去，然后会看到此内容(在 wolfram ):

Go on on the sites I linked to you and will see this (on wolfram):

这是一个非常容易实现且计算速度非常快的Python程序:

This one is pretty easy to implement and very, very fast to compute, in Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

另一种方法是遵循定义(来自维基百科):

An other way to do it is following the definition (from wikipedia):

序列的第一个数字为0， 第二个数字是1，每个 后续数等于和 的前两个数字中的一个 序列本身，产生序列 0、1、1、2、3、5、8等

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc.

如果您的语言支持迭代器，则可以执行以下操作:

If your language supports iterators you may do something like:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

仅显示Fib序列中的startNumber到endNumber.

一旦您知道如何生成斐波那契数，您只需要循环遍历数字并检查它们是否可以验证给定条件.

Display startNumber to endNumber only from Fib sequence.

Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.

现在假设您编写了一个f(n)，该f(n)返回斐波那契数列的第n个项(如带有sqrt(5)的项)

Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence (like the one with sqrt(5) )

在大多数语言中，您可以执行以下操作:

In most languages you can do something like:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

在python中，我将使用迭代器形式并进行以下操作:

In python I'd use the iterator form and go for:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

我的提示是学习阅读您需要的内容.欧拉计画(google for Euler)会训练您:P 祝你好运，玩得开心！

My hint is to learn to read what you need. Project Euler (google for it) will train you to do so :P Good luck and have fun!

这篇关于如何写斐波那契数列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！