Итерационный алгоритм чисел Фибоначчи

Ответ 1

Проблема в том, что ваш return y находится в цикле вашей функции. Поэтому после первой итерации он уже остановится и вернет первое значение: 1. За исключением случаев, когда n равно 0, и в этом случае функция будет возвращена как 0, а в случае n равна 1, когда цикл for не будет повторяться даже один раз, и не выполняется return (следовательно, возвращаемое значение None).

Чтобы исправить это, просто переместите return y за пределы цикла.

Альтернативная реализация

Следуя примеру KebertXs, вот решение, которое я лично сделал бы на Python. Конечно, если бы вы обрабатывали многие значения Фибоначчи, вы могли бы даже захотеть объединить эти два решения и создать кэш для чисел.

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

Ответ 2

Вы возвращаете значение в цикле, поэтому функция выходит до того, как значение y всегда будет больше 1.

Если я могу предложить что-то более короткое и гораздо более pythonful:

def fibs(n):                                                                                                 
    fibs = [0, 1, 1]                                                                                           
    for f in range(2, n):                                                                                      
        fibs.append(fibs[-1] + fibs[-2])                                                                         
    return fibs[n]

Это будет делать то же самое, что и ваш алгоритм, но вместо создания трех временных переменных он просто добавляет их в список и возвращает n число фибоначчи по индексу.

Ответ 3

В фиде (0) вы возвращаете 0, потому что:

if (n == 0) {
    return 0;
}

В фиде (1) вы возвращаетесь 1, потому что:

y = 1
return y

На рисунке (2) вы возвращаете 1, потому что:

y = 1
return y

... и так далее. Пока return y находится внутри вашего цикла, функция заканчивается на первой итерации вашего цикла for каждый раз.

Здесь хорошее решение, которое придумал другой пользователь: Как написать последовательность Фибоначчи в Python

Ответ 4

Нерекурсивная последовательность Фибоначчи в python

def fibs(n):
    f = []
    a = 0
    b = 1
    if n == 0 or n == 1:
        print n
    else:
        f.append(a)
        f.append(b)
        while len(f) != n:
            temp = a + b
            f.append(temp)
            a = b
            b = temp

    print f

fibs(10)

Вывод: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Ответ 5

def fibiter(n):
    f1=1
    f2=1
    tmp=int()
    for i in range(1,int(n)-1):
        tmp = f1+f2
        f1=f2
        f2=tmp
    return f2

или с параллельным назначением:

def fibiter(n):
    f1=1
    f2=1
    for i in range(1,int(n)-1):
        f1,f2=f2,f1+f2
    return f2

шрифт печати (4)

Ответ 6

Я наткнулся на это на еще один поток, и он значительно быстрее, чем что-либо еще, что я пробовал, и не нахожусь на большом количестве. Вот ссылка в математику.

def fib(n):
    v1, v2, v3 = 1, 1, 0  
    for rec in bin(n)[3:]: 
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

Ответ 7

Эта работа (интуитивно)

def fib(n):
    if n < 2:
        return n
    o,i = 0,1
    while n > 1:
        g = i
        i = o + i
        o = g
        n -= 1
    return i

Ответ 8

Как насчет этого простого, но самого быстрого способа... (я только что открыл!)

def fib(n):
    x = [0,1]
    for i in range(n >> 1):
        x[0] += x[1]
        x[1] += x[0]
    return x[n % 2]

Внимание! в результате этот простой алгоритм использует только 1 назначение и 1 дополнение, так как длина цикла сокращается как 1/2, и каждый цикл включает в себя 2 назначения и 2 дополнения.

Ответ 9

fcount = 0 #a count recording the number of Fibonacci numbers generated
prev = 0
current = 0
next = 1
ll = 0 #lower limit
ul = 999 #upper limit

while ul < 100000:
    print("The following Fibonacci numbers make up the chunk between %d and %d." % (ll, ul))
    while next <= ul:
        print(next)
        prev = current
        current = next
        next = prev + current
        fcount += 1 #increments count

    print("Number of Fibonacci numbers between %d and %d is %d. \n" % (ll, ul, fcount))        
    ll = ul + 1 #current upper limit, plus 1, becomes new lower limit
    ul += 1000 #add 1000 for the new upper limit
    fcount = 0 #set count to zero for a new batch of 1000 numbers

Ответ 10

Другой возможный подход:

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=2
while i<n:
    e=d[-1]+d[-2]
    d.append(e)
    i+=1
print("Fibonacci series of {} is {}".format(n,d))

Ответ 11

Предполагая эти значения для последовательности фибоначчи:

F (0) = 0;

F (1) = 1;

F (2) = 1;

F (3) = 2

При значениях N > 2 вычислим значение фибоначчи с помощью этой формулы:

F (N) = F (N-1) + F (N-2)

Один итеративный подход, который мы можем взять на это, заключается в вычислении фибоначчи от N = 0 до N = Target_N, так как мы делаем это, мы можем отслеживать предыдущие результаты фибоначчи для N-1 и N-2

public int Fibonacci(int N)
{
    // If N is zero return zero
    if(N == 0)
    {
        return 0;
    }

    // If the value of N is one or two return 1
    if( N == 1 || N == 2)
    {
       return 1;
    }

    // Keep track of the fibonacci values for N-1 and N-2
    int N_1 = 1;
    int N_2 = 1;

    // From the bottom-up calculate all the fibonacci values until you 
    // reach the N-1 and N-2 values of the target Fibonacci(N)
    for(int i =3; i < N; i++)
    {
       int temp = N_2;
       N_2 = N_2 + N_1;
       N_1 = temp;
    }

    return N_1 + N_2; 
}

Ответ 12

Возможное решение:

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=0
while len(d)<n:
    temp=a+b
    d.append(temp)
    a=temp
    b=d[i+1]
    i+=1
print("Fibonacci series of {} is {}".format(n,d))  

Ответ 13

import time

a,b=0,1
def fibton(n):
    if n==1:
        time.clock()
        return 0,time.clock()
    elif n==2:
        time.clock()
        return 1,time.clock()
    elif n%2==0:
        read="b"
    elif n%2==1:
        read="a"
    else:
        time.clock()
        for i in range(1,int(n/2)):
            a,b=a+b,a+b
        if read=="b":
            return b,time.clock()
        elif read=="a":
            return.a,time.clock()

Отказ от ответственности: я сейчас на мобильном устройстве, и это может быть не совсем правильно.

Этот алгоритм использует пробел в некоторых других народах, и теперь он буквально в два раза быстрее. Вместо того, чтобы просто установить b равным a или наоборот, а затем установить a на a+b, я делаю это дважды с еще двумя символами. Я также добавил тестирование скорости, основанное на том, как прошел мой другой итерационный алгоритм. Это должно быть в состоянии перейти к 200 000-му числу Фибоначчи за секунду. Он также возвращает длину числа, а не целое число, которое будет навсегда.

Мой другой мог перейти ко второму числу Фибоначчи, как указано встроенными часами: через 10 ^ -6 секунд. Это можно сделать примерно в 5 ^ -6. Я скоро получу несколько более сложных алгоритмов и уточню их для максимальной скорости.

Ответ 14

Для конкретной программы вы можете использовать следующий код

def fib (n): 
if( n == 0):
    return 0
else:
    x = 0 
    y = 1 
    for i in range(1,n):
        y =y+x
        x=y
    return y

for i in range(10):
    print (fib(i))

Здесь x - это старое значение, а y - текущее значение. В цикле замените y (текущее значение) на y+x (текущее значение + старое значение), затем назначьте текущее значение x.Print текущее значение