Как найти числа фибоначчи в c

Числа Фибоначчи на C++ [дубликат]

Решаю задачу на сайте. Нужно написать программу для вычисления чисел Фибоначчи. Написал первую программу, сайт сказал, что она выполнялась слишком долго и была прервана. Переделал решение. У меня всё работает, но сайт почему-то говорит, что программа выдаёт ошибку в процессе выполнения. Проблема во мне или в тестирующей системе?

#include using namespace std; int fib(int n)< int arr[n]; for(int i=2;i <=n;i++)< arr[i] = arr[i-1] + arr[i-2]; >return arr[n]; > int main()< int n; cin >> n; cout

Вычисление чисел Фибоначчи

Что такое числа Фибоначчи и как написать программу вычисления последовательности? Разберём три примера на языке Java.

Числа Фибоначчи — это числа такой последовательности, в которой первые два элемента — 0 и 1, а каждый последующий элемент равен сумме двух предшествующих. Выглядит это так:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, … 

Примечание Иногда 0 опускается, и в этом случае ряд начинается с 1, но мы будем использовать последовательность с 0 на первой позиции.

Формула записывается следующим образом:

Вычисление ряда Фибоначчи — стандартная задача, которую задают на собеседованиях, чтобы проверить кандидата на понимание алгоритмов. Не так популярна, как сортировка, но всё же.

Давайте вычислим ряд и его отдельные элементы, использовав для этого язык Java.

Вычислить ряд Фибоначчи циклом

Предположим, что нам нужно вывести на экран первые десять чисел последовательности Фибоначчи. Мы помним, что:

• первый элемент ряда — 0, второй — 1;
• каждый последующий — сумма двух предыдущих.

Тогда наша последовательность будет иметь такой вид:

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

Но нам нужно вывести результат с использованием программы. Держите код с объяснениями в комментариях:

public class Main < public static void main(String[] args) < //Объявляем переменные при известных первых двух: int num0 = 0; int num1 = 1; int num2; //Первые две переменные выводим вне цикла: System.out.print(num0 + " " + num1 + " "); for(int i = 3; i > > 

Выполнение завершится на десятом элементе. Количество элементов при этом можно менять, изменив значение в условиях цикла.

Найти число Фибоначчи через рекурсию

Рекурсивная функция — это такая функция, которая вызывает саму себя. Она также неплохо отрабатывает в алгоритмических задачах вроде чисел Фибоначчи, но ей требуется больше времени.

Почему так происходит? Всё дело в том, что рекурсивная функция приводит к многоразовому вызову одних и тех же операций. Именно из-за этого её не рекомендуется использовать, но если уж на собеседовании прозвучит такая задача, вы будете готовы.

Рассмотрим пример, в котором нам нужно получить n-ое число в ряде Фибоначчи:

public int fibonacciValue(num) < if (num else if (num == 2) < return 1; >else < return fibonacciValue(num - 1) + fibonacciValue(num - 2); >> 

Если в качестве num задать большое значение, программа зависнет.

Тип int в Java может хранить значения до 2147483647, так что вычислить получится лишь первые 46 чисел Фибоначчи. Тип long хранит до 9223372036854775807, а это 91 число Фибоначчи. Класс BigInteger призван работать с действительно большими значениями, вот только само выполнение программы это никак не ускорит.

Использовать для вычисления Stream

Stream в Java — это компонент для самостоятельной внутренней итерации своих же элементов. Подробнее о нём вы можете почитать в нашей статье о Java Stream API.

И, разумеется, Stream подходит для вычисления элементов последовательности Фибоначчи:

Stream.iterate(new int[], arr -> new int[]) //Задаём лимит значений: .limit(num) //Отбираем по первому элементу каждого массива: .map(y -> y[0]) //Выводим в консоль: .forEach(x -> System.out.println(x)); 

В данном примере метод iterate() будет возвращать упорядоченный поток, ограниченный лимитом в num значений и созданный с применением функции к начальному массиву arr . В консоль будет выведено следующее:

А так мы получим сумму чисел последовательности по элемент num включительно:

int fibonacciValuesSum = Stream.iterate(new int[], arr -> new int[]) .limit(num) .map(y -> y[0]) .mapToInt(Integer::intValue) .sum(); System.out.println(fibonacciValuesSum); 

Математический тест

Любите математику? Попробуйте решить наш математический тест:

Как найти числа фибоначчи в c

Последовательность чисел Фибоначчи определяется формулой F_n = F_n-1 + F_n-2 . То есть, следующее число получается как сумма двух предыдущих.

Первые два числа равны 1 , затем 2(1+1) , затем 3(1+2) , 5(2+3) и так далее: 1, 1, 2, 3, 5, 8, 13, 21. .

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

Напишите функцию fib(n) которая возвращает n-е число Фибоначчи.

function fib(n) < /* ваш код */ >alert(fib(3)); // 2 alert(fib(7)); // 13 alert(fib(77)); // 5527939700884757

P.S. Все запуски функций из примера выше должны работать быстро. Вызов fib(77) должен занимать не более доли секунды.

Сначала решим через рекурсию.

Числа Фибоначчи рекурсивны по определению:

function fib(n) < return n alert( fib(3) ); // 2 alert( fib(7) ); // 13 // fib(77); // вычисляется очень долго

При больших значениях n такое решение будет работать очень долго. Например, fib(77) может повесить браузер на некоторое время, съев все ресурсы процессора.

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

Например, посмотрим на отрывок вычислений для fib(5) :

. fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) . 

