Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
ZRZ_CFB
3 / 3 / 1
Регистрация: 01.01.2015
Сообщений: 122
Завершенные тесты: 1
1

Экономия по времени

30.08.2015, 19:25. Просмотров 318. Ответов 8
Метки нет (Все метки)

Приветствую всех!

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

Запинается на тесте №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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.08.2015, 19:25
Ответы с готовыми решениями:

Экономия памяти
Скажите, будет ли второй вариант кода занимать меньше памяти? 1ый вариант: ...

Экономия памяти
Здравствуйте, уважаемые программисты! Как разместить информацию о числах из...

Экономия памяти при упаковке данных
Здравствуйте, уважаемые программисты! Есть такая задача: Задан упорядоченный...

Скорость или экономия памяти - что бы выбрали Вы?
...

Экономия трафика при передачи последовательности изображений в сети за счет эффективного кодирования
Всем добрый день! Есть такая задачка: мы берем последовательность изображений и...

8
Kerry_Jr
Эксперт PHP
2210 / 2006 / 940
Регистрация: 14.05.2014
Сообщений: 5,869
Записей в блоге: 1
Завершенные тесты: 5
30.08.2015, 19:35 2
ZRZ_CFB, я так полагаю, должен быть предел значений n (например, n <= 10000), какой он?
0
ZRZ_CFB
3 / 3 / 1
Регистрация: 01.01.2015
Сообщений: 122
Завершенные тесты: 1
30.08.2015, 19:36  [ТС] 3
Предел: 0 <= n <= 45.
0
shmkv
1207 / 430 / 59
Регистрация: 21.07.2015
Сообщений: 1,113
30.08.2015, 19:40 4
ТС видел эту статью?
0
ZRZ_CFB
3 / 3 / 1
Регистрация: 01.01.2015
Сообщений: 122
Завершенные тесты: 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;
}
0
shmkv
1207 / 430 / 59
Регистрация: 21.07.2015
Сообщений: 1,113
30.08.2015, 20:00 6
Цитата Сообщение от ZRZ_CFB Посмотреть сообщение
Удалось продвинуться до 43 теста...
Может все же прочить статью и попробовать реализовать улучшенные методы? Это совсем не сложно, поверь мне.
0
Renji
2114 / 1552 / 473
Регистрация: 05.06.2014
Сообщений: 4,505
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];
}
3
shmkv
1207 / 430 / 59
Регистрация: 21.07.2015
Сообщений: 1,113
30.08.2015, 23:42 8
Renji,
0
Ilot
Эксперт С++
1832 / 1190 / 342
Регистрация: 16.05.2013
Сообщений: 3,139
Записей в блоге: 5
Завершенные тесты: 1
31.08.2015, 11:59 9
Цитата Сообщение от ZRZ_CFB Посмотреть сообщение
Кому нужна быстрая программа, ловите:
Есть методы и покруче:
http://www.cyberforum.ru/post7053868.html
или
http://www.cyberforum.ru/post7965087.html
0
31.08.2015, 11:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2015, 11:59

Экономия памяти или борьба с точками. (что-то типа массива ссылок хотелось бы иметь)
У меня есть объект Point. И есть Объект Grup. В объекте Grup я выделил...

Как посчитать сколько времени прошло по заданному интервалу времени
Например сколько времени прошло от 10:00 до 9:59? часовой формат 23 часовой....

Полиморфизм времени выполнения/времени компиляции
Здравствуйте, подскажите, пожалуйста, литературу, где мне внятно можно узнать...


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

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

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