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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ZRZ_CFB
3 / 3 / 0
Регистрация: 01.01.2015
Сообщений: 95
Завершенные тесты: 1
#1

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

30.08.2015, 19:25. Просмотров 271. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.08.2015, 19:25     Экономия по времени
Посмотрите здесь:

Экономия памяти - C++
Скажите, будет ли второй вариант кода занимать меньше памяти? 1ый вариант: float a; f(a); 2ый вариант: #define a 5.33 ...

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

Разумная экономия
«Если человек экономит – значит у него сложности с деньгами». Знакомый стереотип? Почему-то экономию связывают с финансовыми трудностями и...

Экономия ресурсов - Программирование
Единственное что об этом знаю - то какие типы данных лучше устанавливать, не брать допустим под массив записей где есть диапазон 1..10 тип...

Рисование и экономия ресурсов - C++ Builder
Всем привет! На форме есть компонент типа TImage. На нем рисуется линия, например так: Image1-&gt;Picture-&gt;Bitmap-&gt;Canvas-&gt;MoveTo( X2...

Экономия памяти и справочные таблицы - MS Access
Всем привет! Я не так давно работаю в Access и никак не могу уяснить для себя вот какое дело: Допустим у меня есть таблица Животные. В...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kerry_Jr
Модератор
Эксперт PHP
2178 / 1974 / 689
Регистрация: 14.05.2014
Сообщений: 5,773
Записей в блоге: 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
563 / 277 / 37
Регистрация: 21.07.2015
Сообщений: 847
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
563 / 277 / 37
Регистрация: 21.07.2015
Сообщений: 847
30.08.2015, 20:00     Экономия по времени #6
Цитата Сообщение от ZRZ_CFB Посмотреть сообщение
Удалось продвинуться до 43 теста...
Может все же прочить статью и попробовать реализовать улучшенные методы? Это совсем не сложно, поверь мне.
Renji
1876 / 1274 / 290
Регистрация: 05.06.2014
Сообщений: 3,633
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
563 / 277 / 37
Регистрация: 21.07.2015
Сообщений: 847
30.08.2015, 23:42     Экономия по времени #8
Renji,
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2015, 11:59     Экономия по времени
Еще ссылки по теме:

Экономия ресурсов USER.EXE... - Visual Basic
Большой проект, куча форм, на них контролов, юзерконтролов и т.п. Задача этого действительно требует, уменьшить количество этого всего...

GPS велокомпьютер и экономия заряда аккумулятора - Программирование Android
хочу написать программу &quot;велокомпьютер&quot; с подсчетом пройденного расстояния и подсчетом средней и максимальной скорости. Все понятно и...

Экономия на самостоятельной сборке домашнего кинотеатра - Кинотеатры
Вот в данных темах очень часто обсуждается самостоятельная сборка не только акустических систем, но и домашних кинотеатров. И меня...

Экономия на AMD - миф или реальность? - Процессоры
Собираю системник с 0 ( до этого стоял древний комп на athlone, потом ноут на amdшке же). Собственно вопрос, как я понимаю игры все больше...


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

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

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