Бесконечный ряд Фибоначчи

в 11:33, , рубрики: java, метки:

Привет житель ! Сегодня я хочу поделиться с тобой решением простой школьной задачки с небольшим дополнением. Для нахождения бесконечного ряда Фибоначчи (даже больше чем long).

Это моя первая статья и пожалуйста не судите строго. Все коды я буду приводить на Java. И так начнем:

Все мы знаем, стандартный школьный алгоритм для нахождения ряда Фибоначчи до N-го числа и этот алгоритм таков:

int fib(int i) {
    if (i == 1) return 1;
    if (i == 2) return 1;
    return fib(i - 1) + fib(i - 2);
}

Но такой алгоритм будет работать очень долго если нам понадобиться найти например первые 100 чисел этого ряда. Поэтому сделаем чуть быстрее:

class Main {

	static Main ma = new Main();
        long a = 1, b = 1, c = 0, i = 0;

	public void recursive(){
		if (i < 100) {
			++i;
			a = b;
			b = c;
			c = a + b;
			System.out.println("" + c);
			ma.recursive();
		}
	}

	public static void main(String[] args) {
		ma.recursive();
	}

}

вот так будет чуточку быстрее, но с таким подходом мы не сможет корректно найти даже 94 числа этого ряда. Потому что на 94 числе произойдет переполнение разрядной сетки.

Но добрые разработчики Java продумали все за нас и написали замечательный класс BigDecumal который позволяет нам использовать числа любой длины пока не закончится виртуальная память на нашем ПК. и вот конечный результат нашей программы:

import java.math.BigDecimal; // импортируем этот замечательный класс

class Main {

	static Main ma = new Main();
	BigDecimal a = new BigDecimal("1");
	BigDecimal b = new BigDecimal("1");
	BigDecimal c = new BigDecimal("0");
	int i = 0;

	public void recursive(){
		if (i < 1000) {
			++i;
			a = b;
			b = c;
			c = a.add(b);
			System.out.println("" + c);
			ma.recursive();
		}
	}

	public static void main(String[] args) {
		ma.recursive();
	}

}

Вот собственно и все чем я хотел с вами поделиться. Пожалуйста напишите мне ваши замечания и отзывы.

Спасибо!

Автор: Возле ректора

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js