LINUX.ORG.RU
Форум — Development  

ЖЖ (вычисление чисел фибоначчи)

 , ,


1

1

Привет! Только что написал такой код:

#!/usr/bin/python3
def fibs (n): 
	if n==0:
		return 1
	elif n<0:
		return False
	init=[0,1]
	for i in range(1, n+1):
		sum= init[0] + init[1]
		init[0] = init[1]
		init[1]= sum
	
	return init[1]


a= fibs(5)
print(a)

А какие еще варианты функции, вычисляющей числа Фибоначчи приходят вам в голову?

★★

Последнее исправление: alpha (всего исправлений: 1)
← Кривая работа zenity в bash скрипте
Wait_event в userspace или ожидание события →
 ← 1 2

Только что написал такой код:

Прям до пробела соответствует тому, что приведен в Algorithms For Dummies. Написал он, ага. Учи пеп.

anonymous
()
Ответ на: комментарий от anonymous

Вариант, что я изобрел велосипед в голову не приходил? И приведи мне это пример.

anti_win ★★
() автор топика
Последнее исправление: anti_win (всего исправлений: 1)
Ответ на: комментарий от vvn_black

Интересно. Но я пока решил не вдаватся в функциональное программирование. Все-таки, это уже следующий этап, на мой взгляд.

anti_win ★★
() автор топика

А какие еще варианты функции, вычисляющей числа Фибоначчи приходят вам в голову?

$ clojure
Clojure 1.10.1
user=> (def fib (lazy-cat [0 1] (map + (rest fib) fib)))
#'user/fib
user=> (take 30 fib)
(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)

)))))))))))))))))))))))))))))))))))))))))

EXL ★★★★★
()
Ответ на: комментарий от Darth_Revan

 Это когда функция вызывает саму себя. Не благодари

Спасибо, Капитан Очевидность! Не хочу показаться невежлевым, но эту информацию я знаю и без твоих мудрых сентенций.

anti_win ★★
() автор топика
Ответ на: комментарий от Darth_Revan

рекурсия хороша до тех пор, пока ее глубина заведомо невелика. например вычислить рекурсией(если компилятор не умеет или не может ее развертнуть в цикл) нечто глубиной в миллиард рекурсивных вызовов вряд ли сможет средний комп. зато циклом это делается запросто, вопрос только во времени вычислений.

alysnix ★★★
()
Ответ на: комментарий от anti_win

Спасибо, Капитан Очевидность! Не хочу показаться невежлевым, но эту информацию я знаю и без твоих мудрых сентенций.

Так в чём проблема-то? Это самый прямой и простой способ реализовать вычисление чисел Фибоначчи (а заодно и самый медленный и плохой):

#!/usr/bin/env python3

def fibs(n: int):
    if n < 0:
        return False
    elif n == 0:
        return 0
    elif n == 1: 
        return 1
    else:
        return fibs(n - 2) + fibs(n - 1)

if __name__ == "__main__":
    print(fibs(5))
Darth_Revan ★★★★★
()
Последнее исправление: Darth_Revan (всего исправлений: 3)

А какие еще варианты функции, вычисляющей числа Фибоначчи приходят вам в голову?

def fib(n):
    q, w, e, r = 0, 1, 0, 1
    n += 1
    while n > 0:
        if n & 1:
            e, r = q * e + w * r, w * e + (q + w) * r
            n -= 1
        else:
            q, w = q * q + w * w, q * w * 2 + w * w
            n //= 2
    return e

(Конечно же это придумал не я. А жаль. Идея довольно красивая.)

i-rinat ★★★★★
()
Последнее исправление: i-rinat (всего исправлений: 1) 
from math import sqrt, pow

def fib(n):
    fi = (sqrt(5) + 1) / 2
    return int((pow(fi, n) - pow(-fi, -n))/(2 * fi - 1))
eternal_sorrow ★★★★★
()
Последнее исправление: eternal_sorrow (всего исправлений: 1)
Ответ на: комментарий от alysnix

Для любого языка можно найти реализацию trampoline

anonymous
()
Ответ на: комментарий от Darth_Revan

Это самый прямой и простой способ реализовать вычисление чисел Фибоначчи (а заодно и самый медленный и плохой)

Компилятор наверное развернет рекурсию в цикл или питон так не умеет?

Int64 ★★★
()
Ответ на: комментарий от Int64

Компилятор наверное развернет рекурсию в цикл или питон так не умеет?

никто не умеет, это же не хвостовая рекурсия…

fsb4000 ★★★★★
()

А какие еще варианты функции, вычисляющей числа Фибоначчи приходят вам в голову?

#include <iostream>

template <int N>
struct Fib
{
    enum { value = Fib<N-1>::value + Fib<N-2>::value };
};

template <>
struct Fib<0>
{
    enum { value = 1 } ;
};

template <>
struct Fib<1>
{
    enum { value = 1 } ;
};

struct Null {
    typedef struct Null value;
    typedef struct Null next;
};

template <int N, template<int> typename T, int L = N>
struct Take
{
    typedef T<L-N> value;
    typedef Take<N-1, T, L> next;
};

template <template<int> typename T, int L>
struct Take<0, T, L>
{
    typedef T<L> value;
    typedef Null next;
};

template <typename T, template<typename> typename F, typename value = typename T::value, typename next = typename T::next>
struct For
{
    void operator()() {
        (F<value>())();
        (For<next, F>())();
    }
};

