Форум программистов, компьютерный форум CyberForum.ru

Экономия по времени - C++

Восстановить пароль Регистрация
 
ZRZ_CFB
3 / 3 / 0
Регистрация: 01.01.2015
Сообщений: 95
Завершенные тесты: 1
30.08.2015, 19:25     Экономия по времени #1
Приветствую всех!

Как сделать данную программу максимально быстрой, для прохождения теста в олимпиадном программировании.

Запинается на тесте №41, где лимит подскочил аж до 2000 мс. Самих тестов нет...

Идея программы такова, входной файл: Число Фибоначчи F(n);
Вывести число F(n) ряда последовательности Фибоначчи.
 Комментарий модератора 
Не отсылайте других пользователей в поиск и избегайте ссылок на поисковые системы (Google, Yandex и др.).


Код программы:

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
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <cstdio>
 
using namespace std;
 
int Fib(int i)
{
    int value = 0;
    if (i < 1) return 0;
    if (i == 1) return 1;
    return Fib(i - 1) + Fib(i - 2);
}
int main()
{
    ifstream cin("fib.in");
    ofstream cout("fib.out");
    int Fibonacci, i = 1;
    cin >> Fibonacci;
    for (i = 1; i < Fibonacci; i++) Fib(i + 1);
    
        cout << Fib(i+1);
    return 0;
}
Примеры входных / выходных файлов:

PHP
1
2
3
4
5
6
in: 1 out: 1
in: 2 out: 2
in: 3 out: 3
in: 4 out: 5
in: 5 out: 8
in: 6 out: 13
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.08.2015, 19:25     Экономия по времени
Посмотрите здесь:

C++ сравнение времени
Экономия памяти или борьба с точками. (что-то типа массива ссылок хотелось бы иметь) C++
Значение времени C++
Отсчет времени C++
Вывод времени C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kerry_Jr
Модератор
 Аватар для Kerry_Jr
1859 / 1655 / 577
Регистрация: 14.05.2014
Сообщений: 4,760
Записей в блоге: 1
Завершенные тесты: 5
30.08.2015, 19:35     Экономия по времени #2
ZRZ_CFB, я так полагаю, должен быть предел значений n (например, n <= 10000), какой он?
ZRZ_CFB
3 / 3 / 0
Регистрация: 01.01.2015
Сообщений: 95
Завершенные тесты: 1
30.08.2015, 19:36  [ТС]     Экономия по времени #3
Предел: 0 <= n <= 45.
shmkv
539 / 253 / 28
Регистрация: 21.07.2015
Сообщений: 756
30.08.2015, 19:40     Экономия по времени #4
ТС видел эту статью?
ZRZ_CFB
3 / 3 / 0
Регистрация: 01.01.2015
Сообщений: 95
Завершенные тесты: 1
30.08.2015, 20:00  [ТС]     Экономия по времени #5
shmkv, нет. Благодарю!

Добавлено через 12 минут
Удалось продвинуться до 43 теста...
А дальше опять ограничение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <fstream>
#include <cstdio>
 
using namespace std;
 
int Fib(unsigned int x)
{
    if (x <= 1) return 1;
    else return Fib(x - 1) + Fib(x - 2);
}
 
int main()
{
    ifstream cin("fib.in");
    ofstream cout("fib.out");
    int Fibonacci;
    cin >> Fibonacci;
    cout << Fib(Fibonacci);
    return 0;
}
Добавлено через 2 минуты
Тема закрыта!

Исправил.

Кому нужна быстрая программа, ловите:

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
#include <iostream>
#include <fstream>
#include <cstdio>
 
using namespace std;
 
unsigned long fib(unsigned int n) {
    if (n == 0) return 0;
    unsigned long previous = 0;
    unsigned long current = 1;
    for (unsigned int i = 1; i < n; ++i) {
        unsigned long next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}
int main()
{
    ifstream cin("fib.in");
    ofstream cout("fib.out");
    int Fibonacci;
    cin >> Fibonacci;
    cout << fib(Fibonacci+1);
    return 0;
}
shmkv
539 / 253 / 28
Регистрация: 21.07.2015
Сообщений: 756
30.08.2015, 20:00     Экономия по времени #6
Цитата Сообщение от ZRZ_CFB Посмотреть сообщение
Удалось продвинуться до 43 теста...
Может все же прочить статью и попробовать реализовать улучшенные методы? Это совсем не сложно, поверь мне.
Renji
1535 / 983 / 240
Регистрация: 05.06.2014
Сообщений: 2,963
30.08.2015, 23:30     Экономия по времени #7
Цитата Сообщение от ZRZ_CFB Посмотреть сообщение
Предел: 0 <= n <= 45.
Нет, я понимаю что не спортивно, но все же:
C++
1
2
3
4
5
unsigned long fib(unsigned int n)
{
    static const unsigned long table[48]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073};
    return table[n];
}
shmkv
539 / 253 / 28
Регистрация: 21.07.2015
Сообщений: 756
30.08.2015, 23:42     Экономия по времени #8
Renji,
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2015, 11:59     Экономия по времени
Еще ссылки по теме:

C++ Задержка времени
Экономия памяти C++
Предел времени C++

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

Или воспользуйтесь поиском по форуму:
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
31.08.2015, 11:59     Экономия по времени #9
Цитата Сообщение от ZRZ_CFB Посмотреть сообщение
Кому нужна быстрая программа, ловите:
Есть методы и покруче:
Определить F – 40-е число Фибоначчи
или
Последняя цифра чисел Фибоначчи
Yandex
Объявления
31.08.2015, 11:59     Экономия по времени
Ответ Создать тему
Опции темы

Текущее время: 21:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru