Как сделать число фибоначчи в паскале

Добавил пользователь Валентин П.
Обновлено: 19.09.2024

program fibon;
var i,n: longint;
a:array[1..n] of longint;
begin
readln(n);
a[1]:=1;
a[2]:=1;
for i:=3 to n do
begin
a:=a[i-1]+a[i-2];
end;
writeln(a);
end.

Требует константное выражение n, а мне с клавиатуры надо. Пишу в Pascal ABC. В чем тут проблема? (Я еще чайник, пока)

Паскаль не поддерживает динамические массивы, т. е. массивы, размер которых не задан на момент компиляции.. . Выкручивайтесь без них.

Если в теле функции встречается вызов самой этой функции, то это и есть рекурсия.

Рекурсивностью в Паскале могут обладать как функции, так и процедуры.

По сути, рекурсия может быть бесконечной. Но, как и любой другой алгоритм, она обязана выдавать результат своей работы за некое определенное количество операций.

Поэтому важно: На каждом шаге выполнения рекурсивного тела процедуры или функции обязательно либо изменение параметра данной функции, либо наличие условия при котором она больше себя не будет вызывать!

Рассмотрим простой пример использования рекурсивной процедуры:

Пример: Напечатать последовательность чисел в обpатном поpядке, используя рекурсивный вызов процедуры. Напpимеp:
row (5) = 5 4 3 2 1
Из условия задачи ясно, что условием завершения рекурсии будет сам аргумент функции, который следует уменьшать на единицу, пока он >= 1 .

Теперь рассмотрим более сложный пример использования рекурсии в Паскаль.

Пример: Написать рекурсивную процедуру, выводящую цифры, переданного ей в качестве фактического параметра числа, в обратном порядке.

Например: при переданном функции числе 3078 , должно в итоге вернуть 8703
Использовать операции div и mod

Подсказка:
2!=2*1=2
3!=3*2*1=6
Выводим формулу a!=a*((a-1)!)

Рекурсия: Написать рекурсивную функцию sumTo(n) , которая для данного n вычисляет сумму чисел от 1 до n , например:
sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
.

Рекурсия: Написать рекурсивную функцию определения степени числа.

Для чисел 3430 и 1365:

остаток от деления 3430 на 1365	3430 mod 1365 = 700
остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток	1365 mod 700 = 665
остаток также не нуль, поэтому еще одно деление	700 mod 665 = 35
остаток также не нуль, поэтому еще одно деление	665 mod 35 = 0
остаток нуль	НОД равен 35

Рекурсия: Распечатать первые 10 чисел Фибоначчи (до 21), используя рекурсивную процедуру с двумя параметрами.
Результат должен быть: 1 2 3 5 8 13 21 34 55 89
Дополните код:

Задача для самостоятельного решения: Используя рекурсивный метод найти N-ый элемент ряда Фибоначчи. Программа должна запрашивать число N и выдавать ответ. Например при вводе числа 8 ответ будет 21.

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

Числа Фибоначчи - это, определение

Числа Фибоначчи - это элементы бесконечной числовой последовательности: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …, в которой каждое последующее число равно сумме двух предыдущих.

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

Числа Фибоначчи - это числовая последовательность, обладающая рядом уникальных свойств, среди которых, например: сумма двух соседних чисел последовательности определяет значение следующего за ними числа (например, 1+1=2; 2+3=5 и т.д.), что порождает существование так называемых коэффициентов Фибоначчи, т.е. постоянных соотношений между числами этой последовательности.

1. Вывести на экран n первых чисел ряда Фибоначчи.

Решение: первый алгоритм поиска чисел Фибоначчи.
Ответ:
n=6
1 1 2 3 5 8

Наверх
Блок-схема

2. Вывести на экран n-ый элемент ряда Фибоначчи.

Решение: первый алгоритм поиска чисел Фибоначчи.
Ответ:
n=10
ch=55

program fib_02;
uses crt;
var ch, ch1, n, i, ch2: integer;

Наверх
Блок-схема

3. Вывести на экран n1-ый и n2-ой элементы ряда Фибоначчи и их сумму

Решение: первый алгоритм поиска чисел Фибоначчи.

Ответ:
n1=5
n2=10
5 55
S=60

или

Ответ:
n1=10
n2=5
5 55
S=60

Program fib_03;
Uses CRT;
var n1, n2, ch, ch1,ch2, i, max, s:integer;

n1, n2 - номера чисел Фибоначчи;
ch - число Фибоначчи;
ch1, ch2 - вспомогательные переменные алгоритма поиска чисел Фибоначчи;
max - наибольший номер числа Фибоначчи;
S - сумма чисел>

begin
clrscr;
s:=0;
write('n1='); readln(n1);
write('n2='); readln(n2);

if n2 > n1 then max:=n2 else max:=n1;

Наверх
Блок-схема

5. Найти удвоенное двадцатое число Фибоначчи.
Решение: первый алгоритм поиска чисел Фибоначчи.
Ответ: ch*2=13530

Наверх
Блок-схема

6. 10 случайных чисел генерируются компьютером в интервале [5,10].
Вывести на экран числа ряда Фибоначчи. Найти их среднее арифметическое.

Решение: первый алгоритм поиска чисел Фибоначчи (рациональнее было бы применить второй алгоритм поиска чисел Фибоначчи. )

Ответ может быть:
Количество чисел Фибоначчи равно 0.

ch=8 ch=8 ch=8
Sred=8.

if kch 0 then begin Sred:=s/kch ; write ('Sred=':5, sred) end
else writeln('Количество чисел Фибоначчи равно 0.');
end.

Наверх
Блок-схема

7. Число x вводится с клавиатуры. Проверить, является оно числом ряда Фибоначчи. Программа с тестированием.

Решение: второй алгоритм поиска чисел Фибоначчи.

Ответ:
x=5
1. ch1=1 ch2=0 ch=1
2. ch1=0 ch2=1 ch=1
3. ch1=1 ch2=1 ch=2
4. ch1=1 ch2=2 ch=3
5. ch1=2 ch2=3 ch=5
Цикл закончен
x - число Фибоначчи

x=6
1. ch1=1 ch2=0 ch=1
2. ch1=0 ch2=1 ch=1
3. ch1=1 ch2=1 ch=2
4. ch1=1 ch2=2 ch=3
5. ch1=2 ch2=3 ch=5
6. ch1=3 ch2=5 ch=8
Цикл закончен
x - не число Фибоначчи

Наверх
Блок-схема

8. Найти количество чисел Фибоначчи в интервале [2, 6].
Программа с тестированием.

Решение: второй алгоритм поиска чисел Фибоначчи.

Ответ:
x=2
число Фибоначчи= 2 k=1

x=3
число Фибоначчи= 3 k=2

x=4
x - не число Фибоначчи

x=5
число Фибоначчи= 5 k=3

x=6
x - не число Фибоначчи

Наверх
Блок-схема

9. Найти количество чисел Фибоначчи в интервале [a, b].

Решение: второй алгоритм поиска чисел Фибоначчи.

Ответ:
первое число в заданном интервале=10
последнее число в заданном интервале=1000
число Фибоначчи= 13
число Фибоначчи= 21
число Фибоначчи= 34
число Фибоначчи= 55
число Фибоначчи= 89
число Фибоначчи= 144
число Фибоначчи= 233
число Фибоначчи= 377
число Фибоначчи= 610
число Фибоначчи= 987
k=10

program fib_09;
uses crt;
var ch, ch1, ch2, a, b, x, k :integer;

begin writeln('число Фибоначчи= ',ch-1); inc(k) end;

Наверх
Блок-схема

Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

Замкнутая формула

Пропустим детали, но желающие могут ознакомиться с выводом формулы. Идея в том, чтобы предположить, что есть некий x, для которого F_n = x n , а затем найти x.

Решаем квадратное уравнение:

что и используем для вычисления F_n.

Хорошее:
Быстро и просто для малых n
Плохое:
Требуются операции с плавающей запятой. Для больших n потребуется большая точность.
Злое:
Использование комплексных чисел для вычисления F_n красиво с математической точки зрения, но уродливо — с компьютерной.

Рекурсия

Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В Python её можно записать в одну строку:

Хорошее:
Очень простая реализация, повторяющая математическое определение
Плохое:
Экспоненциальное время выполнения. Для больших n очень медленно
Злое:
Переполнение стека

Запоминание

У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений.

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

(В Python это можно также сделать при помощи декоратора, functools.lru_cache.)

Хорошее:
Просто превратить рекурсию в решение с запоминанием. Превращает экспоненциальное время выполнение в линейное, для чего тратит больше памяти.
Плохое:
Тратит много памяти
Злое:
Возможно переполнение стека, как и у рекурсии

Динамическое программирование

После решения с запоминанием становится понятно, что нам нужны не все предыдущие результаты, а только два последних. Кроме этого, вместо того, чтобы начинать с fib(n) и идти назад, можно начать с fib(0) и идти вперёд. У следующего кода линейное время выполнение, а использование памяти – фиксированное. На практике скорость решения будет ещё выше, поскольку тут отсутствуют рекурсивные вызовы функций и связанная с этим работа. И код выглядит проще.

Это решение часто приводится в качестве примера динамического программирования.

Хорошее:
Быстро работает для малых n, простой код
Плохое:
Всё ещё линейное время выполнения
Злое:
Да особо ничего.

Матричная алгебра

И, наконец, наименее освещаемое, но наиболее правильное решение, грамотно использующее как время, так и память. Его также можно расширить на любую гомогенную линейную последовательность. Идея в использовании матриц. Достаточно просто видеть, что

А обобщение этого говорит о том, что

Два значения для x, полученных нами ранее, из которых одно представляло собою золотое сечение, являются собственными значениями матрицы. Поэтому, ещё одним способом вывода замкнутой формулы является использование матричного уравнения и линейной алгебры.

Так чем же полезна такая формулировка? Тем, что возведение в степень можно произвести за логарифмическое время. Это делается через возведения в квадрат. Суть в том, что

где первое выражение используется для чётных A, второе для нечётных. Осталось только организовать перемножения матриц, и всё готово. Получается следующий код. Я организовал рекурсивную реализацию pow, поскольку её проще понять. Итеративную версию смотрите тут.

Хорошее:
Фиксированный объём памяти, логарифмическое время
Плохое:
Код посложнее
Злое:
Приходится работать с матрицами, хотя они не так уж и плохи

Сравнение быстродействия

Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе n, то получится, что матричное решение линейно, а решение с динамическим программированием – экспоненциально. Практический пример – вычисление fib(10 ** 6), числа, у которого будет больше двухсот тысяч знаков.

n = 10 ** 6
Вычисляем fib_matrix: у fib(n) всего 208988 цифр, расчёт занял 0.24993 секунд.
Вычисляем fib_dynamic: у fib(n) всего 208988 цифр, расчёт занял 11.83377 секунд.

Теоретические замечания

Не напрямую касаясь приведённого выше кода, данное замечание всё-таки имеет определённый интерес. Рассмотрим следующий граф:

Читайте также: