Создание последовательности чисел Фибоначчи (оптимизация)

@Kvintero · Регистрация: 21.04.2014

Author24 — интернет-сервис помощи студентам

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

Вопрос у меня сегодня такой: как можно оптимизировать мою функцию по созданию последовательности чисел Фибоначчи?
Вот что я написал:

Haskell

1	fib x = foldl (\x y -> x++[(head (tail(reverse x)))+(last x)] ) [1,1] (replicate (x-2) 1)

@_Ivana · 23.06.2015, 16:16

Да как угодно. Для начала, без ++, ластов и реверсов. Для продолжения - вам именно последовательность или число с определенным порядковым номером? Если первое, то есть много красивых алгоритмов, мне нравится через поток. Если второе, то есть пара не менее красивых алгоритмов.

@Araneo · 23.06.2015, 16:18

На удивление годный способ, я нашёл в своё время на вики...

Haskell

1	fibs = 0 : 1 : [a + b \| (a,b) <- zip fibs (tail fibs)]

@Kvintero · 23.06.2015, 16:33 **[ТС]**

Да, интересная функция, но она считает все числа. Можно добавить считалку по индексу, для выбора конкретного числа или последовательности. Будет это побыстрей работать. Но главная проблема, как я понял из-за того, что одно число это сумма дувух предыдущих. как обратиться к пред-предпоследнему числу не пробегая по всему списку чисел?

@Catstail · 23.06.2015, 20:00

Haskell

fib :: Integer -> Integer
fib n = fib' n 1 1
        where fib' n c p | (n<=2) = c
                         | otherwise = fib' (n-1) (c+p) c

@_Ivana · 23.06.2015, 20:22

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

Haskell

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

В таком виде он (и еще много интересного) приведен в SICP (реализация конечно на Scheme, безо всяких листомонад и туплей), в таком же виде я его нарисовал в своем лискрипте на ленивых потоках. И тут самое интересное - у меня ленивые вычисления не мемоизируются при расчете (навскидку не удалось сделать), так что тот же самый код у меня выполняется экспоненциальное время, в на Scheme и в Haskell - линейное. Достаточно забавно, учитывая что код один и тот же, а его "годность" различается в зависимости от языка выполнения. Но конечно существует другой вариант реализации, который выполняется даже на моем скрипте линейное время, и третий - за логарифмическое.

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

И это только пара моментов, касательно вышеувиденного.

Добавлено через 3 минуты
https://github.com/Ivana-/Lisc... /test1.txt

Lisp

-- поток Фибоначчи - нульарная функция
-- НЕ экспоненциальный расчет
(defn fibgen (a b) (s-cons a (fibgen b (+ a b))))
(def fibs (fibgen 0 1))
(printLn "")
(printLn "первые 25 членов потока ряда Фибоначчи:")
(printLn (s-take 25 fibs))
 
-- экспоненциальный расчет
-- первый конс обычный, второй - потоковый отложенный, через макрос
(defn fibsexp () (cons 0 (s-cons 1 (s-sum (s-tail (fibsexp)) (fibsexp)))))
(printLn "")
(printLn "первые 10 членов потока ряда Фибоначчи:")
(printLn (s-take 10 (fibsexp)))

@Shamil1 · 23.06.2015, 20:36

Сообщение от Kvintero

Да, интересная функция, но она считает все числа.

В сабже "Создание последовательности чисел Фибоначчи"

Сообщение от Kvintero

Но главная проблема, как я понял из-за того, что одно число это сумма дувух предыдущих. как обратиться к пред-предпоследнему числу не пробегая по всему списку чисел?

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

Haskell

1
2
3

fib n = iter 1 0 n where
    iter a b k | k == 0    = b
               | otherwise = iter (a + b) a (k - 1)

Но можно вычислить число Фибоначчи и без вычисления всех предшествующих чисел:

Haskell

fib2 n = iter 1 0 0 1 n where
    iter a b p q k | k == 0    = b
                   | even k    = iter a b (p*p+q*q) (2*p*q+q*q) (div k 2)
                   | otherwise = iter (b*q+a*q+a*p) (b*p+a*q) p q (k-1)

@_Ivana · 23.06.2015, 20:52

Не по теме:

Началось котомеряние, жаль тема про Фибоначчи а не про факториал - у меня есть хорошая такая ссылка насчет котомеряния факториалами. Хотя и про Фибоначчи можно не хуже собрать подборку :)

@Shamil1 · 24.06.2015, 09:21

Не по теме:

Сообщение от _Ivana

Началось котомеряние,

Да тут даже не котомеряние, а просто использование O(logN) алгоритма вместо O(N). Быстрое возведение в степень вместо перемножения N раз.

@castorsky · 24.06.2015, 13:21

Сообщение от Shamil1

Но можно вычислить число Фибоначчи и без вычисления всех предшествующих чисел

ага Ряд Фибоначчи

@_Ivana · 24.06.2015, 15:11

Не по теме:

Shamil1, да это все понятно, кэп. Плавали, писали, в тех же примерах для моего лискрипта на гитхабе реализовано. Еще про алгоритм на основе перемножения матриц (тот же, только из другой теоретической формализации) расскажите. Просто я назвал эту ситуацию котомерянием. Причем, не в плохом смысле этого слова :)

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	23.06.2015, 16:16	2
	Да как угодно. Для начала, без ++, ластов и реверсов. Для продолжения - вам именно последовательность или число с определенным порядковым номером? Если первое, то есть много красивых алгоритмов, мне нравится через поток. Если второе, то есть пара не менее красивых алгоритмов. 0

@Kvintero 1 / 1 / 0 Регистрация: 21.04.2014 Сообщений: 65
	23.06.2015, 16:33 [ТС]	4
	Да, интересная функция, но она считает все числа. Можно добавить считалку по индексу, для выбора конкретного числа или последовательности. Будет это побыстрей работать. Но главная проблема, как я понял из-за того, что одно число это сумма дувух предыдущих. как обратиться к пред-предпоследнему числу не пробегая по всему списку чисел? 0

@_Ivana
	23.06.2015, 20:52 #8
	Не по теме: Началось котомеряние, жаль тема про Фибоначчи а не про факториал - у меня есть хорошая такая ссылка насчет котомеряния факториалами. Хотя и про Фибоначчи можно не хуже собрать подборку :) 0

@Shamil1
	24.06.2015, 09:21 #9
	Не по теме: Сообщение от _Ivana Началось котомеряние, Да тут даже не котомеряние, а просто использование O(logN) алгоритма вместо O(N). Быстрое возведение в степень вместо перемножения N раз. 0

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	24.06.2015, 13:21	10
	Сообщение от Shamil1 Но можно вычислить число Фибоначчи и без вычисления всех предшествующих чисел ага Ряд Фибоначчи 0

@_Ivana
	24.06.2015, 15:11 Создание последовательности чисел Фибоначчи (оптимизация) #11
	Не по теме: Shamil1, да это все понятно, кэп. Плавали, писали, в тех же примерах для моего лискрипта на гитхабе реализовано. Еще про алгоритм на основе перемножения матриц (тот же, только из другой теоретической формализации) расскажите. Просто я назвал эту ситуацию котомерянием. Причем, не в плохом смысле этого слова :) 0