Числа Фибоначчи
Есть мнение, что впервые последовательность Фибоначчи была известна в Индии. Однако, своим названием в современном мире последовательность обязана Леонарду Пизанскому (Leonardo Pisano) по прозвищу Фибоначчи (Fibonacci), жившему в средневековой Европе примерно с 1170 по 1250.
Отца Леонардо звали Гильермо. Он был торговцем. Хотя, судя по всему, много большим, чем просто человек у лотка. После именно Леонардо, успевший значительно попутешествовать с отцом и без него, предложит использовать в торговых делах арабские цифры и десятичную систему счисления.
По поводу этимологии прозвища Леонардо имеются две версии. Согласно первой Гильермо имел прозвище Bonacci, то есть «Благонамеренный». Примечательное прозвище для торговца, замечу. Леонардо же назвал себя filius Bonacci — «сын Благонамеренного». Согласно второй версии Фибоначчи есть прочтение итальянской фразы figlio buono nato ci, что означает «там родился хороший сын».
Правило получения последовательности Фибоначчи звучит просто: каждый последующий член последовательности равен сумме двух предыдущих, при том, что нулевой член равен нулю, а первый — единице. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и так далее. То есть общая формула получения последовательности выглядит так:
Иногда бывает полезно записать ее же относительно n-го члена. Тогда формула примет вид:
Закономерность для отрицательных чисел последовательности Фибоначчи определяется следующим выражением:
Код программы на Java, реализующий получение чисел Фибоначчи.
package fibonacciNumber;
import java.math.BigInteger;
public class FibonacciNumber {
static long getByRecurcive(int n) {
if (n < 2) {
return n;
} else {
return getByRecurcive(n - 1) + getByRecurcive(n - 2);
}
}
static long getByLoop(int n) {
long a = 0;
long b = 1;
for (int i = 0; i < n; i++) {
long saveA = a;
a = b;
b = saveA + a;
}
return a;
}
static BigInteger getByLoopWithBigInteger(int n) {
BigInteger a = new BigInteger("0");
BigInteger b = new BigInteger("1");
for (int i = 0; i < n; i++) {
BigInteger saveA = a;
a = b;
b = saveA.add(a);
}
return a;
}
public static void main(String[] args) {
for (int n = 0; n < 10; n++) {
System.out.print(FibonacciNumber.getByRecurcive(n) + " ");
}
System.out.println();
for (int n = 0; n < 10; n++) {
System.out.print(FibonacciNumber.getByLoop(n) + " ");
}
System.out.println();
for (int n = 0; n < 10; n++) {
System.out.print(FibonacciNumber.getByLoopWithBigInteger(n) + " ");
}
System.out.println();
}
}
Программа реализована одним классом. В классе присутствуют три статических метода для вычисление числа Фибоначчи на позиции N. Метод getByRecurcive реализует рекурсивное вычисление. Остерегайтесь переполнения стека. Метод работает значительно медленнее двух других, основанных на итерациях. Методы getByLoop и getByLoopWithBigInteger отличаются только ограничением на разрядность возвращаемого значения.
Несколько слов о выходе за разрядную сетку. Максимальное значение целого числа и длинного целого числа можно посмотреть с помощью конструкций
System.out.println("Max integer value is " + Integer.MAX_VALUE);
System.out.println("Max long value is " + Long.MAX_VALUE);
Максимальное значение Integer будет 2 147 483 647. Значение 45 члена последовательности Фибоначчи будет 1 134 903 170, 46 — 1 836 311 903. А если бы методы из примера возвращали не long, а int, то при попытке вычислить 47 член мы бы увидели -1 323 752 223, вместо 2 971 215 073.
Аналогично для Long. 9 223 372 036 854 775 807 — максимальное значение. Значение 92 члена — 7 540 113 804 746 346 429. А на 93 будет выход за разрядную сетку, и вместо 12 200 160 415 121 876 738 мы увидим -6 246 583 658 587 674 878.
Таким образом для алгоритмов с int можно вычислить последовательность Фибоначчи до 46 члена включительно, а для алгоритмов с возврщаемым значением long — до 92 включительно. Для получения значений больших членов необходимо использовать типы данных с большей разрядностью.
Ваш комментарий