Числа Фибоначчи (этюд на C#)
Наверное многим студентам приходилось изучать рекурсию на примере вычисления чисел Фибоначчи. Задачка это безусловно академическая, и рекурсию она иллюстрирует явно хуже чем вычисление, скажем, факториалов, но она интересна тем, что имеет много решений разной степени извращенности. В этом посте – небольшой этюд на эту тему.
Думаю что никого не удивит “дефолтное” решение для вычисления N-го числа Фибоначчи:
static int fib(int n) < return n >1 ? fib(n - 1) + fib(n - 2) : n; > Также, есть достаточно “модная” форма записи этого решения которая использует Y-комбинатор:
Func fib = Y(f => n => n > 1 ? f(n - 1) + f(n - 2) : n); Где Y определен, к примеру, вот так:
static Func Y(Func f) < Funcg = null; g = f(a=>g(a)); return g; > Для больших N, такой подход непродуктивен. Как посчитать число N быстрее? Для начала давайте вспомним, почему например x*x считается быстрее чем Math.Pow(x,2) ? Потому что для целочисленной степени можно не только обойтись без рядов Тейлора, но также оптимизировать вычисление для больших степеней путем создания временных переменных. Например, x 4 можно считать как int y = x * x; return y * y; – и чем больше степень, тем больше экономия.
К чему это я? К тому что число Фибоначчи можно рассчитать с помощью следующей формулы:
Теперь понятно зачем нам целочисленное возведение в степень? Для матриц можно делать то же самое, только сначала нужно понять как это вообще делается. На просторах интеренета я нашел возможно идеальный алгоритм, который оптимизирует целочисленное возведение в степень. Прошу заметить, что в примере ниже степень имеет тип short .
public static long IntPower(int x, short power) < if (power == 0) return 1; if (power == 1) return x; int n = 15; while ((power = 0) n--; long tmp = x; while (--n > 0) tmp = tmp * tmp * (((power
Теперь осталось только определить матрицу 2×2. Тут можно было бы воспользоваться какой-то библиотечкой, но я решил написать самую простую возможную структуру:
struct mtx2x2 < public int _11, _12, _21, _22; public static mtx2x2 operator*(mtx2x2 lhs, mtx2x2 rhs) < return new mtx2x2 < _11 = lhs._11*rhs._11 + lhs._12*rhs._21, _12 = lhs._11*rhs._12 + lhs._12*rhs._22, _21 = lhs._21*rhs._11 + lhs._22*rhs._21, _22 = lhs._21*rhs._12 + lhs._22*rhs._22 >; > > После этого нужно было определить две константы которые нам пригодятся – ту матрицу которую мы будет возводить в степень и единичную матрицу:
private static readonly mtx2x2 fibMtx = new mtx2x2 ; private static readonly mtx2x2 identity = new mtx2x2 ; Теперь мы можем переписать метод IntPower() для матриц 2×2:
public static mtx2x2 IntPower(mtx2x2 x, short power) < if (power == 0) return identity; if (power == 1) return x; int n = 15; while ((power = 0) n--; mtx2x2 tmp = x; while (--n > 0) tmp = (tmp * tmp) * (((power
И определить новый метод для вычисления числа Фибоначчи:
static int fibm(short n)
Вот и все. Думаю что сравнивать производительность бессмысленно – у меня fib(40) считается 4 секунды, а fibm(40) выводится моментально. ■
Числа Фибоначчи
Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих:
1, 1, 2, 3, 5, 8, 13 и т. д.
То есть последовательность всегда начинается с двух единиц. А каждое следующее число является определяется по формуле:
Для определения чисел Фибоначчи часто используется рекурсивный алгоритм:
- Если n = 1 или n = 2, вернуть 1 (поскольку первый и второй элементы ряда Фибоначчи равны 1).
- Вызвать рекурсивно функцию с аргументами n-1 и n-2.
- Результат двух вызовов сложить и вернуть полученное значение.
Реализация с использованием рекурсии
Реализация на Си
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define _CRT_SECURE_NO_WARNINGS
#include
int fibonacci( int N) // рекурсивная функция
if (N == 1 || N == 2)
return 1; // первые 2 числа равны 1
return fibonacci(N — 1) + fibonacci(N — 2); // складываем предыдущие 2 числа
>
int main()
int N;
printf( «N=» );
scanf( «%d» , &N); // вводим число N
for ( int i = 1; i printf( «%d » , fibonacci(i));
getchar(); getchar();
return 0;
>
Результат выполнения
У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fibonacci(N) , то подсчитываются значения функции N-1 и для N-2 . Но если требуется вычислить fibonacci(N-1) , то значения для N-2 и N-3 вычисляются заново.
Поэтому поставленную задачу определения чисел Фибоначчи можно решить без использования рекурсии.
Реализация с использованием цикла
В этом алгоритме используется свойство, что для определения следующего числа Фибоначчи используются только два предыдущих значения.
Алгоритм при этом будет следующий
- Ввести номер N определяемого элемента.
- Проинициализировать два первых элемента a и b значениями 1, и если N
- Выполнять нижеследующие действия N-2 раза
- Сложить a и b, присвоив результат третьей переменной c.
- Поменять начальные значения: a = b, b = c
Реализация на Си
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include
int main()
int N;
printf( «N=» ); // вводим число N
scanf( «%d» , &N);
int a = 1, b = 1, c;
if (N printf( «1 » );
else
for ( int i = 3; i c = a + b; // вычисляем следующее число как сумму двух предыдущих
a = b; b = c; // перемещаем два предыдущих числа
>
printf( «%d » , b); // выводим последнее число
>
getchar(); getchar();
return 0;
>Как найти Числа Фибоначчи?
A103. Числа Фибоначчи
Ряд Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13,… (последовательность A000045 в OEIS) состоит из чисел, которые рекуррентно определяются как сумма двух предыдущих: Fn = Fn-2 + Fn-1. Ряд начинается с F0 = 0 и F1 = 1 и продолжается до бесконечности.Напишите программу, которая находит N-ное число Фибоначчи.
На входе
Целое число N в пределах 0 ≤ N ≤ 45.На выходе
Число Фибоначчи FN.Пример
На входе 8 На выходе 2194731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:Найти целое число k-порядковый номер числа фибоначчи
Дано целое число N(>1), являющееся числом Фибоначчи: N=Fk(число Фибоначчи Fk определяется следующим.Найти количество сложений для вычисления n-го числа Фибоначчи рекурсивным и обычным алгоритмом.
Найти количество сложений для вычисления n-го числа Фибоначчи рекурсивным и обычным алгоритмом. .
В типизированный файл занести числа Фибоначчи, не превосходящие заданного числа N
Создайте файл целых чисел, занося в него числа Фибоначчи, не превосходящие заданного числа N.Вывести числа Фибоначчи
#include<stdio.h> #include<math.h> #include <clocale> #include <locale.h> // Библиотека.
4877 / 3880 / 1609
Регистрация: 24.04.2014
Сообщений: 11,371
Сообщение от Hayit 
Как найти Числа Фибоначчи?
Сообщение от Hayit рекуррентно определяются как сумма двух предыдущих: Fn = Fn-2 + Fn-1. Ряд начинается с F0 = 0 и F1 = 1
Поиск «Фибоначчи» по этому форуму дает свыше 5000 ссылок. По-видимому, автору темы все они не подходят (только неясно почему: он такой тупой или такой ленивый или все вместе?).
Меню пользователя zer0mail Читать блог Регистрация: 28.10.2015
Сообщений: 93как сделать чтобы сразу выходила ответ а не по очереде
Например когда нажимаю на 8 ответ выглядит так 1 1 2 3 5 8 13 21
мне надо чтобы сразу ответ 211 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
#include #include int main() { unsigned int n,i,a1,a2,b; scanf_s("%d",&n); a1 = 1; a2 = 1; printf("%d %d ",a1,a2); for (i=3; in; i++) { printf("%d ", a1+a2); b = a1; a1 = a2; a2 = b + a1; } printf("\n"); _getch (); return 0; }2655 / 2230 / 240
Регистрация: 03.07.2012
Сообщений: 8,106
Записей в блоге: 1Напиши printf(«%d «, a2); после цикла. Неужели так трудно догадаться? Если реально трудно, то Си (++) не для вас, увы.
Регистрация: 27.01.2014
Сообщений: 784Сообщение от Jewbacabra Ряд начинается с F0 = 0 и F1 = 1
Т.е первым числом ряда является ноль или всё-таки отсчёт идёт с единицы?
F1 = 0
F2 = 1
F3 = 1
F4 = 2F1 = 1
F2 = 1
F3 = 2
F4 = 3Первый вариант или второй?
4877 / 3880 / 1609
Регистрация: 24.04.2014
Сообщений: 11,371Сообщение от kalonord Первый вариант или второй?
Третий
F0 = 0
F1 = 1
F2 = 1
F3 = 2
F4 = 3
В любом случае числа одни и те же, индексы только различаютсяРегистрация: 18.03.2016
Сообщений: 1Как найти Числа Фибоначчи?
В загруженном файле представлены два новых способа получения точного ответа на вопрос ТС.
Очень верится, что программистов заинтерисует статья и, возможно, они по своей инициативе
предримут попытки для создания программ на разных языках. К месту скажу — я не программист.P. S. Не в тему. Я не вижу кнопки Спасибо (а хотел бы это сказать) под тем или иным сообщением.
Помогите разобраться.Странно, загрузить файл не дает администрация.
Спасибо за доброе действие. Я уже и пожалел, что здесь вчера зарегистрировался.
Будьте здоровы!Рекурсивное нахождение чисел Фибоначчи на C++
Задачи по вычислению числа из ряда чисел Фибоначчи очень часто встречаются при изучении программирования на языке C++. В этой статье я расскажу об одном алгоритме, который может решить эту задачу. Если Вас интересуют другие задачи, то загляните в раздел с решениями задач по программированию.
Числа Фибоначчи — это числовая последовательность, в которой каждый следующий член равен сумме двух предыдущих. Первые два члена равны единице. Нулевой член равен нулю, но чаще всего его не рассматривают как элемент последовательности, и тогда ряд чисел Фибоначчи имеет вид: 1, 1, 2, 3, 5, 8, 13, 21, … — такой вид он имеет и в отрицательную сторону с отрицательным знаком.
Пример последовательности от -5-го до 5-го члена: -5, -3, -2, -1, -1, 0, 1, 1, 2, 3, 5
В задачах обычно требуется найти n-ый член последовательности.
Рекурсивное решение на C++
Очень часто рекурсию в программировании показывают на примере вычисления чисел Фибоначчи рекурсивным алгоритмом. Такой алгоритм довольно прост, но время выполнение растет по экспаненте при увеличении n. Поэтому алгоритм работает медленно при больших n, а также может произойти переполнение стека(Stack Overflow).
Для решения создадим функцию f(n), в качестве аргумента она будет получать число n. Эта функция будет возвращать число, которое будет равно f(n-1) + f(n-2). То есть она вызывает себя 2 раза из самой себя.
unsigned long long int f(int n)
Теперь добавим возвращемое значение для f(0), f(1), f(2), чтобы при вызове функции с такими агрументами функция прекращала вызывать себя и выдавала значение. Для f(0) возвращаемое значение будет 0. Для f(1) и f(2) — 1.
unsigned long long int f(int n)
Обратите внимание, функция возвращает значение с типом unsigned long long int. Это позволит ей выводить огромные числа (о т 0 до 18 446 744 073 709 551 615 ), а значит она сможет работать с большими n.
Таким образом данная функция вычисляет n-ое число из ряда чисел Фиббоначи. Функция работает только с n >= 0.
В ходе работы функция вызывает сама себя, раскладывается, пока не вызовет f(1) или f(2), которые тут же возвратят 1 и не будут делать больше ничего. После этого функция обратно «складывается».
Для примера напишем программу с вызовом функции f() с аргументом 5 и выведем результат.
#include using namespace std; unsigned long long int f(int n) < if(n == 0) return 0; if(n == 1 || n == 2) return 1; return f(n-1)+f(n-2); >int main()
Результат выполнения программы
Вычисленное число Фибоначчи
Под капотом всё происходило примерно так: функция f(5) вызвала 2 функции f(4) и f(3); функция f(4) вызвала функции f(3) и f(2), а функция f(3) вызвала функции f(2) и f(1) и так далее… Но, для наглядности посмотрите на рисунок.
Вызовы функции f()
Стрелочка, выходящая из прямоугольника с функцией, показывает возвращаемое значение.
Для вас это может быть интересно:
Раздел: Алгоритмы Метки: C++, алгоритм, программирование, рекурсия, решение, фибоначчи, числа
Рекурсивное нахождение чисел Фибоначчи на C++ : 1 комментарий
- Иван 08.03.2018 В обратную сторону у ряда Фибоначчи знак чередуется, то есть ваш пример последовательности от -5-го до 5-го члена должен иметь вид: 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5
Добавить комментарий Отменить ответ
Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.
- Qt (4)
- SEO (5)
- Администрирование (4)
- Алгоритмы (6)
- Заработок (1)
- Операционные системы (4)
- Ответы (2)
- Программирование (23)
- Сайтостроительство (11)
- Продвинутая работа с массивами PHP 05.08.2021
- Использование SSH: исполнение, выгрузка и загрузка файлов по SSH 02.08.2021
- Краткий гайд по командам Composer для PHP 26.01.2021
- Как найти сумму и произведение элементов массива на C++ 09.12.2020
- Как вывести неповторяющиеся элементы массива на C/C++ 09.12.2020
- Чынгыз к записи Как найти сумму и произведение элементов массива на C++
- Чынгыз к записи Как найти сумму и произведение элементов массива на C++
- Di к записи Создание Excel документа на PHP (генерация .xls файлов)
- Илья к записи Русские символы(буквы) при вводе/выводе в консоль на C++
- LedsHack к записи Найти максимальный и минимальный элемент массива на C++