54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 1
1

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

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

Author24 — интернет-сервис помощи студентам
Задача:

Найдите, сколько существует строк заданной длины 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.12.2013, 19:41
Ответы с готовыми решениями:

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

Алгоритм Ахо-Карасика: для каждого слова определить, сколько раз оно встречается как подстрока во всех остальных словах
Алгоритм Ахо-Карасика. Дан набор из n различных слов. Для каждого слова узнайте, сколько раз оно...

Усовершенствовать рекурсивный алгоритм
Здравствуйте, помогите пожалуйста добавить &quot;кеш&quot; в алгоритм. При больших значения матрицы он не...

Как усовершенствовать алгоритм?
Здравствуйте. Есть такой код: for(int i = 0; i &lt; WORDS-&gt;Count; i++) { flag = false;...

2
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
02.12.2013, 20:08 2
динамику считать. вроде можно так: d[i] = d[i-1] * 3 - d[i-2].
0
54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 1
02.12.2013, 20:42  [ТС] 3
Цитата Сообщение от salam Посмотреть сообщение
динамику считать. вроде можно так: d[i] = d[i-1] * 3 - d[i-2].
непонял
0
02.12.2013, 20:42
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.12.2013, 20:42
Помогаю со студенческими работами здесь

усовершенствовать алгоритм с циклом
Есть N целых чисел. Нужно складывать их до тех пор, пока они их сумма НЕ будет превышать лимит....

Как усовершенствовать алгоритм?
Архивация public static void Zip(string FileRes, string FileDest) { ...

Усовершенствовать алгоритм Евклида по нахождению наибольшего общего делителя
Помогите пожалуйста. Усовершенствовать алгоритм евклида нахождение наибольшего общего определителя...

Задача. Алгоритм
задача такая Дано вещественное число X(|X|&lt;1) и целое число N(&gt;0). Найти значение выражения...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru