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

Программа не укладывается во время - C++

Восстановить пароль Регистрация
 
SergeyKandy
0 / 0 / 0
Регистрация: 31.12.2012
Сообщений: 5
31.12.2012, 20:46     Программа не укладывается во время #1
Здравствуйте. Я решаю одну олимпиадную задачу,и она должна улаживатся в 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
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
using namespace std;
int sum=0;
int n;
int P(string a,string b){
         int pos=0,k;
         int i,j;
         i=0;j=n-1;
         pos= a.find(b);
         if(pos!=-1)return 1; 
         for(;;){
         if(i>=j)return 0;
         if(a[i]!=a[j])return 1;
         i++;j--;
         }
}
 int F(string a,string b){    
     int k;
     if(a.length()==n)
     {k=P(a,b);if(k==0){sum++;}return 0;}
      F(a+'A',b);
      F(a+'B',b);
      return 0; 
   }
   
 
int main()
{
   
  string a,b;   
  cin>>b>>n;
  F(a,b);
  cout<<sum;
//system("PAUSE");
   return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
31.12.2012, 20:53     Программа не укладывается во время #2
SergeyKandy, что за задание?
SergeyKandy
0 / 0 / 0
Регистрация: 31.12.2012
Сообщений: 5
31.12.2012, 20:54  [ТС]     Программа не укладывается во время #3
Условие задачи:Известно, что палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, палиндромами являются строки “A”, “ABA”, “ABBA”, а строки “AB”, “AAB”, “ABAB” палиндромами не являются. В новогоднюю ночь роботы генерировали пожелания друг другу в виде палиндромов. Но чтобы пожелание было добрым оно не должно содержать запрещенных строк. Рассмотрим некоторую строку S, состоящую только из латинских букв A и B. Назовем запрещенными все строки длины N, которые состоят также только из букв A и B и содержат S в качестве подстроки. Например, если S = “AB” и N = 3, то существует четыре запрещенных строки: “AAB”, “ABA”, “ABB” и “BAB”. Остальные строки будет называть допустимыми.

Помогите роботам с генерацией добрых пожеланий - напишите программу, которая для заданной строки S длиной не более пяти символов и заданного числа N определяет количество допустимых строк длины N, которые являются палиндромами.
Формат входных данных
Первая строка содержит строку S. Вторая строка содержит одно целое число N. Длина строки S не превосходит пяти.

1 ≤ N ≤ 100
Формат выходных данных
Выведите одно целое число - количество строк длины N, которые являются палиндромами и не содержат S в качестве подстроки.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
31.12.2012, 20:59     Программа не укладывается во время #4
SergeyKandy, могу сказать, что нужно не оптимизировать то, что есть, а придумывать новый алгоритм.
SergeyKandy
0 / 0 / 0
Регистрация: 31.12.2012
Сообщений: 5
31.12.2012, 21:04  [ТС]     Программа не укладывается во время #5
В каком направление вы посоветуете думать?
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
31.12.2012, 21:17     Программа не укладывается во время #6
Что вы делаете сейчас - перебираете все наборы длины N и каждый проверяете на то, содержится ли там строка S, а также является ли набор палиндромом. Сомнительно, не правда ли?
Начнем с того, что мы можем изначально генерировать не абы какой набор символов, а гарантированный палиндром. Это уже значительно уменьшит сложность.
И еще я бы посоветовал задаться вопросом - а надо ли вообще перебирать наборы? У нас же не просят вывести на экран все "добрые пожелания". У нас спрашивают только их количество. Может их количество можно найти не простым перебором, а некоторой формулой? Например, мы находим общее количество палиндромов длины N. Затем находим количество палиндромов, содержащих в себе строку S. Ответом будет разность этих двух чисел.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
31.12.2012, 22:56     Программа не укладывается во время #7
Динамическое программирование должно помочь
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.01.2013, 13:16     Программа не укладывается во время
Еще ссылки по теме:

Программа, во время выполнения, после ввода, прекращает работу C++
Найти из массива пары чисел, сумма которых укладывается в определенном диапазоне C++
C++ Организация вычислений во время ввода данных программа С++

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.01.2013, 13:16     Программа не укладывается во время #8
Цитата Сообщение от SergeyKandy Посмотреть сообщение
Здравствуйте. Я решаю одну олимпиадную задачу,и она должна улаживатся в 2 секунды.
Улаживаться в 2 секунды - это есть проблема, позвонил и всё уладил, к прогам относиться не может.
Yandex
Объявления
01.01.2013, 13:16     Программа не укладывается во время
Ответ Создать тему
Опции темы

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