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

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

Войти
Регистрация
Восстановить пароль
 
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 754
Записей в блоге: 1
#1

Задача: плохая подстрока. Усовершенствовать алгоритм - C++

02.12.2013, 19:41. Просмотров 827. Ответов 2
Метки нет (Все метки)

Задача:

Найдите, сколько существует строк заданной длины n, состоящих только из символов 'a', 'b' и "c", и не содержащих подстроки "ab".

вот мое решение:
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
#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    int n;
    
    __int64 a = 0, b, len;
    char str[ 50 ];
    
    cin >> n;
    b = pow( (double)3, (double)n );
    a = 0;
    
    for( int i = 0; i < b; i++ )
    {
         strcpy( str, "" );
         itoa( i, str, 3 );
         
         len = strlen( str );
         
         for( int j = 0; j < len - 1; j++ )
         {
              if( str[ j ] == '1' && str[ j + 1 ] == '2' )
              {
                  a++;
                  break;
              }
         }
    }
    
    cout <<  b - a << "\n";
   return system("pause");
}
оно работает, но работает очень долго на больших n. Вопрос: как ускорить алгоритм?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2013, 19:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача: плохая подстрока. Усовершенствовать алгоритм (C++):

Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице - C++
У меня есть этот алгоритм. Кто знает, как усовершенствовать его, чтобы он искал символьную подматрицу m * m в символьной матрицы n * n, при...

Олимпиадная задача. Алгоритм - C++
Всем привет. Помогите понять алгоритм решения задачи. 1. Как найти перекресток, с которого начинается движение робота (и...

усовершенствовать код - C++
У меня две просьбы 1.Нужно усовершенствовать этот код , чтобы его нельзя было никакими методами &quot;сломать&quot;. Задача: Вывести...

немного усовершенствовать... - C++
B]как сделать так чтобы пробег автобусов генерировался randomize а не вводился с клавиатуры...?...все время получаются какие то...

Усовершенствовать код - C++
Можно ли сделать так что бы не писать s1,s2 ,а просто сделать так чтобы результат от s1 остался и я такими же вычислениями посчитал s2 и в...

Исправление fillMaze (задача на алгоритм Ли и очередь) - C++
Имеется задача про нахождение кратчайшего пути в лабиринте до цели. В fillMaze используется алгоритм Ли. Также для решения задачи...

2
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
02.12.2013, 20:08 #2
динамику считать. вроде можно так: d[i] = d[i-1] * 3 - d[i-2].
0
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 754
Записей в блоге: 1
02.12.2013, 20:42  [ТС] #3
Цитата Сообщение от salam Посмотреть сообщение
динамику считать. вроде можно так: d[i] = d[i-1] * 3 - d[i-2].
непонял
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2013, 20:42
Привет! Вот еще темы с ответами:

Как усовершенствовать программу? - C++
Доброго времени суток! Начал изучать с++,написал простенькую прогу чтобы попрактиковаться,хотелось бы узнать как можно ещё более...

усовершенствовать граф редактор - C++
Здраствуйте.Пишу с просьбой помогите решить поставленную задачу.Необходимо из заготовки с исходным кодом усовершенствовать граф редактор...

подстрока - C++
в заданной строке найти позицию первого вхождения указанной подстроки .не используя стандартные функции.спасибо!

Подстрока - C++
Всем Приветы, вопрос на сейчас такой: Как получить подстроку из данной строки, если данная задаётся пользователем? Вот пример: ...


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

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

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