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

Оптимизация робота - C++

Восстановить пароль Регистрация
 
Deligor
1 / 1 / 0
Регистрация: 12.04.2014
Сообщений: 30
15.08.2014, 21:26     Оптимизация робота #1
Написал вот эту задачу:

Робот
Имя входного файла: robot.in
Имя выходного файла: robot.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
В исследовательской лаборатории фирмы Robots&Co разработали новую мо-
дель робота. Главной особенностью данной модели робота является то, что он ра-
ботает по заранее заданной программе, в которой могут присутствовать команды:
сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу
строго последовательно и, дойдя до конца программы, останавливается. Специа-
листы из Robots&Co заинтересовались вопросом, сколько существует различных
программ, состоящих из K инструкций, таких, что робот, выйдя из начала ко-
ординат, придет в точку с координатами (X, Y ). Оси координат располагаются
параллельно сторонам света, и единица измерения, соответствует одному шагу
робота. Напишите программу, которая дает ответ на этот вопрос.

Формат входных данных
Во входном файле находятся три числа K, X и Y (0 6 K 6 16, |X|, |Y | 6 16),
разделенные пробелами.

Формат выходных данных
В выходной файл ваша программа должна поместить одно число - количество
программ для робота.

Вот мой код:
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 <fstream>
#include <cmath>
 
using namespace std;
 
ifstream fin;
ofstream fout;
 
int F(int x, int y, int k){
    if(abs(x)>k || abs(y)>k || abs(x+y)>k)
        return 0;
    if(k==0)
        if(x==0 && y==0)
            return 1;
        else
            return 0;
    return F(x-1, y, k-1) + F(x+1, y, k-1) + F(x, y-1, k-1) + F(x, y+1, k-1);
}
 
int main(){
    fin.open("robot.in");
    fout.open("robot.out");
    int K, X, Y;
    fin >> K >> X >> Y;
    fout << F(X, Y, K);
    return 0;
}
Выдает Time Limit на 6 тесте.
Уважаемые знатоки, подскажите, как оптимизировать программу. Заранее благодарю!

Добавлено через 9 минут
Цитата Сообщение от Deligor Посмотреть сообщение
Формат входных данных
Во входном файле находятся три числа K, X и Y (0 6 K 6 16, |X|, |Y | 6 16),
разделенные пробелами.
Здесь должно быть "три числа K, X и Y (0 <= K <= 16, |X|, |Y| <= 16)". Кодировка сломалась...
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.08.2014, 21:26     Оптимизация робота
Посмотрите здесь:

Робота с строками в С++ C++
Робота со строками в с++ 3.1 C++
C++ Лабораторная робота!
C++ Робота з файлами
Робота со строками C++
робота с текстом C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
15.08.2014, 21:27     Оптимизация робота #2
Первая же ссылка ведет на разбор.
http://www.problems.ru/view_problem_...w.php?id=98716
BlackIce
309 / 171 / 64
Регистрация: 18.01.2014
Сообщений: 387
15.08.2014, 21:36     Оптимизация робота #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
https://ru.wikipedia.org/wiki/%D0%9C...86%D0%B8%D1%8F

Создаете структуру (массив, ассоциативный массив (map), что больше подходит) в котором будут хранится результаты предыдущих вычислений k, x, y, изменяете функцию F таким образом: при вызове функции F сначала проверяете, есть ли уже такой сохраненный результат с такими параметрами вызова, если есть, то возвращаете его, если нет, то вычисляете, заносите в кэш и тоже возвращаете.
Yandex
Объявления
15.08.2014, 21:36     Оптимизация робота
Ответ Создать тему
Опции темы

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