Сумма последовательности Фибоначчи отключена на 1
У меня есть код для вычисления суммы всех четных чисел последовательности Фибоначчи меньше 4 000 000.
/*
Through the use of Binet's formula for the Fibonacci Sequence and the fact
that every third number of the sequence is an even number.
*/
import java.lang.Math.*;
public class Optimised002 {
public static void main(String[] args) {
long sum = 0;
for (int i = 0; i < 4_000_000; i += 3) {
long number = binetsFormula(i);
if (number < 4_000_000L) {
sum += number;
}
}
System.out.println(sum);
}
public static float sqrt5 = 2.2360679775f;
public static float goldenRatio = 1.61803398875f;
public static float reciprocalGoldenRaio = -0.61803398875f;
public static long binetsFormula(int nth) {
return Math.round((Math.pow(goldenRatio, nth) - Math.pow(reciprocalGoldenRaio, nth)) / sqrt5);
}
}
Правильный ответ, который я получил с помощью грубой силы ранее, - 4613732, для этого метода я получаю сумму 4613733: off на значение 1. Возможно, это из-за того, что sqrt5 или GoldenRatio недостаточно точны, или некоторые компьютеры плохо разбираются в математике. вещь: я понятия не имею, почему. Понимание очень ценится.
Ну, если бы вы складывали только четные числа, у вас не было бы нечетной суммы. Как насчет того, чтобы проверить, какой из терминов, которые вы добавляете, является странным?
@khelwood это хороший момент
Я бы рекомендовал использовать double, а не float. Вы показали эти константы с большим количеством знаков после запятой, чем может точно представить float, и формула Бине на самом деле очень чувствительна к неточностям в значениях этих констант.
Напоминание: реальная арифметика и компьютерная арифметика — не одно и то же.
Еще одна маленькая проблема с вашим кодом — вы складываете только 11 чисел Фибоначчи, но вычисляете 1,33 миллиона из них и просто отбрасываете результат для большинства из них. Это означает, что ваш код в 120 тысяч раз медленнее, чем должен быть.
И, наконец, я не думаю, что часть - Math.pow(reciprocalGoldenRaio, nth) вообще изменит результат. Этот термин очень быстро становится очень маленьким, и ваше округление все равно полностью его убьет.
Ответы 1
Вы можете изменить число с плавающей запятой на двойное, а также использовать встроенный класс Math.
Я думаю, что double может хранить больше десятичных знаков, чем float, поскольку double хранит 64 бита информации, тогда как float хранит 32 бита информации.
Https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html
Также бывает, что статический метод Math.sqrt(n) возвращает значение типа double, поэтому имеет смысл использовать тип double.
Вот пример кода.
public class BinetsFormula {
public int fib(int n) {
double a = (1 + Math.sqrt(5))/2;
double b = (1 - Math.sqrt(5))/2;
double c = (Math.pow(a, n) - Math.pow(b, n))/Math.sqrt(5);
return (int) c;
}
public static void main(String[] args) {
BinetsFormula formula = new BinetsFormula();
for (int i = 0; i < 20; i++) {
if (i < 19)
System.out.print(formula.fib(i) + " ");
else if (i == 19)
System.out.println(formula.fib(i));
}
}
}
Приведенный выше код выводит первые 20 чисел Фибоначчи.
Теперь мы можем получить сумму всех четных чисел Фибоначчи меньше 4 000 000.
public class BinetsFormula {
private final double sqrt5 = Math.sqrt(5);
private final double a = (1 + sqrt5)/2;
private final double b = (1 - sqrt5)/2;
public long fib(int n) {
return Math.round((Math.pow(a, n) - Math.pow(b, n))/sqrt5);
}
public static void main(String[] args) {
BinetsFormula formula = new BinetsFormula();
int n = 0;
long f = 0;
long sum = 0;
long max = 4000000;
while ((f = formula.fib(n)) < max) {
if (f % 2 == 0)
sum += f;
n++;
}
System.out.printf("Sum: %d\n", sum);
}
}
Второй пример оптимизирован.
Я создал константы sqrt5, a и b, чтобы эти вычисления выполнялись только один раз.
@khelwood Я суммирую только каждое третье число последовательности Фибоначчи, поэтому обе единицы пропускаются.