Значение чисел Фибоначчи
Числа Фибоначчи — это определенная последовательность положительных целых чисел, начинающаяся с 0. Целые числа — это положительные целые числа. Итак, число Фибоначчи — это определенная последовательность целых чисел или натуральных чисел, начинающаяся с 0. В этой последовательности первые два числа — 0 и 1, именно в таком порядке. Остальные числа получаются оттуда путем добавления двух предыдущих чисел. Первые двенадцать чисел Фибоначчи получаются следующим образом:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Другими словами, первые двенадцать чисел Фибоначчи:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Конечно, тринадцатым числом будет: 144 = 55 + 89. Числа Фибоначчи можно представить в виде массива, например:
| 0 | 1 | 1 | два | 3 | 5 | 8 | 13 | двадцать один | 3. 4 | 55 | 89 |
Массив имеет индексы. В следующей таблице во второй строке показаны соответствующие индексы с отсчетом от нуля для чисел Фибоначчи в массиве:
| 0 | 1 | 1 | два | 3 | 5 | 8 | 13 | двадцать один | 3. 4 | 55 | 89 |
| 0 | 1 | два | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | одиннадцать |
В индексах с отсчетом от нуля, если элементов двенадцать, последний индекс равен 11.
Числа Фибоначчи могут быть получены за время O(n) или за время O(1). В этих выражениях временной сложности n означает n основных операций, а 1 означает 1 основную операцию. При O(n) получается n чисел Фибоначчи, начиная с 0. При O(1) из соответствующего индекса получается одно число Фибоначчи. Вот почему O(1) выполняет только одну основную операцию вместо n основных операций.
Цель этой статьи — объяснить, как создавать числа Фибоначчи в любом случае с помощью JavaScript, который сегодня фактически является ECMAScript.
Среда кодирования
Среда node.js не будет использоваться, как мог ожидать читатель. Вместо этого браузер будет использоваться для интерпретации кода и отображения результатов. Скрипт (код) должен быть записан в файле текстового редактора, который следует сохранить с расширением «.html». Скрипт должен иметь как минимум код:
ДОКТИП HTML >< HTML >
< глава >
< заглавие > Числа Фибоначчи с JavaScript заглавие >
глава >
< тело >
< тип сценария знак равно 'текст/ecmascript' >
сценарий >
тело >
HTML >
Это приблизительный минимальный код, необходимый веб-странице. Весь код для этой статьи находится между тегами .
Для запуска написанного (добавленного) кода достаточно дважды щелкнуть значок имени файла, и браузер компьютера откроет его.
Определение числа Фибоначчи
Существует математическое определение числа Фибоначчи. Он определяется следующим образом:
Где Fn — число Фибоначчи, соответствующее индексу с отсчетом от нуля, n.
Первые два числа: 0 и 1 объявляются заранее, именно в таком порядке. Последняя строка этой функции показывает, как остальные числа происходят от первых двух чисел в их порядке.
Это определение также является одной из формул числа Фибоначчи.
Получение чисел Фибоначчи за время O(n)
Если n равно 1, то в качестве числа Фибоначчи будет отображаться только 0. Если n равно 2, то 0 и 1 будут отображаться как числа Фибоначчи в указанном порядке. Если n равно 3, то 0, 1 и 1 будут отображаться как числа Фибоначчи в указанном порядке. Если n равно 4, то 0, 1, 1 и 2 будут отображаться как числа Фибоначчи в указанном порядке. Если n равно 5, то 0, 1, 1, 2 и 3 будут отображаться как числа Фибоначчи в указанном порядке. Если n равно 6, то 0, 1, 1, 2, 3 и 5 будут отображаться как числа Фибоначчи в указанном порядке — и так далее.
Функция ECMAscript для генерации первых n целых чисел Фибоначчи:
< тип сценария знак равно 'текст/ecmascript' >функция Фибоначчи ( А ) {
н знак равно А. длина ;
если ( н > 0 )
А [ 0 ] знак равно 0 ;
если ( н > 1 )
А [ 1 ] знак равно 1 ;
за ( я знак равно два ; я < н ; я ++ ) { //n=0 и n=2 учтены
currNo знак равно А [ я - 1 ] + А [ я - два ] ;
А [ я ] знак равно currNo ;
}
}
Закрывающий тег скрипта не показан. Функция получает массив. Первые два числа Фибоначчи назначаются на свои позиции. Цикл for повторяется от индекса, начинающегося с нуля, от 2 до чуть меньше n. Самый важный оператор в цикле for:
currNo = A[i – 1] + A[i – 2];
Это добавляет два ближайших предыдущих числа в массив, чтобы получить текущий номер. К моменту завершения выполнения функции fibonacci() все элементы массива представляют собой первые n чисел Фибоначчи. Подходящий код для вызова функции fibonacci() и отображения чисел Фибоначчи:
Н знак равно 12 ;обр знак равно новый Множество ( Н ) ;
Фибоначчи ( обр ) ;
за ( я знак равно 0 ; я < Н ; я ++ )
документ. записывать ( обр [ я ] + ' ' ) ;
документ. записывать ( '
' ) ;
сценарий >
Этот код показывает закрывающий тег скрипта. Код вводится под приведенным выше кодом. Вывод, отображаемый на веб-странице:
0 1 1 2 3 5 8 13 21 34 55 89
как и ожидалось.
Получение одного числа Фибоначчи за время O(1)
O(1) — постоянное время. Это относится к одной основной операции. Другая математическая формула для получения числа Фибоначчи:
Обратите внимание, что в правой части уравнения не квадратный корень из 5 возводится в степень n; это выражение в скобках, возведенное в степень n. Таких выражений два.
Если n равно 0, Fibn будет равно 0. Если n равно 1, Fibn будет равно 1. Если n равно 2, Fibn будет равно 1. Если n равно 3, Fibn будет равно 2. Если n равно 4, Fibn будет равно 3 – и так далее. Читатель может проверить эту формулу математически, подставляя различные значения для n и оценивая. n — индекс в этой формуле, отсчитываемый от нуля. Результатом является соответствующее число Фибоначчи.
Код ECMAScript (JavaScript) для этой формулы:
< тип сценария знак равно 'текст/ecmascript' >функция фибнет ( н ) {
Фибоначчи знак равно ( Математика . паф ( ( 1 + Математика . кв ( 5 ) ) / два , н ) - Математика . паф ( ( 1 - Математика . кв ( 5 ) ) / два , н ) ) / Математика . кв ( 5 ) ;
возвращаться Фибоначчи ;
}
Закрывающий тег скрипта не показан. Обратите внимание, как используются предопределенные функции мощности (pow) и квадратного корня (sqrt). В ECMAScript (JavaScript) математический модуль не нужно импортировать. Функция fibNo() напрямую реализует формулу. Подходящий вызов и отображение функции fibNo() на веб-странице:
Н знак равно одиннадцать ;Правильно знак равно фибнет ( Н ) ;
документ. записывать ( Правильно ) ;
сценарий >
В коде показан закрывающий тег сценария. Результат:
89.00000000000003
Из ответа можно убрать ненужные десятичные цифры. Впрочем, это разговор как-нибудь в другой раз.
Если требуется более одного числа Фибоначчи, код должен вызывать формулу один раз для каждого соответствующего индекса n, основанного на нуле.
Вывод
Числа Фибоначчи — это определенная последовательность положительных целых чисел, начинающаяся с 0. Целые числа — это положительные целые числа. Итак, число Фибоначчи — это определенная последовательность целых чисел или натуральных чисел, начинающаяся с 0. В этой последовательности первые два числа — 0 и 1, именно в таком порядке. Эти первые два числа просто определены как таковые. Остальные числа получаются оттуда путем добавления двух предыдущих чисел.
После получения первых двух чисел Фибоначчи, чтобы получить остальные числа Фибоначчи, чтобы в итоге получить n чисел, необходимо использовать цикл for с оператором:
currNo = A[i – 1] + A[i – 2];
Это добавляет два последних числа Фибоначчи к текущему числу Фибоначчи.
Если задан индекс с отсчетом от нуля, чтобы получить соответствующее число Фибоначчи, используйте формулу:
