- Что такое числа Фибоначчи?
- Как найти первые
n
чисел Фибоначчи?
2 ответа
Определение чисел Фибоначчи
Числа Фибоначчи это последовательность натуральных чисел, которая начинается с чисел ноль и один, а каждое следующее число равно сумме двух предыдущих:
Первые 10 чисел Фибоначчи:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Получение первых n
чисел Фибоначчи
Чтобы найти первые n
чисел Фибоначчи, можно создать массив размера n
, первые два элемента будут равны нулю и единице, а остальные элементы можно получить, используя цикл и вышеприведённую формулу:
int[] f = new int[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; ++i) {
f[i] = f[i - 1] + f[i - 2];
}
В коде предполагается существование переменной n
, которую можно ввести с клавиатуры, например так:
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
После заполнения массива f
полученные первые n
чисел Фибоначчи можно вывести на экран с помощью цикла:
for (int i = 0; i < n; ++i) {
System.out.println(f[i]);
}
Стоит заметить, что тип int
в Java позволяет хранить только числа до 231-1, поэтому вышеприведённым способом получится вычислить только первые 46 чисел Фибоначчи (при попытке вычислить сорок седьмое число Фибоначчи произойдёт переполнение и получится отрицательное число). Используя тип данных long
вместо int
без переполнения получится вычислить первые 91 число Фибоначчи. Чтобы вычислять последующие числа Фибоначчи можно воспользоваться классом BigInteger
, который реализует длинную арифметику в Java.
Получения n
-ого по счёту числа Фибоначчи
Для получения только n
-ого числа Фибоначчи не обязательно использовать массив, достаточно завести две переменных a
и b
, в которых будут храниться последние два числа Фибоначчи, и пересчитывать эти переменные n - 2
раза:
int a = 0;
int b = 1;
for (int i = 2; i <= n; ++i) {
int next = a + b;
a = b;
b = next;
}
System.out.println(b);
Рекурсивное вычисление чисел Фибоначчи
Существует также рекурсивный способ вычисления чисел Фибоначчи. Однако его не рекомендуется использовать, потому что, в отличии от предыдущих двух способов, которые работают за линейное время от n
, рекурсивный способ может работать значительно дольше.
// функция, возвращающая n-ое число Фибоначчи
public static int f(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return f(n - 1) + f(n - 2);
}
}
Рекурсивный способ работает за экспоненциальное время от n
, например для n
равного 46 рекурсивный способ работает дольше пяти секунд, а способ с запоминанием последних двух чисел Фибоначчи работает менее одной десятой секунды).
Рекурсивный способ может работать долго, потому что в процессе вычисления функция будет много раз вызываться от одного и того же аргумента (например, при вычислении f(5)
функция сделает рекурсивные вызовы к f(4)
и f(3)
, оба рекурсивных вызова обратятся к f(2)
), что приведёт к многократному повторению одних и тех же операций.
Быстрое вычисление чисел Фибоначчи с помощью быстрого умножения матриц (используя O(log n)
операций умножения)
Рассмотрим матрицу:
Используя матричное умножение, рекуррентное соотношение для последних двух чисел Фибоначчи может быть записано так:
Расписывая это соотношение, получаем:
Таким образом, чтобы найти n
-ое число Фибоначчи достаточно возвести матрицу A
в степень n - 1
. Это можно сделать алгоритмом быстрого возведения в степень.
// матричное умножение двух матриц размера 2 на 2
public static BigInteger[][] matrixMultiplication(BigInteger[][] a, BigInteger[][] b) {
// [a00 * b00 + a01 * b10, a00 * b01 + a01 * b11]
// [a10 * b00 + a11 * b10, a10 * b01 + a11 * b11]
return new BigInteger[][]{
{a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])), a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))},
{a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])), a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))},
};
}
// возведение матрицы размера 2 на 2 в степень n
public static BigInteger[][] matrixPowerFast(BigInteger[][] a, int n) {
if (n == 0) {
// любая матрица в нулевой степени равна единичной матрице
return new BigInteger[][]{
{BigInteger.ONE, BigInteger.ZERO},
{BigInteger.ZERO, BigInteger.ONE}
};
} else if (n % 2 == 0) {
// a ^ (2k) = (a ^ 2) ^ k
return matrixPowerFast(matrixMultiplication(a, a), n / 2);
} else {
// a ^ (2k + 1) = (a) * (a ^ 2k)
return matrixMultiplication(matrixPowerFast(a, n - 1), a);
}
}
// функция, возвращающая n-ое число Фибоначчи
public static BigInteger fibonacci(int n) {
if (n == 0) {
return BigInteger.ZERO;
}
BigInteger[][] a = {
{BigInteger.ONE, BigInteger.ONE},
{BigInteger.ONE, BigInteger.ZERO}
};
BigInteger[][] powerOfA = matrixPowerFast(a, n - 1);
// nthFibonacci = powerOfA[0][0] * F_1 + powerOfA[0][0] * F_0 = powerOfA[0][0] * 1 + powerOfA[0][0] * 0
BigInteger nthFibonacci = powerOfA[0][0];
return nthFibonacci;
}
public static void main(String[] args) {
System.out.println(fibonacci(1024));
}
В дополнение к ответу @diralik
Быстрое вычисление без матриц
Степени матрицы можно выразить через числа Фибоначчи. Нетрудно показать по индукции, что
Это выражение даёт нам формулы удвоения индекса числа Фибоначчи:
Эта формула реализована в коде ниже в методе Fib.fast(int)
.
import java.math.BigInteger;
public class Fib {
public BigInteger next_ = BigInteger.ONE;
public BigInteger current_ = BigInteger.ZERO;
public int n = 0;
public Fib next() {
BigInteger tmp = next_.add(current_);
current_ = next_;
next_ = tmp;
n++;
return this;
}
public static Fib slow(int n) {
var result = new Fib();
for (var i = 0; i < n; i++) {
result.next();
}
return result;
}
public static Fib fast(int n) {
if (n < 16) {
return Fib.slow(n);
}
var result = Fib.fast(n/2);
result.n *= 2;
// F_{2n+1} = F_{n+1}**2 + F_{n}**2
var _next = result.next_.multiply(result.next_).add(result.current_.multiply(result.current_));
// F_{2n} = (2*F_{n+1} - F_{n})*F_{n}
var _current = (result.next_.add(result.next_).subtract(result.current_)).multiply(result.current_);
result.next_ = _next;
result.current_ = _current;
if (n%2 == 1) {
result.next();
}
return result;
}
}
Оценка через золотое сечение
Для чисел Фибоначчи есть формула Бине, которая вычисляет числа Фибоначчи без итерации.
Так как числа Фибоначчи довольно быстро выходят за пределы типа double
, для оценки числа Фибоначчи через формулу Бине я использую BigDecimal
с округлением до 20 значащих цифр. Такое округление даёт 10 правильных цифр в результате.
private static final MathContext _mc = new MathContext(20, RoundingMode.HALF_UP);
private static final double _sqrt5 = Math.sqrt(5);
public static final BigDecimal Sqrt5 = new BigDecimal(_sqrt5, _mc);
public static final BigDecimal Phi = new BigDecimal((1 + _sqrt5)/2, _mc);
public static BigDecimal estimate(int n) {
return Phi.pow(n, _mc).divide(Sqrt5, _mc);
}
Сравнение скорости
Быстрая формула вычисления чисел Фибоначчи использует три умножения на каждой итерации. Но благодаря тому, что число итераций растёт как логарифм n
, общее время счёта по быстрой формуле в разы меньше, чем по классической формуле.
Ниже приведены сравнения результатов для n=100, 1000, 10000, 100000, 1000000
. Время в миллисекундах. Estimate
- это как раз оценка по формуле Бине.
Slow: 100: 0.3249 (ms)
Fast: 100: 0.0736 (ms)
As double: 100: 3.5422484817E+20
Estimate : 100: 3.5422484817926308651E+20
Slow: 1000: 0.4168 (ms)
Fast: 1000: 0.1707 (ms)
As double: 1000: 4.3466557686E+208
Estimate : 1000: 4.3466557686938912905E+208
Slow: 10000: 5.604 (ms)
Fast: 10000: 1.526 (ms)
As double: 10000: 3.3644764876E+2089
Estimate : 10000: 3.3644764876443071607E+2089
Slow: 100000: 231.6341 (ms)
Fast: 100000: 8.0684 (ms)
As double: 100000: 2.5974069347E+20898
Estimate : 100000: 2.5974069347308882558E+20898
Slow: 1000000: 15967.3608 (ms)
Fast: 1000000: 89.9357 (ms)
As double: 1000000: 1.9532821287E+208987
Estimate : 1000000: 1.9532821287733027741E+208987
В выводе используется функция asFloatString
, которая для большого целого строит приблизительное представление в виде вещественного числа
private static String asFloatString(BigInteger bint, int ndig) {
var _full = bint.toString(10);
var s = _full.substring(0, ndig+1);
s = s.substring(0,1) + "." + s.substring(1) + "E+" + (_full.length()-1);
return s;
}