Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Etyuhibosecyu
Его Правительские Звания
-14 / 10 / 5
Регистрация: 13.07.2017
Сообщений: 593
Записей в блоге: 2
Завершенные тесты: 1
1

Фибоначчи - без рекурсии! - прошу прокомментировать

16.05.2018, 18:57. Просмотров 246. Ответов 1
Метки нет (Все метки)

Наверное, почти все, кто учился в школе и знает основы программирования, знают, что числа Фибоначчи вычисляются так:
C++
1
return fib(n - 1) + fib(n - 2);
Но почему-то никто не знает о другом способе. А может быть, он нерабочий?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static long double fib(unsigned int n) {
    if (n < 1) {
        return 0;
    }
    else if (n < 3) {
        return 1;
    }
    else {
        long double a[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 1;
        for (int i = 3; i <= n; i++) {
            a[0] = a[1];
            a[1] = a[2];
            a[2] = a[0] + a[1];
        }
        return a[2];
    }
}
Кода получилось намного больше, но этот способ никогда не должен приводить к переполнению стека, так как не использует рекурсию. Кроме того, мне кажется, он вычисляет быстрее, так каждый элемент вычисляется всего один раз. Прошу прокомментировать.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.05.2018, 18:57
Ответы с готовыми решениями:

Числа Фибоначчи без использования рекурсии и массивов
int a, b=0, c=1; cout&lt;&lt;&quot;Введите число Фибоначчи: &quot;&lt;&lt;endl; cin&gt;&gt;a; for(int i=2;i&lt;=(a-3);i++) {...

Почему вычисление числа Фибоначчи с помощью рекурсии медленнее, чем без нее?
Почему, к примеру вычисление числа Фибоначчи с помощью рекурсии, когда #include&lt;iostream&gt; using...

Рекурсия без рекурсии
Как известно с рекурсией связана маленькая скорость и проблема переполнения стека. Ее можно...

О 8 ферзях(Без рекурсии)
Пытаюсь сделать задачу о 8 ферзях без рекурсии. Сделал набросок, но работает как то криво. В чем...

Функция Аккермана без рекурсии
Задача: A(0, n) = n + 1; A(m, 0) = A(m–1, 1); при m &gt; 0; A(m, n) = A(m–1, A(m, n–1)); при m &gt;...

1
ПерС
431 / 356 / 322
Регистрация: 05.11.2013
Сообщений: 1,010
Записей в блоге: 6
Завершенные тесты: 1
16.05.2018, 19:25 2
Рекурсию всегда можно заменить на не-рекурсию.
Числа Фибоначчи - пример для рекурсии вообще не самый удачный, никто не виноват, что преподы другого не знают.
Коль скоро для вычисления очередного значения нужны только 2 предыдущих, можно обойтись просто тремя переменными и вообще без массивов, ну или массивом из 3 элементов, как ты сделал.
Вопрос-то в чём?
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.05.2018, 19:25

Сортировка слияниеим без рекурсии
Нужна сортировка слиянием без использования рекурсии. Помогите ...

Функция Аккермана без рекурсии
Возможно сделать функцию Аккермана НЕ рекурсивно, а циклически? Сложность с которой я столкнулся в...

Написать функцию без рекурсии
bool st(int a) { if(a==1) return true; else return ((a%5==0) ? st(a/5) : false); }


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru