Как сделать последовательность фибоначчи в python
Перейти к содержимому

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

  • автор:

Числа Фибоначчи: циклом и рекурсией

Числа Фибоначчи – это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих.

Иногда ряд начинают с нуля.

В данном случае мы будем придерживаться первого варианта.

Формула и пример вычисления чисел ряда Фибоначчи

Вычисление n-го числа ряда Фибоначчи с помощью цикла while

Присвоим переменным fib1 и fib2 значения двух первых элементов ряда, то есть единицы.

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

Поскольку значения первых двух элементов ряда Фибоначчи нам уже известны и вычисления начинаем с третьего, количество проходов по телу цикла должно быть на 2 меньше значения n , то есть n — 2 .

Если пользователь вводит 1 или 2, тело цикла ни разу не выполняется, на экран выводится исходное значение fib2 .

  1. Сложить fib1 и fib2 , присвоив результат переменной для временного хранения данных, например, fib_sum .
  2. Переменной fib1 присвоить значение fib2 .
  3. Переменной fib2 присвоить значение fib_sum .

После окончания работы цикла вывести значение fib2 на экран.

fib1 = 1 fib2 = 1 n = input("Номер элемента ряда Фибоначчи: ") n = int(n) i = 0 while i  n - 2: fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print("Значение этого элемента:", fib2)

Пример выполнения программы:

Номер элемента ряда Фибоначчи: 10 Значение этого элемента: 55

Компактный вариант кода:

fib1 = fib2 = 1 n = input("Номер элемента ряда Фибоначчи: ") n = int(n) - 2 while n > 0: fib1, fib2 = fib2, fib1 + fib2 n -= 1 print("Значение этого элемента:", fib2)

Вывод ряда чисел Фибоначчи с помощью цикла for

В данном случае выводится не только значение искомого элемента ряда Фибоначчи, но и все числа до него включительно. Для этого вывод значения fib2 помещен в цикл.

fib1 = fib2 = 1 n = int(input()) print(fib1, fib2, end=' ') for i in range(2, n): fib1, fib2 = fib2, fib1 + fib2 print(fib2, end=' ') 
10 1 1 2 3 5 8 13 21 34 55

Рекурсивное вычисление n-го числа ряда Фибоначчи

  1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице.
  2. Во всех остальных случаях вызвать эту же функцию с аргументами n — 1 и n — 2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.
def fibonacci(n): if n in (1, 2): return 1 return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(10))

Допустим, n = 4. Тогда произойдет рекурсивный вызов fibonacci(3) и fibonacci(2). Второй вернет единицу, а первый приведет к еще двум вызовам функции: fibonacci(2) и fibonacci(1). Оба вызова вернут единицу, в сумме будет два. Таким образом, вызов fibonacci(3) возвращает число 2, которое суммируется с числом 1 от вызова fibonacci(2). Результат 3 возвращается в основную ветку программы. Четвертый элемент ряда Фибоначчи равен трем: 1 1 2 3.

X Скрыть Наверх

Решение задач на Python

Числа Фибоначчи в языке программирования Python: как произвести расчет

Lorem ipsum dolor

Цикл «for» в Python позволяет вывести не только конкретное число Фибоначчи, но и все предшествующие числа, то есть целый ряд чисел. Чтобы у нас это получилось , мы вывод значения «fsum2» поместим в цикл.

Как это реализуется:

fnum1 = fnum2 = 1

n = intput (“Введите номер числа Фибоначчи: “)

n = int(n)

print (fnum1, fnum2, end= )

for i in range(2, n):

fnum1, fnum2 = fnum2, fnum1 + fnum2

print(“Ряд чисел Фибоначчи до указанного номера: “, fnum2, end= )

Программа нам выдаст следующий результат:

Введите номер числа Фибоначчи: 13

Ряд чисел Фибоначчи до указанного номера: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

Заключение

Числа Фибоначчи можно просчитать при помощи циклов «for» или «while». Иногда для генерации чисел используют рекурсию, однако она имеет ряд ограничений и работает медленнее, чем представленные функции.

Мы будем очень благодарны

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

Рекурсивный метод нахождения чисел Фибоначчи

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

Решение задачи

  1. Принимаем на вход число членов последовательности и записываем его в отдельную переменную.
  2. Это число передается в качестве аргумента в рекурсивную функцию, которая будет вычислять n -й член последовательности.
  3. В качестве базового условия принимаем то обстоятельство, что число членов последовательности Фибоначчи не может быть меньше единицы либо равно ей. При наступление этого условия рекурсия останавливается.
  4. В противном случае функция вызывается вновь следующим образом: в качестве аргумента нашей рекурсивной функции передается введенное число, уменьшенное на единицу, и к этому прибавляется эта же функция с аргументом, уменьшенным уже на 2.
  5. Каждый вызов функции возвращает одно число, которое мы потом выводим на экран.

Исходный код

Ниже дан исходный код, который осуществляет вывод всех членов последовательности Фибоначчи заданного размера. Результаты работы программы также даны ниже.

