Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.87/501: Рейтинг темы: голосов - 501, средняя оценка - 4.87
0 / 0 / 0
Регистрация: 10.04.2018
Сообщений: 3

Вывести n-е число Фибоначчи

11.04.2018, 22:35. Показов 96384. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите написать программу, что бы выводилось n-ое число ряда чисел Фибоначчи на экран
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.04.2018, 22:35
Ответы с готовыми решениями:

Вывести остаток от деления НОД чисел F(i) и F(j) на 10^9. (F - Число Фибоначчи)
Последовательностью Фибоначчи называется последовательность чисел F0 = 0, F1 = 1, … , Fk = Fk-1 + Fk-2, (k > 1). Требуется найти...

Дано число А. Проверить – это число Фибоначчи или нет
Ребята, помогите решить задачу по целочисленной арифметике, надо написать код на c++. Очень надо, помогите, пожалуйста. Собственно, задача:...

Написать программу, которая определяет число Фибоначчи под номером N и проверяет, является ли это число возрастающим
Доброго времени! Есть задача: "Написать программу, которая определяет число Фибоначчи под номером N и проверяет, является ли это...

12
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
11.04.2018, 23:17
1. Пункт 4.7 правил читали?
2. Про фибоначчи даже здесь, на форуме, вагон и маленькая тележка... Не по глазам?
1
7438 / 5030 / 2892
Регистрация: 18.12.2017
Сообщений: 15,692
12.04.2018, 00:46
для ряда 0, 1, 1, 2, 3, 5, 8, 13 ...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream> 
using namespace std;
 
int f(int n) 
{
    if ( n == 1 || n == 2) return (n -1); 
    return f(n-1) + f(n-2); 
}
 
int main()
{
    int n;    
    cout << "n="; cin >> n;       
    cout <<f(n)<<" ";    
    cout <<endl;
system("pause");
return 0;
}
1
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
05.05.2018, 20:43
Yetty, здравствуйте Просто хотел добавить, что ваша программа полностью верна, однако дело в том, что я немного увлекаюсь олимпиадным программированием и сталкивался с такой проблемой, что рекурсия для данной задачи, при больших n, будет работать очень медленно и это я сам ощутил по некоторым непройденным по времени тестам некоторых похожим задач, включая эту. Поэтому, просто хотел добавить, что лучше пользоваться арифметическими операциями (они намного быстрее) как, например, в кодах ниже:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
 
using namespace std;
 
int f(int n)
{
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; i++)
    {
        a = a + b;
        b = a - b;
    }
    return a;
}
 
int main()
{
    int n;
    cin >> n;
    cout << f(n) << "\n";
    system("pause");
    return 0;
}
Или так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
 
    using namespace std;
 
int f(int n) {
    int a, b, sum, count;
    a = count = sum = 0;
    b = 1;
    while (count < n) {
        sum = a + b;
        a = b;
        b = sum;
        count++;
    }
    return a;
}
 
int main() {
    int n;
    cin >> n;
    cout << f(n) << "\n";
    system("pause");
    return 0;
}
P.S. Кстати, это, также, касается многих других последовательностей, для которых существуют похожие законы формирования.
5
0 / 0 / 0
Регистрация: 23.11.2021
Сообщений: 17
02.12.2021, 12:09
круто
0
0 / 0 / 0
Регистрация: 20.10.2021
Сообщений: 1
11.02.2022, 21:00
Добавлено через 7 минут
Fixer_84, А можешь, пожалуйста, пояснить, почему a = a+b и b = b-a, как это вообще работает?
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
12.02.2022, 07:05
Цитата Сообщение от Artyom_BS Посмотреть сообщение
Fixer_84, А можешь, пожалуйста, пояснить, почему a = a+b и b = b-a, как это вообще работает?
Не в силах сам подставить в формулы а=5, b=3 (для примера)?

Добавлено через 1 минуту
А заодно и сами формулы внимательно прочитать...
0
19 / 13 / 6
Регистрация: 25.05.2022
Сообщений: 71
25.05.2022, 15:48
Переделал немного код Fixer_84, Теперь работает с отрицательными числами + немного проверок ввода.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
 
