Не буду врать, вы почувствуете себя так после того, как столкнетесь с числами Фибоначчи. Эта концепция ошеломляет, и тем не менее неожиданно часто встречается в математике, и как бы мы, программисты, ни старались избегать сложной математики, мы все, скорее всего, столкнемся с этими плохими мальчиками, когда меньше всего этого ожидаем.
Числа Фибоначчи
Как предупреждение, алгоритм этой недели доведен до Python. Я немного больше работал с этим языком и просто подумал, что проще всего показать вам алгоритм на этом языке, поскольку он читается почти как псевдокод. Вот:
Этот алгоритм находит n-е число в последовательности Фибоначчи.
Если вам нужен другой источник для изучения чисел Фибоначчи, загляните в википедию в абзац здесь. Я буду постоянно обращаться к ним, когда буду объяснять последовательность, так как я не специалист по математике и, вероятно, никогда им не стану.
По сути, есть две отправные точки для чисел Фибоначчи. Одна последовательность начинается с 0, а другая начинается с 1. Я выбрал последовательность, которая начинается с 1, поскольку это исходная теория Фибоначчи и обычное использование, хотя вы могли бы начать с 0.
Последовательность Фибоначчи выглядит следующим образом: каждое число после первых двух является суммой двух предшествующих чисел.
Вот пример
1 1 2 3 5 8 13 21 34 55 …
Как видите, первое и второе числа всегда будут равны 1. После этого третье число будет суммой 1 + 1, четвертое число — суммой 1 + 2 и так далее.
Вам может быть интересно, как этот алгоритм может рекурсивно вызывать сам себя и вычислять n-й номер последовательности. У чисел Фибоначчи также есть уникальная характеристика, которая делает это возможным. Если вы хотите вычислить десятое число в последовательности, оно равно девятому числу Фибоначчи плюс восьмое.
fib(10) = fib(9) + fib(8)
Возьмем другой пример: третье число в последовательности — это второе число в последовательности плюс первое.
fib(3) = fib(2) + fib(1)
Как вы можете видеть в приведенном выше алгоритме, fib(2) и fib(1) всегда будут возвращать 1 для любого из них.
В конечном итоге уравнение для нахождения n-го числа Фибоначчи становится
fib(n) = fib(n-1) + fib(n-2)
это именно то, что показано в алгоритме выше.
Заключение
Это заняло у меня некоторое время, когда я впервые изучал его, поэтому, если это займет у вас немного времени, не расстраивайтесь. Хотя Фибоначчи представил европейскому миру эту математическую концепцию в 1202 году, она настолько сложна и широко распространена, что ее изучению посвящен целый журнал. Прочтите статью в Википедии, и вы поймете, что я имею в виду. До скорого. Ваше здоровье!