Здесь видно, что значение fib(3) нужно одновременно и для fib(5) и для fib(4) . В коде оно будет вычислено два раза, совершенно независимо.

Полное дерево рекурсии:

Можно заметить, что fib(3) вычисляется дважды, а fib(2) – трижды. Общее количество вычислений растёт намного быстрее, чем n , что делает его огромным даже для n=77 .

Можно это оптимизировать, запоминая уже вычисленные значения: если значение, скажем, fib(3) вычислено однажды, затем мы просто переиспользуем это значение для последующих вычислений.

Другим вариантом было бы отказаться от рекурсии и использовать совершенно другой алгоритм на основе цикла.

Вместо того, чтобы начинать с n и вычислять необходимые предыдущие значения, можно написать цикл, который начнёт с 1 и 2 , затем из них получит fib(3) как их сумму, затем fib(4) как сумму предыдущих значений, затем fib(5) и так далее, до финального результата. На каждом шаге нам нужно помнить только значения двух предыдущих чисел последовательности.

Вот детальные шаги нового алгоритма.

// a = fib(1), b = fib(2), эти значения по определению равны 1 let a = 1, b = 1; // получим c = fib(3) как их сумму let c = a + b; /* теперь у нас есть fib(1), fib(2), fib(3) a b c 1, 1, 2 */

Теперь мы хотим получить fib(4) = fib(2) + fib(3) .

Переставим переменные: a,b , присвоим значения fib(2),fib(3) , тогда c можно получить как их сумму:

a = b; // теперь a = fib(2) b = c; // теперь b = fib(3) c = a + b; // c = fib(4) /* имеем последовательность: a b c 1, 1, 2, 3 */

Следующий шаг даёт новое число последовательности:

a = b; // now a = fib(3) b = c; // now b = fib(4) c = a + b; // c = fib(5) /* последовательность теперь (на одно число больше): a b c 1, 1, 2, 3, 5 */

…И так далее, пока не получим искомое значение. Это намного быстрее рекурсии и не требует повторных вычислений.

function fib(n) < let a = 1; let b = 1; for (let i = 3; i return b; > alert( fib(3) ); // 2 alert( fib(7) ); // 13 alert( fib(77) ); // 5527939700884757

Цикл начинается с i=3 , потому что первое и второе значения последовательности заданы a=1 , b=1 .

Находим N'е число Фибоначчи тремя способами за приемлемое время: основы динамического программирования

Очень часто на разнообразных олимпиадах попадаются задачи вроде этой, которые, как думается на первый взгляд, можно решить с помощью простого перебора. Но если мы подсчитаем количество возможных вариантов, то сразу убедимся в неэффективности такого подхода: например, простая рекурсивная функция, приведенная ниже, будет потреблять существенные ресурсы уже на 30-ом числе Фибоначчи, тогда как на олимпиадах время решения часто ограничено 1-5 секундами.

int fibo(int n) < if (n == 1 || n == 2) < return 1; >else < return fibo(n - 1) + fibo(n - 2); >> 

Давайте подумаем, почему так происходит. Например, для вычисления fibo(30) мы сначала вычисляем fibo(29) и fibo(28). Но при этом наша программа «забывает», что fibo(28) мы уже вычисляли при поиске fibo(29).

Основная ошибка такого подхода «в лоб» в том, что одинаковые значения аргументов функции исчисляются многократно — а ведь это достаточно ресурсоемкие операции. Избавиться от повторяющихся вычислений нам поможет метод динамического программирования — это прием, при использовании которого задача разбивается на общие и повторяющиеся подзадачи, каждая из которых решается только 1 раз — это значительно повышает эффективность программы. Этот метод подробно описан в нашей статье, там же есть и примеры решения других задач.

Самый просто вариант улучшения нашей функции — запоминать, какие значения мы уже вычисляли. Для этого нужно ввести дополнительный массив, который будет служить как бы «кэшем» для наших вычислений: перед вычислением нового значения мы будем проверять, не вычисляли ли его раньше. Если вычисляли, то будем брать из массива готовое значение, а если не вычисляли — придётся считать его на основе предыдущих и запоминать на будущее:

int cache[100]; int fibo(int n) < if (cache[n] == 0) < if (n == 1 || n == 2) < cache[n] = 1; >else < cache[n] = fibo(n - 1) + fibo(n - 2); >> return cache[n]; > 

Так как в данной задаче для вычисления N-ого значения нам гарантированно понадобится (N-1)-е, то не составит труда переписать формулу в итерационный вид — просто будем заполнять наш массив подряд до тех пор, пока не дойдём до нужной ячейки:

cache[0] = 1; cache[1] = 1; for (int i = 2; i cout 

//Два предыдущих значения: int cache1 = 1; int cache2 = 1; //Новое значение int cache3; for (int i = 2; i через итерацию потеряет актуальность cache2, т.е. он и должен стать cache1 //Иными словами, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n). //Пусть N=n+1 (номер, который мы вычисляем на следующей итерации). Тогда n-2=N-3, n-1=N-2, n=N-1. //В соответствии с новыми реалиями мы и переписываем значения наших переменных: cache1 = cache2; cache2 = cache3; > cout 

cache[0] = 1; cache[1] = 1; for (int i = 2; i cout 

int x = 1; int y = 1; for (int i = 2; i < n; i++) < y = x + y; x = y - x; >cout 

const double SQRT5 = sqrt(5); const double PHI = (SQRT5 + 1) / 2; int fibo(int n)< return int(pow(PHI, n) / SQRT5 + 0.5); >