Блог

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..

С точки зрения математики, общая формула для вычисления ряда Фибоначчи такова

fn = fn-1 + fn-2 , где n ≥ 2

Здесь f₀ = 0 и f₁ = 1.

Нам нужно вычислить n чисел Фибоначчи для любого заданного целого числа n, где n≥0.

Пример:

Input : n = 5
Output : [0, 1, 1, 2, 3]

Input : n = 10
Output : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

В этой статье мы сосредоточимся на двух основных и распространенных способах вычисления рядов Фибоначчи.

1. С помощью для петли и время как цикл
2. С помощью рекурсия

Использование цикла: Метод вычисления рядов Фибоначчи с использованием этого метода лучше по сравнению с рекурсивным методом. Этот метод использует Динамическое программирование, что работает, сохраняя число, сгенерированное до сих пор, а затем используя его для дальнейших вычислений.

Как число для n=1 и n=2 являются фиксированными, то есть, 0 и 1, то остальные числа в ряду могут быть вычислены с помощью логики:

f3 = f2 + f1
f4 = f3 + f2
f5 = f4 + f3
...
fn = fn-1 + fn-2

Эта логика может быть реализована как с помощью цикла for, так и с помощью цикла while в JavaScript.

Использование цикла for: 

Поскольку первые два значения ряда фиксированы, мы начинаем цикл с i = 2 и повторяем до тех пор, пока i

<script>
	const n = 10;
	
	// Create a new array of size 'n'
	var series = new Array(n);

	// Fills all places in array with 0
	series.fill(0);
	
	// Seed value for 1st element
	series[0] = 0;
	
	// Seed value for 2nd element
	series[1] = 1;
	
	for(let i = 2; i < n; i++) {

		// Apply basic Fibonacci formulae
		series[i] = series[i-1] + series[i-2];
	}

	// Print the series
	console.log(series);
</script>

Выход:

Использование цикла while:

<script>
	const n = 10;
	
	// Create a new array of size 'n'
	var series = new Array(n);
	
	// Fills all places in array with 0
	series.fill(0);
	
	// Seed value for 1st element
	series[0] = 0;
	
	// Seed value for 2nd element
	series[1] = 1;
	
	// Initialize the conditional variable
	let i = 2;
	while(i < n) {

		// Apply basic Fibonacci formulae
		series[i] = series[i-1] + series[i-2];
		
		// Increment the conditional variable
		i++;
	}
	
	// Print the series
	console.log(series);
</script>

Выход:

Используя рекурсию: рекурсия метод печати целого ряда Фибоначчи до определенного числа не рекомендуется, потому что рекурсия алгоритм сам по себе является затратным с точки зрения времени и сложности, и наряду с получение ряда Фибоначчи числа в такое-то положение, надо хранить их в массив, который вызывает рекурсивную функцию снова и снова для каждого элемента,  н раз!

Метод рекурсии может быть применен в JavaScript следующим образом.

<script>
	function fibonacci(n){
	if(n == 1) return 0; // Return value for n=1
	if(n == 2) return 1; // Return value for n=2
	
	// Recursive call
	return fibonacci(n-1) + fibonacci(n-2);
	}
	
	const n = 10;
	
	// Create a new array of size 'n'
	var series = new Array(n);

	// Fills all places in array with 0
	series.fill(0);
	
	for(let i = 1; i <= n; i++) {

		// Store i-th Fibonacci number
		series[i-1] = fibonacci(i);
	}

	// Print the series
	console.log(series);
</script>

Выход: