Задача вычисления числа Фибоначчи, наверное, одна из самых классических и часто встречающихся задач. Поспорить с ней за это звание может, разве что написание "Hallo World".
В том или ином виде это задание встречается в различных курсах по программированию. в школьном курсе информатики (кому повезет с информатикой в школе), институтском курсе. Так что, если вы увлечены данной темой, надеюсь этот разбор будет вам не лишним.
Итак, давайте сформулируем задание: Вычислить значение итого числа ряда Фибоначчи. Номер числа в ряду вводится стандартным вводом (клавиатура). Вывод результата на стандартный вывод (Монитор).
Мне кажется все максимально понятно. С клавиатуры вводится число, и программа выводи на экран число из ряда с введенным индексом.
Теперь давайте разберем немного теории: Ряд Фибоначчи это такой ряд где каждый член равен сумме двух предыдущих.
0, 1, 1, 2, 3, 5, 8, 13...
не трудно заметить что: 0+1=1, 1+1=2, 1+2=3, 2+3=5, 3+5=8, 5+8=13...
То-есть: N(i)=N(i-1)+N(i-2) от этого мы будем отталкиваться в своих вычислениях.
Так же нужно указать что ноль является нулевым членом ряда, таким образом получается N(0)=0, N(1)=1 то-есть значение первых двух членов ряда равно их номерам.
Теперь, когда мы разобрались с теорией, я предлагаю вам подумать, и постараться найти свое решение, позже сравнить результаты.
Как же будем решать сею проблему.
Во первых нам нужно будет организовать ввод данных и клавиатуры, и преобразовать полученную строку в "int", потому как мы будем работать с целочисленными значениями. Пишем:
n = int(input('Введите номер числа '))
Дальше мы недолго думая пользуемся той особенностью, что значение первых двух членов ряда равно их номерам. N(0)=0, N(1)=1, пишем:
if n < 2:
print(f'Искомый элемент равен {n}')
Как вы можете заметить тут используется "Форматируемая строка", позволяющая обратиться к прерменной, написав ее имя в фгурных скобках {n}. Для организации этой строки пред кавычками необходимо поставить букву f
Отлично, для первых значений (0 и 1) сделали, а далее мы с вами сыграем в некие пятнашки. Для решения нам понадобиться три ячейки памяти. Можно использовать три переменные или организовать список. Я буду делать через список, обращаясь к его элементам по индексу.
Тут внимательно. Мы должны организовать цикл, до того момента пока значение счетчика цикла не станет равным номеру искомого элемента.
i = 2
мы задаем счетчик на двойке потому как для 0 и 1, выполняется условие в начале кода.
fibo = [0,1,1]
Создаем список с тремя элементами. Они сейчас описывают начальное состояние при каждой итерации цикла. В fibo[0] лежит 0, это нулевое значение В fibo[1] лежит 1 это первое значение ряда. В fibo[2] так же лежит 1, но это только для того, чтобы не оставлять пустое значение.
Таким образом при первой же итерации мы солжем значение первой и нулевой ячейки и положим ее в третью:
fibo[2] = fibo[0]+fibo[1]
Затем, мы переместим значения из первой ячейки в нулевую, и из второй в первую. Таким образом получив fibo = [1,2,2]
fibo[0] = fibo[1]
fibo[1] = fibo[2]
И прибавим к значению счетчика единицу
i+=1
Как вы можете видеть, в конце итерации мы имеем список где нулевая ячейка это N(i-2), а первая N(i-1) Третья ячейка несет в себе функцию пустой клетки в пятнышках, временного хранилища результата сложения. Далее следует проверка условия цикла и если i превысило введенное значение, то цикл прекращается и на экран выводится значение первой ячейки, то-есть N(i-1)
print(f'Искомый элемент равен {fibo[1]}')
Таким образом мы завершаем написание программы.
Надеюсь, вам все было понятно, вы можете посмотреть видео разбор на нашем канале YouTube:
Код вы можете найти здесь:
https://colab.research.google.com/drive/1KN0afqyU22EBRDwhVYJUSUD2HV853Vzi?usp=sharing