Pull to refresh

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

Привет житель Хабра! Сегодня я хочу поделиться с тобой решением простой школьной задачки с небольшим дополнением. Для нахождения бесконечного ряда Фибоначчи (даже больше чем 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();
	}

}

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

Спасибо!
Tags:
Hubs:
You can’t comment this publication because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.