def fibonacci(n): if (n 

Объяснение работы программы

  1. Пользователь вводит число и оно записывается в переменную n .
  2. Передаем число n в качестве аргумента в рекурсивную функцию, которая вычисляет n-ый член последовательности.
  3. Так как первый член последовательности Фибоначчи по определению не может быть меньше 1, в качестве базового условия принимаем n
  4. В противном случае функция вызывается вновь следующим образом: fibonacci(n-1) + fibonacci(n-2) .
  5. Результаты выводятся на экран при помощи цикла for .

Результаты работы программы

Пример 1: Введите число членов последовательности:5 Последовательность Фибоначчи: 0 1 1 2 3 Пример 2: Введите число членов последовательности:7 Последовательность Фибоначчи: 0 1 1 2 3 5 8

Примечания переводчика

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

Вычисление чисел Фибоначчи

Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как Φ n > , где Φ — золотое сечение.

Приведем C++ — код этой функции:

//Функция возвращает n-e число Фибоначчи по данному n. int fib(unsigned int n)  if (n  2) return n; return fib(n - 1) + fib(n - 2); > 

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

Решение с помощью динамического программирования [ править ]

В данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением F i > . В этой задаче легко организовать восходящее ДП, так как мы знаем, что для вычисления F n > понадобятся F n − 1 > и F n − 2 > . Асимптотическая сложность алгоритма будет O(n) время и O(n) памяти.(Требуется массив и один проход по массиву).

Код функции, реализующий восходящее ДП:

//возвращает n-e число Фибоначчи int fib_n(int n)  if (n  2) return n; int dp[n]; dp[1] = 1; dp[2] = 1; for (int i = 3; i  n; i++)  dp[i] = dp[i - 1] + dp[i - 2]; > return dp[n]; > 

Код функции на Python, возвращающий последовательность чисел с помощью списка:

def fibo(n): f = [0, 1] for i in range(2, n + 1): f.append(f[i-1] + f[i-2]) print(f) n = 10 fibo(n) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 

Элегантное решение [ править ]

Приведем ещё одно решение — оно использует также как и динамическое программирование O(n) времени, но обходится всего O(1) памяти. Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих, а не все предыдущие.

Приведем С++ — код:

//возвращает n-е число Фибоначчи int fib_n(int n)  //F(n) int x = 1; //F(n-1) int y = 0; for (int i = 0; i  n; i++)  x += y; y = x - y; > return y; > 

Приведем Python — код:

# возвращает последовательность чисел def fibo(n): a = 0 b = 1 print(a, b, end=' ') for i in range(2, n + 1): c = a + b a, b = b, c print(c, end=' ') n = 10 fibo(n) # 0 1 1 2 3 5 8 13 21 34 55 

Решение быстрым возведением матрицы в степень [ править ]

Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем тождестве:

Для удобства обозначим матрицу, возводимую в степень, как P:

Без учета затрат на реализацию длинной арифметики этот алгоритм требует O ( l o g ( n ) ) времени и O ( 1 ) памяти.

Ниже этот алгоритм реализован на языке С. Будем считать, что:

A = ( a b c d ) a&b\\c&d\end>> — временная матрица, используемая в алгоритме возведения в степень. Инициализируется матрицей P . R = ( r c r d ) <\displaystyle R=<\beginrc&rd\end>> — вектор результатов (вторая строка матрицы P n > ), инициализируется как вторая строка единичной матрицы.

//возвращает n-е число Фибоначчи int fib(int n)  int a = 1, ta, b = 1, tb, c = 1, rc = 0, tc, d = 0, rd = 1; while (n)  if (n & 1) // Если степень нечетная  // Умножаем вектор R на матрицу A tc = rc; rc = rc*a + rd*c; rd = tc*b + rd*d; > // Умножаем матрицу A на саму себя ta = a; tb = b; tc = c; a = a*a + b*c; b = ta*b + b*d; c = c*ta + d*c; d = tc*tb+ d*d; n >>= 1; // Уменьшаем степень вдвое > return rc; > 

То же на языке Python:

#возвращает n-е число Фибоначчи def fib(n): a = 1 b = 1 c = 1 rc = 0 d = 0 rd = 1 while n>0: if n%2!=0: #Если степень нечетная # Умножаем вектор R на матрицу A tc = rc rc = rc*a + rd*c rd = tc*b + rd*d #Умножаем матрицу A на саму себя ta = a tb = b tc = c; a = a*a + b*c b = ta*b + b*d c = c*ta + d*c d = tc*tb+ d*d n >>= 1 #Уменьшаем степень вдвое return rc 
  • Программирование
  • Математический анализ
  • Программирование/все учебники
  • Требуется внимание (все учебники)
  • Компьютеры/все учебники
  • Наука/все учебники
  • Учебники по теме/все учебники
  • Математический анализ/все учебники
  • Математика/все учебники
  • Точные науки/все учебники
  • По алфавиту/В

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *