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

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

Восстановить пароль Регистрация
 
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
02.12.2013, 19:41     Задача: плохая подстрока. Усовершенствовать алгоритм #1
Задача:

Найдите, сколько существует строк заданной длины 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. Вопрос: как ускорить алгоритм?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2013, 19:41     Задача: плохая подстрока. Усовершенствовать алгоритм
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.12.2013, 20:08     Задача: плохая подстрока. Усовершенствовать алгоритм #2
динамику считать. вроде можно так: d[i] = d[i-1] * 3 - d[i-2].
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 644
Записей в блоге: 1
02.12.2013, 20:42  [ТС]     Задача: плохая подстрока. Усовершенствовать алгоритм #3
Цитата Сообщение от salam Посмотреть сообщение
динамику считать. вроде можно так: d[i] = d[i-1] * 3 - d[i-2].
непонял
Yandex
Объявления
02.12.2013, 20:42     Задача: плохая подстрока. Усовершенствовать алгоритм
Ответ Создать тему
Опции темы

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