template <template<typename> typename F, typename value, typename next>
struct For<Null, F, value, next>
{
    void operator()() {
    }
};

template<typename value> struct Print {
    void operator()() {
        std::cout << value::value << " ";
    }
};

int main(void)
{
    (For<Take<30, Fib>, Print>())();
    std::cout << std::endl;
    return 0;
}

$ g++ fib.cpp && ./a.out
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
Deleted
() 
cat fib
#!/bin/bash

echo -n "0, 1"
prev=0;
cur=1;
for i in $(seq 3 $1); do
	x=$prev
	prev=$cur
	cur=$((prev + $x))
	echo -n ", $cur"
done
echo ""

./fib 30
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
anonymous
()

Ещё немного функциональщины, без рекурсивного ограничения и даже с попыткой «тупой» оптимизации мемоизацией:

from functools import reduce


def fib(n):
    return reduce(
        lambda a, c: c > 2 and {**a, **{c: a[c - 1] + a[c - 2]}} or a,
        range(n + 1),
        {0: 0, 1: 1, 2: 1})[n]


print(fib(10000))

33644...(ещё 2080 знаков)...66875


real    0m1,199s
user    0m1,176s
sys     0m0,024s

Плюсом, сразу получаем весь ряд. )

vvn_black ★★★★★
()
Последнее исправление: vvn_black (всего исправлений: 1)

из-за особенностей питона он будет излишне тормозить. Сделой хотя бы на генераторе.

Shadow ★★★★★
()

Немного изучил тему рекурсии, написал такой код:

#!/usr/bin/python3

def gp (af, q, n):
	if n == 1:
		return af
	if n == 2:
		return af *q**(n-1)
	return q*gp(af, q, n-1)

a = gp(2, 8, 3)
print(a)

Считает n-ый член геометрической прогрессии.

anti_win ★★
() автор топика 
def f(n):
    sqrt5 = 5 ** .5
    golden = (1 + sqrt5) / 2
    return int(golden**n/sqrt5 +.5)

Дьёрдь Пойа тебе

qulinxao3 ★★
()
Ответ на: комментарий от anti_win

если курить рекурсию - то функцию Аккермана раскури.

и apply|eval Из лишпа 1.5

перепеши их в питончик - получишь самопальный универсальный …

играясь с сим интерпретатор скобок укуришся так рекурсией что твоё умение питона достигнет Юпитера.

дерзай рекурсию правильным образом.

qulinxao3 ★★
()
Ответ на: комментарий от anti_win 
#!/usr/bin/python3

def gp(r, q, n):
	if n == 1:
		return r
	return gp(r*q, q, n-1)

a = gp(2, 8, 3)
print(a)
qulinxao3 ★★
()

А питон умеет в замыкания? На луа я бы написал итератор, который помнит два последних числа и возвращает следующее. И дергай его пока не надоест. Просто, понятно, стек не кончится

pihter ★★★★★
()
Ответ на: комментарий от pihter 
def fibs(n: int) -> int:
    def iter() -> int:
        nonlocal prev, cur
        ret, prev, cur = prev, cur, cur + prev
        return ret

    assert n >= 0
    prev, cur = 0, 1

    for i in range(0, n):
        iter()
    return iter()

Типа такого?

Darth_Revan ★★★★★
()
Ответ на: комментарий от Darth_Revan

Да это я тебе просто в копилку идей, я весь тред не читал, но вроде не было

Прикольно было бы сравнить по скорости с луа :)

pihter ★★★★★
()

синьор фибоначи девелопер к вашим услугам

print((lambda a:lambda v:a(a,v))(lambda s,x: 1 if x in [0, 1] else s(s, x-1) + s(s, x-2))(5))

пятёрку меняй на нужное число

Cirno ★
()
Последнее исправление: Cirno (всего исправлений: 2)

Чет тег code у меня не работает …

[code=python] FibArray = [0,1]
def fibonacci(n): if n<0: print(«Incorrect input») elif n<=len(FibArray): return FibArray[n-1] else: temp_fib = fibonacci(n-1)+fibonacci(n-2) FibArray.append(temp_fib) return temp_fib

Driver Program

print(fibonacci(9)) [/code]

hotpil ★★★★
()
Последнее исправление: hotpil (всего исправлений: 3)
Ответ на: комментарий от fsb4000

Напишите коллективную жалобу на марк даунов в l-o-r и запилите вакабамарк по умычанию.

anonymous
()
Ответ на: комментарий от vvn_black

Красиво в математике, согласен. Но не красиво когда стек переполняется. Рекурсии место там, где есть умные компиляторы, которые её в цикл разворачивать умеют.

peregrine ★★★★★
()
Ответ на: комментарий от anonymous

в строке где в N матчится N происходит стекование аргументов акерманки перед вызовом акерманки что кушает стек - т.е сия реализация не полностью концевая :)

qulinxao3 ★★
()
Ответ на: комментарий от qulinxao3

Акермана разверни

Он итак развернут. Проблемы (реализации) языка Аккермана не касаются

anonymous
()

мне нравиться вот такая версия

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

AndreyKl ★★★★★
()
Ответ на: комментарий от fsb4000

Компилятор наверное развернет рекурсию в цикл или питон так не умеет?

никто не умеет, это же не хвостовая рекурсия…

Умеет. GHC.

Vault_Boy ★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2
← Кривая работа zenity в bash скрипте
Development
Wait_event в userspace или ожидание события →