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

Оптимизация программы на С++ - C++

Восстановить пароль Регистрация
 
programka311
0 / 0 / 0
Регистрация: 22.03.2013
Сообщений: 9
22.03.2013, 10:38     Оптимизация программы на С++ #1
Помогите оптимизировать программу на С++, я не представляю, что в ней можно изменить. Хотя бы намек на функцию, в которой нужна оптимизация Очень надо!!!
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <iostream.h>
//прототипы функций
void vvod (long &,int &);
void conversion(long,int,int *&,int &);
int polin(int *&,int);
void vivod(int *&,int);
void summa(int *, int , int , int & , int * , int * &, int);
void vichitanie(int *,int , int *,int ,int *&,int &,int);
void main()
{
    //инициализация переменных
    long j,con_dip;
    int *a,na,osn,*min,*max,nmin,nmax,l=0,*s,ns,*v,nv;
    //вызов функции ввода
    vvod(con_dip,osn);
    cout<<"Osnovanie sistemi="<<osn<<endl;
    //цикл по всему диапазону чисел
    for(j=100;j<con_dip;j++)
    {
        //вызов функции перевода из 10 в заданную системы счисления и наоборот
        conversion(j,osn,a,na);
        conversion(j,10,b,nb);
        //вызов функции нахождения палиндрома и запись результат в переменную
        int voz1= polin(a,na);
        int voz2=polin(b,nb);
        //сравниваем результаты функции нахождения палиндромав
        if(voz1==1 && voz2==1)
            {
                //запоминаем 1 палиндром
                if(l==0)
                    {
                    min=a;
                        nmin=na;
                        l=1;
                    }
                //вывод палиндромов
                vivod(a,na);
                //запоминаем последний палиндром
                max=a;
                nmax=na;
            }
   }
   //вывод минимума
   cout<<"**********MIN**********"<<endl;
   vivod(min,nmin);
      //вывод максимума
   cout<<"**********MAX**********"<<endl;
   vivod(max,nmax);
      //расчет и вывод суммы
   cout<<"**********SUMMA**********"<<endl;
   summa(min,nmin,nmax,ns,max,s,osn);
   vivod(s,ns);
      //расчет и вывод разности
   cout<<"**********RAZNOST**********"<<endl;
   vichitanie(min,nmin,max,nmax,v,nv,osn);
   vivod(v,nv);
      //задержка 
   cin >>na;
}
//функция ввода
void vvod(long &con_dip,int &osn)
{
    do
    {
        cout<<"Vvedite chislo:"<<endl;
        cin>>con_dip;
    }
   while(con_dip<100 );//ввод основания системы счисления от 100
   do
    {
        cout<<"Vvedite osnovanie sistemi:"<<endl;
        cin>>osn;
    }
   while(osn<2 || osn>16);//ввод основания системы счисления от 2 до 16
}
//функция перевода числа из 10-ой в заданную систему счисления
void conversion(long j, int osn, int *&x, int &n)
{
    int i;
    //заносим число из диапазона в переменную s, чтобы само число не менять для дальнейшей работы с ним
    long s=j;
    //определяем размер массива для палиндрома
    for(n=1;s>=osn;n++)
        {
            s=s/osn;
        }
        //выделение памяти для массива битов числа
    x=new int[n];
    //перевод числа в заданную систему счисления
    for(i=n-1;i>=0;i--)
        {
            //остаток от делание на основание системы счисления
            x[i]=j%osn;
            //уменьшение числа для дальнейшего деления с остатком
            j=j/osn;
        }
}
//функция нахождения палиндромов
int polin(int *&x, int n)
{
    int i; 
    //определяем палиндром или нет
    for(i=0;i<=n/2;i++)
        {
            if(x[i]!=x[n-i-1])
            //если не палиндром
            return 0;
        }
        //если палиндром
    return 1;
}
//функция вывода
void vivod(int *&x, int n)
{
    int i;
    for(i=0;i<n;i++)
        {
            ////Если значения в ячейке больше 9, то заменяем их буквами, для 16 системы счисления
            if(x[i]==10)
                cout << 'A';
            else
            if(x[i]==11)
                cout<<'B';
            else
            if(x[i]==12)
                cout<<'C';
            else
            if(x[i]==13)
                cout<<'D';
            else
            if(x[i]==14)
                cout<<'E';
            else
            if(x[i]==15)
                cout<<'F';
            else
                cout<<x[i];//вывод для остальных систем счисления
        }
    cout<<endl;
}
//функция нахождения суммы максимального и минимального палиндромов
void summa(int * min, int nmin, int nmax, int & n, int * max, int * & x, int osn)
{
    int d=0;
    //выделение памяти под массив суммы
    n = nmax+1;
    x = new int [n];
    for (int i=nmin-1,k=nmax-1; i>=0; i--, k--)
        {
            //сумма заносится по разрядно в массив суммы
            x[k+1]=(max[k]+min[i]+d)%osn; 
            //установка переполнения
                                 d=(max[k]+min[i]+d)/osn;
        }
        
    //снос оставшихся битов с переполнением
    for (int i=nmax-nmin; i>0; i--)
        {
            x[i]=(max[i-1]+d)%osn;
            d=(max[i-1]+d)/osn;
        }
    x[0]=d;
}
//функция нахождения разности между максимальным и минимальным 
void vichitanie(int *min,int nmin,int *max,int nmax,int *&x,int &n,int osn)
{
    n=nmax;
    //Выделение памяти для результирующего массива разности
    x=new int [nmax]; 
    long t = 0;
    
    //цикл, пока не начало массива максимального палиндрома
    for(int i=nmax-1, k=nmin-1; i>=0; i--, k--) 
        {
             //Если минимальный палиндром закончился
            if(k<0)
            //От текущего элемента массива максимального палиндрома отнимается "займ"
                x[i]=max[i]-t; 
            //От текущего элемента массива максимального палиндрома отнимается соответствующий минимальный и отнимается "займ"
            x[i]=max[i]-min[k]-t; 
             //Если вычитание отрицательно
            if(x[i]<0)
            {
                //Добавление основания системы к результату вычитания
                x[i]=x[i]+osn;
                //Установка необходимости займа
                t=1;    
            }
            else
            t=0; 
        }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2013, 10:38     Оптимизация программы на С++
Посмотрите здесь:

C++ Оптимизация кода программы
Оптимизация простой программы C++
Оптимизация программы C++
Оптимизация программы C++
Оптимизация программы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
22.03.2013, 10:59     Оптимизация программы на С++ #2
Например, вместо
Цитата Сообщение от programka311 Посмотреть сообщение
////Если значения в ячейке больше 9, то заменяем их буквами, для 16 системы счисления
if(x[i]==10)
cout << 'A';
else
if(x[i]==11)
cout<<'B';
else
if(x[i]==12)
cout<<'C';
else
if(x[i]==13)
cout<<'D';
else
if(x[i]==14)
cout<<'E';
else
if(x[i]==15)
cout<<'F';
else
cout<<x[i];//вывод для остальных систем счисления
Можно
C++
1
  cout << char((x[i] > 9) ? 'A' + x[i] - 10 : '0' + x[i]);
Добавлено через 1 минуту
Цитата Сообщение от programka311 Посмотреть сообщение
Помогите оптимизировать программу на С++, я не представляю, что в ней можно изменить.
Зачем и что "оптимизировать", если вы не представляете, что можно изменить?
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,334
Завершенные тесты: 1
22.03.2013, 11:03     Оптимизация программы на С++ #3
Не основное:
Если писать комментарии сбоку от того, что они комментируют, то это оптимизирует вам общее количество строк кода.

В функции vivod можно заменить
C++
1
2
3
4
5
6
7
8
9
10
            ////Если значения в ячейке больше 9, то заменяем их буквами, для 16 системы счисления
switch(x[i])
  {
  case 10 : cout << 'A'; break;
  case 11 : cout << 'B'; break;
  case 12 : cout <<' C'; break;
  case 13 : cout << 'D'; break;
  case 14 : cout << 'E'; break;
  case 15 : cout << 'F'; break;
  default  : cout << x[i]; //вывод для остальных систем счисления
Но это тоже так себе оптимизация.
programka311
0 / 0 / 0
Регистрация: 22.03.2013
Сообщений: 9
22.03.2013, 11:33  [ТС]     Оптимизация программы на С++ #4
Цитата Сообщение от lemegeton Посмотреть сообщение
Зачем и что "оптимизировать", если вы не представляете, что можно изменить?
Я про тоже, что и так все норм. Задание такое. Надо и все, хоть ты тресни.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,334
Завершенные тесты: 1
22.03.2013, 12:16     Оптимизация программы на С++ #5
В 147 строке
C++
1
2
    n = nmax+1;
    x = new int [n];
заменить на
C++
1
x = new int [++nmax]
А так же в 168 по аналогии.

Но скорее всего в задании имеется ввиду покурить повнимательнее алгоритмы и изменить их принцип работы.
programka311
0 / 0 / 0
Регистрация: 22.03.2013
Сообщений: 9
22.03.2013, 13:55  [ТС]     Оптимизация программы на С++ #6
Цитата Сообщение от SatanaXIII Посмотреть сообщение
В 147 строке
C++
1
2
    n = nmax+1;
    x = new int [n];
заменить на
C++
1
x = new int [++nmax]
А так же в 168 по аналогии.

Но скорее всего в задании имеется ввиду покурить повнимательнее алгоритмы и изменить их принцип работы.
Оптимизацию нужно сделать по объему память или по времени выполнения!
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4925 / 2668 / 243
Регистрация: 29.11.2010
Сообщений: 7,421
22.03.2013, 14:06     Оптимизация программы на С++ #7
void main убрать, транслит убрать, сдвиги подкорректировать
Цитата Сообщение от programka311 Посмотреть сообщение
x=new int [nmax];
я надеюсь, вы понимаете, что память надо освободить.

Хотелось бы ТЗ знать, а то даже не понятно, что программа должна в идеале делать.
Цитата Сообщение от programka311 Посмотреть сообщение
x[i]=x[i]+osn;
C++
1
x[i] += osn; // для краткости и удобочитаемости
Добавлено через 1 минуту
Цитата Сообщение от programka311 Посмотреть сообщение
for(i=0;i<=n/2;i++)
* * * * {
* * * * * * if(x[i]!=x[n-i-1])
* * * * * * //если не палиндром
* * * * * * return 0;
* * * * }
* * * * //если палиндром
насчет сдвигов - вот так:
C++
1
2
3
4
5
for(i=0; i <= n/2; i++)
{
    if(x[i] != x[n-i-1])* //если не палиндром
        return 0;
}
programka311
0 / 0 / 0
Регистрация: 22.03.2013
Сообщений: 9
22.03.2013, 14:10  [ТС]     Оптимизация программы на С++ #8
Цитата Сообщение от MrGluck Посмотреть сообщение
void main убрать, транслит убрать, сдвиги подкорректировать

я надеюсь, вы понимаете, что память надо освободить.

Хотелось бы ТЗ знать, а то даже не понятно, что программа должна в идеале делать.

C++
1
x[i] += osn; // для краткости и удобочитаемости
Добавлено через 1 минуту

насчет сдвигов - вот так:
C++
1
2
3
4
5
for(i=0;i<=n/2;i++)
{
    if(x[i] != x[n-i-1])* //если не палиндром
* *     return 0;
}
ТЗ:
Выдать на печать все числа от 100 до n, которые будут
являться палиндромами, как в десятичной системе счисления,
так и в q-ичной. Вычислять сумму и разность между
максимальным и минимальным палиндромами.

Добавлено через 3 минуты
Цитата Сообщение от MrGluck Посмотреть сообщение
void main убрать, транслит убрать, сдвиги подкорректировать

я надеюсь, вы понимаете, что память надо освободить.

Хотелось бы ТЗ знать, а то даже не понятно, что программа должна в идеале делать.

C++
1
x[i] += osn; // для краткости и удобочитаемости
Добавлено через 1 минуту

насчет сдвигов - вот так:
C++
1
2
3
4
5
for(i=0; i <= n/2; i++)
{
    if(x[i] != x[n-i-1])* //если не палиндром
        return 0;
}
И чем помогут подкорректированные сдвиги??? А как без void main()
saaresto
9 / 9 / 0
Регистрация: 22.03.2013
Сообщений: 23
22.03.2013, 14:11     Оптимизация программы на С++ #9
Цитата Сообщение от programka311 Посмотреть сообщение
И чем помогут подкорректированные сдвиги???
Повысят читабельность кода
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4925 / 2668 / 243
Регистрация: 29.11.2010
Сообщений: 7,421
22.03.2013, 14:14     Оптимизация программы на С++ #10
Цитата Сообщение от programka311 Посмотреть сообщение
А как без void main()
как требует стандарт и все нормальные компиляторы:
int main()
programka311
0 / 0 / 0
Регистрация: 22.03.2013
Сообщений: 9
22.03.2013, 14:18  [ТС]     Оптимизация программы на С++ #11
Цитата Сообщение от MrGluck Посмотреть сообщение
я надеюсь, вы понимаете, что память надо освободить.
Как ее ОСВОБОДИТЬ???
saaresto
9 / 9 / 0
Регистрация: 22.03.2013
Сообщений: 23
22.03.2013, 14:20     Оптимизация программы на С++ #12
Цитата Сообщение от programka311 Посмотреть сообщение
Как ее ОСВОБОДИТЬ???
C++
1
2
3
4
5
x=new int [nmax];
/*
код программы
*/
delete [] x;
programka311
0 / 0 / 0
Регистрация: 22.03.2013
Сообщений: 9
22.03.2013, 14:26  [ТС]     Оптимизация программы на С++ #13
Вот мои труды оптимизации, но они ни чего не дали
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
int main()
{
      //........
      //вместо этого...
     int voz1= polin(a,na);
     int voz2=polin(b,nb);
     //вот это!
     if(polin(a,na)==1 && polin(b,nb)==1)
    //....
    //В самом конце int main()
    delete a;
    delete b;
    delete min;
    delete max;
    delete s;
    delete v;
   
}
//функцию вывода изменила полностью
void vivod(int *&x, int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        //0 символ "0" соответствует 0, и так далееф, 10 символ "A". То есть на k-ой позиции k-я цифра.
        char* digits = "0123456789ABCDEF";
        cout << digits[x[i]];
    }
    cout<<endl;
}
И НИ ЧЕГО
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
22.03.2013, 14:27     Оптимизация программы на С++ #14
Цитата Сообщение от MrGluck Посмотреть сообщение
А как без void main()
как требует стандарт и все нормальные компиляторы:
int main()
а что, правда использование int main () вместо void main() быстрее работает?
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
22.03.2013, 15:02     Оптимизация программы на С++ #15
Неплохо было бы узнать, какая была исходная задача? Если это то, что я думаю, можно сделать в два раза короче.
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
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <iostream>
 
char *toBase(char *buffer, int number, int radix) {
  const static char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  char *result = buffer;
  for (; number > 0; number /= radix) {
    *buffer++ = digits[number % radix];
  }
  *buffer-- = '\0';
  for (char *i = result; i < buffer; ++i, --buffer) {
    char c = *i;
    *i = *buffer;
    *buffer = c;
  }
  return result;
};
 
int reverse(int number) {
  int result = 0;
  while (number > 0) {
    result = (result * 10 + number % 10);
    number /= 10;
  }
  return result;
};
 
bool isPalindrome(int number) {
  return number == reverse(number);
};
 
bool isPalindrome(const char *word) {
  const char *first = word;
  const char *last = word + strlen(word) - 1;
  while (first < last) {
    if (*first++ != *last--) {
      return false;
    } 
  }
  return true;
};
 
int main(int argc, char *argv[]) {
  srand(time(0));
  
  char buffer[512];
  
  int radix = 2 + rand() % 15;
  int firstNumber = 100;
  int lastNumber = 300000;
    
  int minPalindrome = -1; 
  int maxPalindrome = -1;
 
  std::cout << "Radix is " << radix << ", first number is " << 
    firstNumber << ", last number is " << lastNumber << 
    " exclusive." << std::endl;
 
  for (int number = firstNumber; number <lastNumber; ++number) {
    if (isPalindrome(number) &&
      isPalindrome(toBase(buffer, number, radix))) {
      std::cout << "Found number: " << number << " aka " << buffer << 
        " is palindrome in both 10 and " << radix << " radix." <<
        std::endl;
      if (minPalindrome > number || minPalindrome < 0) {
        minPalindrome = number;
      }
      if (maxPalindrome < number || maxPalindrome < 0) {
        maxPalindrome = number;
      }
    }
  }
 
  std::cout << "Minimal palindrome is " << minPalindrome <<
    ", in radix " << radix << ": " <<
    toBase(buffer, minPalindrome, radix) << std::endl;
  std::cout << "Maximal palindrome is " << maxPalindrome <<
    ", in radix " << radix << ": " <<
    toBase(buffer, maxPalindrome, radix) << std::endl;
 
  std::cout << "Sum of max and min palindroms is " <<
    minPalindrome + maxPalindrome <<
    ", in radix " << radix << ": " <<
    toBase(buffer, minPalindrome + maxPalindrome, radix) << std::endl;
  
  std::cout << "Difference of max and min palindroms is " <<
    maxPalindrome - minPalindrome <<
    ", in radix " << radix << ": " <<
    toBase(buffer, maxPalindrome - minPalindrome, radix) << std::endl;
 
  return 0;
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11841 / 6820 / 771
Регистрация: 27.09.2012
Сообщений: 16,911
Записей в блоге: 2
Завершенные тесты: 1
22.03.2013, 15:21     Оптимизация программы на С++ #16
Цитата Сообщение от Asker Посмотреть сообщение
а что, правда использование int main () вместо void main() быстрее работает?
По стандарту должно быть int. Большинство компиляторов уже давно не компилируют void main()
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.03.2013, 16:12     Оптимизация программы на С++
Еще ссылки по теме:

C++ Оптимизация программы
C++ Оптимизация программы
C++ Оптимизация программы по памяти

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

Или воспользуйтесь поиском по форуму:
iifat
2179 / 1332 / 96
Регистрация: 05.06.2011
Сообщений: 3,690
22.03.2013, 16:12     Оптимизация программы на С++ #17
Выкинуть массив вводимых чисел. Нам нужно очередное, его номер, максимум из просмотренных, минимум из просмотренных.
Взяли число, проверили, надо ли обрабатывать, напечатали, скорректировали максимум/минимум -- следующее читаем в ту же переменную.
Yandex
Объявления
22.03.2013, 16:12     Оптимизация программы на С++
Ответ Создать тему
Опции темы

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