long long CalcFib(short N)
{
    long long a = 0;
    long long b = 1;
 
    if (N >= 0)    // Положительные
    {
        for (int i = 0; i < N; i++)
        {
            a = a + b;
            b = a - b;
        }
    }
    else    // Отрицательные
    {
        for (int i = 0; i > N; i--)
        {
            a = b - a;
            b = b + (-a);
        }
    }
 
    return a;
}
 
int main()
{
    setlocale(0, "ru");
 
    const int NUM_MIN = -40, NUM_MAX = 40;
    int inputNum;
    std::string endNum = "";
 
    while (true)
    {
        system("cls");    // Чистим консоль
 
        std::cin.unsetf(std::ios::skipws);    // Не игнорить Space, Tab и Еnter
        std::cout.width(3);    // Ширина вывода не меньше 3х символов
 
 
        std::cout << "Введите N элемента последовательности чисел Фибоначчи [" << NUM_MIN << "-" << NUM_MAX << "]: ";
 
        if (std::cin >> inputNum && std::cin.peek() == '\n' && inputNum >= NUM_MIN && inputNum <= NUM_MAX)
        {
            if (abs(inputNum) / 10 % 10 == 1)    // от 10 до 19
            {
                endNum = "ый";
            }
            else if (abs(inputNum) == 0 || abs(inputNum) % 10 == 2 || abs(inputNum) % 10 == 6 || abs(inputNum) % 10 == 7 || abs(inputNum) % 10 == 8 || abs(inputNum) % 100 == 40)    // 0, заканивается на 2,6,7,8,40
            {
                endNum = "ой";
            }
            else if (abs(inputNum) % 10 == 3)    // заканчивается на 3
            {
                endNum = "ий";
            }
            else    // остальные числа
            {
                endNum = "ый";
            }
        }
        else
        {
            std::cin.clear();    // Очищаем флаг ошибки
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');    // Пропуск до конца строки
 
            continue;    // Перезапускаем цикл
        }
 
        std::cout << "\n" << inputNum << endNum << " элемент = " << CalcFib(inputNum) << "\n\n";
 
        system("pause");
    }
}
0
0 / 0 / 0
Регистрация: 30.06.2022
Сообщений: 4
08.08.2022, 15:43
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
 
using namespace std;
 
int main()
{
    int a, fib_1, fib_2, fib_summ, n, res;
    cin >> a;
    fib_1 = 0;
    fib_2 = 1;
    fib_summ = 1;
    n = 0;
    res = -1;
    while (fib_1 <= a)
    {
        fib_summ = fib_1 + fib_2;
        fib_1 = fib_2;
        fib_2 = fib_summ;
        n += 1;
        if (fib_1 == a)
        {
            res = n;
        }
        else if (a == 0)
        {
            res = -1;
        }
    }
    cout << res;
}
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6128 / 2823 / 1038
Регистрация: 01.06.2021
Сообщений: 10,291
08.08.2022, 19:43
Цитата Сообщение от Fixer_84 Посмотреть сообщение
рекурсия для данной задачи, при больших n, будет работать очень медленно
Рекурсия всегда работает медленнее цикла и об этом уверен знает сам Yetty. Но дело в том, что такие задания на числа Фибоначчи или факториал дают студентам во время прохождения рекурсии. И когда падаван покажет мастеру решение через циклы, то он это не одобрит, по головке не погладит и не скажет "ай маладэц, какой ты умный". Тут на форуме есть очень много приколистов, которые специально пишут решения сложными методами, чтобы эти халявщики спалились при сдаче кода. Но Yetty не такой, всегда старается помочь и пишет просто и внятно.
Я это к тому, что вам не нужно ему рассказать, что ваш код будет быстрее, чем ваш. Он это и сам знает.
Лучше всех в данной теме ответил zer0mail:
Цитата Сообщение от zer0mail Посмотреть сообщение
Про фибоначчи даже здесь, на форуме, вагон и маленькая тележка...
На форуме полно тем про этот ряд. Fixer_84, и даже не раз встречались реализации через цикл, как вот у вас. Более того, тут даже проводились целые научные дискуссии, рассуждали формулу Бине, разные методы оптимизаций линейных рекуррентных последовательностей. Причем, не только в разделе в С++, но и в Java и в других разделах.
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
08.08.2022, 20:08
Royal_X, так прикол не в том, что у рекурсии какие-то там затраты на вложенные вызовы с сохранениями-восстановлениями контекста проигрывают циклу.
А прикол в том, что данная конкретная рекурсивная функция поиска Фибоначчи делает двойную или какой там порядок... работу! Проблема в том что некрасиво делать вызов f(n-2) в коде Yetty, ибо это значение уже считалось!
Вот и всё.
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6128 / 2823 / 1038
Регистрация: 01.06.2021
Сообщений: 10,291
08.08.2022, 20:31
Kuzia domovenok, ну так поправить можно было его код, а не предлагать новый, не связанный с рекурсией. А вообще, нужно было оставить все как есть и дать возможность ТС воспользоваться поиском по форуму.

Добавлено через 2 минуты
Вообще, в учебных примерах встречается такой код:

C++
1
2
3
4
5
6
7
8
int fibonacci(int count)
{
    if (count == 0)
        return 0; // base case (termination condition)
    if (count == 1)
        return 1; // base case (termination condition)
    return fibonacci(count-1) + fibonacci(count-2);
}
взято из https://www.learncpp.com/cpp-tutorial/recursion/

Добавлено через 1 минуту
там же рассказывается о мемоизации

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
 
// h/t to potterman28wxcv for a variant of this code
int fibonacci(int count)
{
    // We'll use a static std::vector to cache calculated results
    static std::vector<int> results{ 0, 1 };
 
    // If we've already seen this count, then use the cache'd result
    if (count < static_cast<int>(std::size(results)))
        return results[count];
    else
    {
        // Otherwise calculate the new result and add it
        results.push_back(fibonacci(count - 1) + fibonacci(count - 2));
        return results[count];
    }
}
 
// And a main program to display the first 13 Fibonacci numbers
int main()
{
    for (int count { 0 }; count < 13; ++count)
        std::cout << fibonacci(count) << ' ';
 
    return 0;
}
Добавлено через 9 минут
Цитата Сообщение от JerryFernan Посмотреть сообщение
Вывести n-е число Фибоначчи
А вообще ТС просит вывести не весь ряд, а только n-е число.
линейной рекуррентной последовательности есть точная формула для вывода n-го члена без вычисления предыдущих членов. Для Фибоначчи это формула Бине.
Там, конечно, есть квадратный корень, который немного усложняет задачу. Но решение существует.
Читаем https://habr.com/ru/post/645829/
А также темы (там есть очень хорошие коды):
Найти число Фибоначчи по порядковому номеру
Рассчитать 50-е число Фибоначчи, не считая всех предыдущих

Добавлено через 5 минут
Цитата Сообщение от Fixer_84 Посмотреть сообщение
int f(int n)
{
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; i++)
    {
        a = a + b;
        b = a - b;
    }
    return a;
}
как по мне вот этот вариант лучше (без медленного вычитания):

C++
1
2
3
4
5
6
7
8
9
10
11
int fib(int n)
{
    int c = 0, p = 1, q;
    for (int i = 1; i <= n; ++i)
    {
        q = c + p;
        p = c;
        c = q;
    }
    return c;
}
0
10 / 9 / 1
Регистрация: 23.11.2019
Сообщений: 159
08.08.2022, 20:32
Цитата Сообщение от Artyom_BS Посмотреть сообщение
Fixer_84, А можешь, пожалуйста, пояснить, почему a = a+b и b = b-a, как это вообще работает?
а и б изначально инициализированы базовыми значениями, через
a = a+b - новый член ряда
b = b-a - прошлый член ряда, т.е. значение а до суммирования
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
08.08.2022, 20:32
Помогаю со студенческими работами здесь

Дано целое число. Вывести его строку-описание вида «отрицательное чет-ное число», «нулевое число», «положительное нечетное число» и т. д.
Дано целое число. Вывести его строку-описание вида «отрицательное чет-ное число», «нулевое число», «положительное нечетное число» и т. д. ...

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

Число Фибоначчи, циклы.
Прошу помочь с решением... Нужно сформировать все числа Фибоначчи не превышающие заданное число. Заранее спасибо..

Определить F – 40-е число Фибоначчи
Числа Фибоначчи (Fn) определяются формулами: F0 = F1 = 1; Fn = Fn-1 + Fn-2 при n = 2, 3,… Определить F – 40-е ...

Число Фибоначчи номер N
Требуется найти число Фибоначчи номер N, по модулю 1000000000. Числа Фибоначчи — элементы числовой последовательности 0, 1, 1, 2, 3,...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru