Числа Фибоначчи

@Jorka · Регистрация: 25.07.2020

Студворк — интернет-сервис помощи студентам

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

Последовательность Фибоначчи задаётся следующим образом. F(0)=F(1)=1, для всех N>1 F(N)=F(N-1)+F(N-2). Вам задано целое число N, 1 <= N <= 10**4.
Вычислите остаток от деления F(N) на 10^6+3

Sample Input 1:
1
Sample Output 1:
1
Sample Input 2:
7
Sample Output 2:
21
Sample Input 3:
2020
Sample Output 3:
735440

Вот что у меня

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll fib(ll s)
{
    if (s == 1 || s == 0)
    {
        return 1;
    }
    return fib(s-1) + fib(s-2);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    cout << fib(n) % 1000003;
    return 0;
}

Никак не пойму как ускорить или что сделать

Добавлено через 1 минуту
Failed test #3 of 20. Time limit exceeded

Добавлено через 19 секунд
Понял, из-за скорости всё же

@alexu_007 · 11.08.2020, 20:22

Это не ограничение, которое можно убрать.

@ivan_proger · 15.08.2020, 23:27

Jorka, Вот ещё мой вариант программы:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main(int argc, char** argv) {
    int n;
    cin>>n;
    long double a = 1;
    long double b = 1;
    long double c = 0;
    int i = 0;
    while (i!=n){
 
        a=b;
        b=c;
        c=a+b;
        ++i;
        cout<<endl<<c<<endl;
    }
    cout<<endl<<c<<endl;
    system("pause");
    return 0;
}

@Jorka · 16.08.2020, 02:23 **[ТС]**

ivan_proger, знаю такой, для памяти

Новые блоги и статьи Все статьи Все блоги /
SUNO Ai - Река Без Дна zorxor 31.07.2026 Автор стихотворения - астрофизик Марина Катыс Ссылка на сгенерированную музыкальную композицию: https:/ / suno. com/ song/ 6f6e5464-b290-4650-be6c-44c85f8d8013 Я говорю, что Время- как вода течет. . .	Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,316
	11.08.2020, 20:22
	Это не ограничение, которое можно убрать. 0

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302
	16.08.2020, 02:23 [ТС]
	ivan_proger, знаю такой, для памяти 0