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

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

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

Всем привет.
Сразу хочу сказать спасибо постояльцам форума за помощь, которую я получил почти год назад, когда только начинал изучать программирование. С вашей помощью вошел в 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
1
2
3
4
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- поток Фибоначчи - нульарная функция
-- НЕ экспоненциальный расчет
(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
1
2
3
4
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, да это все понятно, кэп. Плавали, писали, в тех же примерах для моего лискрипта на гитхабе реализовано. Еще про алгоритм на основе перемножения матриц (тот же, только из другой теоретической формализации) расскажите. Просто я назвал эту ситуацию котомерянием. Причем, не в плохом смысле этого слова :)

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

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

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

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

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