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

Убыстрение работы программы - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Функция вычисления длины дискового файла http://www.cyberforum.ru/cpp-beginners/thread674564.html
Как сделать функцию, которая вычисляет длину дискового файла в байтах. При этом имя файла задано в командной строке.
C++ Разработка под какую платформу перспективнее Что на дальней дистанции перспективнее в плане разработки? там ПО под винду,анроид, иос.....какую платформу выбрать? http://www.cyberforum.ru/cpp-beginners/thread674563.html
C++ Переписать код с использованием указателей на функцию
Помогите вот эту программу переделать на указатели! Спасибо всем) #include <iostream> #include <locale.h> #include <conio.h> using namespace std; float sum(float,float); int main() { float a,b;
Преобразовать точки в троеточия C++
Дана строка символов. Преобразовать ее, заменив в ней каждую точку многоточием. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <conio.h> void main () {int i;
C++ Простая программа на указатели! http://www.cyberforum.ru/cpp-beginners/thread674540.html
Помогите пожалуйста написать вот эту программу через указатели! Я не понимаю с чего начать, очень нужно! Заранее спасибо) #include <iostream> #include <conio.h> using namespace std; int min(int ,int); int max(int ,int); int main()
C++ Указатель на функцию float ( *f)(float, float); float rosenbrock(float x1, float x2) { return 100*pow((x2-x1*x1),2)+pow((1-x1),2); } f=rosenbrock; подробнее

Показать сообщение отдельно
DenCHS200
32 / 32 / 1
Регистрация: 07.10.2011
Сообщений: 117

Убыстрение работы программы - C++

18.10.2012, 21:33. Просмотров 417. Ответов 9
Метки (Все метки)

Написал программу по поиску максимальной подстроки из заданных строк. Работает правильно, но нужно оптимизировать по времени выполнения(Не более секунды на обработку результатов). У кого какие соображения по убыстрению программы.
Алгоритм конечно мудрёный получился, но может как-то можно оптимизировать её работу?
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <stdio.h>
#include <iostream>
 
using namespace std;
 
 
char MassivStrok[10][10000];
unsigned int temp2,temp,DlinyStrok[10];
unsigned short numberS=11; // индекс строки с самым минимальным кол-вом символов
char ch;
unsigned int limit=0;
 
char MinString[10000];
char FindSubString[10000];
 
void main()
{
 
 
unsigned int max,j,i,n,i2;  
    
 
cin>>n;
ch=getchar();
for(i=0;i<n;i++) // инициализируем массив 
DlinyStrok[i]=0;
i=j=0;
while(i<n){
    while((ch=getchar())!= '\n')
{
MassivStrok[i][j]=ch;
DlinyStrok[i]++;
j++;
}
    j=0;
    i++;
}
max=DlinyStrok[0];numberS=0;
// далее ищем минимальную по длине строку
for(i=1;i<n;i++)
if(DlinyStrok[i]<max)
{
max=DlinyStrok[i];
numberS=i;
}
 
 
 
for(i=0;i<max;i++){// передаём минимальную строку в массив
MinString[i]=MassivStrok[numberS][i];
FindSubString[i]=MassivStrok[numberS][i];}
unsigned int i1,j1;
 
bool sovpadaet1; // если совпадает текущий проверяемый символ
bool sovpadaet2=false;  // если совпало с i-той строкой
unsigned int index1;// индекс урезания строки справа
unsigned int step,index2 ; // индекс урезания слева
 
index1=index2=0;
 
 
 
 
 
 
 
 
//max3=max;
 
i1=0;
// а теперь самый смак программы, алгоритм!
while((sovpadaet2==false)&&(max>1)){// пока не довели строку до нуля
        
        
    do{
            step=0;
            
            if(i1!=numberS){// если сравнивать не с собой
                
                // находим первый совпадающий символ 
        
    
                
        
        
                j1=0;
M1:;
        while((FindSubString[0]!=MassivStrok[i1][j1])&&(j1<DlinyStrok[i1]))
        {
        j1++;
        }
        
step=0;
i=j1;
// предполагаем, что совпадает
sovpadaet1=true;
do
{
                        if(FindSubString[step]==MassivStrok[i1][i])
                {step++;
                        i++;
                                    }
                else{
                 sovpadaet1=false;
                 sovpadaet2=false;
            break;   
                    }
temp2=max-limit;
    }while(step<temp2);
if((j1<DlinyStrok[i1]-limit)&&(sovpadaet1==false))
{j1++;goto M1;}
 
//endDo-WHILE
 
// Код изменения СубСтроки
//===============================
 
if(sovpadaet1==false) // если не совпало, то делаем строку меньше или изменяем
{
    i1=0;
    if(index1==0){
        limit++;
    index2=limit;}
 
    if(limit<max){
    
        
i2=0;
    for(j=index1;j<max-index2;j++){
        FindSubString[i2]=MinString[j];
        i2++;
    
    }
        index1++;
if(index2!=0)
index2--;
        if(index1>limit)
{index1=0;
index2=limit+1;
}
}
 
}
 
            
 
    
 
        
// Конец изменения субстроки
else // если же строка совпала, то переходим на следующую строку и
// сообщаем о совпадении 
{
sovpadaet2=true;
i1++;
}
            }// endIF
 else{ // в противном случае переходим к следующей строке
i1++;
}
 temp=max-limit;
        }while((i1<n)&&(temp>1));
            
}
        if(sovpadaet2==true){
        for(i=0;i<max-limit;i++)// выводим полученную подстроку
            cout<<FindSubString[i];}
getchar();
    
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru