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

нужна оптимизация приложения - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Реализовать подпрограммы посредством: А) процедур; Б) функции. http://www.cyberforum.ru/cpp-beginners/thread540587.html
По заданным вещественным числам a_0,a_1,… ,a_30,b_0 ,b_1,… b_30,c_0,c_1,…,c_30,x,y,z. вычислить величину ((a_0 x^30+a_1 x^29+⋯+a_30 )^2-(b_0 y^30+b_1 y^29+⋯+b_30 ))/(c_0 (x+z)^30+c_1 (x+z)^29+⋯+c_30 ) Реализовать подпрограммы посредством: А) процедур; Б) функции.
C++ Дан файл f:file of real. Найти наибольшее из значений компонент. Дан файл f:file of real. Найти наибольшее из значений компонент. http://www.cyberforum.ru/cpp-beginners/thread540586.html
Сортировка(2) C++
Во входном файле содержится информация об каждом из n студентов некоторого вуза, разделённого пробелами: 〈фамилия〉 〈имя〉 〈отчество〉 〈пол〉 〈возраст〉〈курс〉, причем в фамилии – не более 12 букв, пол указывается буквами М и Ж, возраст – целое от 16 до 35, курс – целое от 1 до 5. Ввести эту информацию и напечатать номер курса, на котором наибольший процент мужчин.
C++ Сортировка
Даны действительные числа a_1,…,a_n. Получить попарно различные целые j_1,…,j_n, такие, что 1≤k_j≤n,k=1,…,n, и a_j1≥a_j2≥⋯≥a_jn. Воспользоваться методом: А)Сортировки прямым выбором; Б) «шейкерной» сортировки.
C++ Дано: a:array[1…n] of real;p:real;k:integer;(a[1]<=a[2]<=⋯<=a[n],0<k≤n). http://www.cyberforum.ru/cpp-beginners/thread540581.html
Дано: a:array of real;p:real;k:integer;(a<=a<=⋯<=a,0<k≤n). Удалить из a элемент с номером k (т.е. a) и вставить элемент, равный p, так, чтобы не нарушилась упорядоченность.
C++ Простой класс на основе заданной структуры данных с++ Помогите пожалуйста... Необходимо разработать программу, реализующую простой класс на основе заданной структуры данных. подробнее

Показать сообщение отдельно
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.04.2012, 02:30     нужна оптимизация приложения
нужна оптимизация приложения Так что, никто не знает, в чем ошибка? Посмотрите хотя бы первую функцию (mult). Она правильно должна работать?

Добавлено через 3 минуты
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ну а как иначе предлагаешь оценить произведение 100000 чисел, каждое 32 разряда, не вызвав переполнение?
В моём варианте числа хранятся в векторе. На тестовых вариантах получается максимальное время 1375 ms, память 8.5 mb. Но умножение почему-то вообще не меняет изначальное число. Наверное в синтаксисе где-то ошибка, потому что внутренности копировал из статьи про арифметику длинных чисел.

Добавлено через 1 час 44 минуты
Оптимизировал немного, нашел ошибку. Проходит 70% тестов. На одном неверный ответ, на остальных не хватает времени
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
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> lnum;
const int base = 1000*1000*1000;
  lnum a[20];
  int sign[20]; //Г¬Г*Г±Г±ГЁГў õðГ*Г*ГҐГ*ГЁГї Г§Г*Г*ГЄГ*
  int inp[20][100000];
 
lnum mult (lnum a, int b)  //ÓìГ*îæåГ*ГЁГҐ äëèГ*Г*îãî Г*Г* êîðîòêîå
//ÓìГ*îæГ*ГҐГІ äëèГ*Г*îå a Г*Г* êîðîòêîå b (b < (base)) 
//ГЁ ñîõðГ*Г*ГїГҐГІ ðåçóëüòГ*ГІ Гў a:
{
 int carry = 0;
 for (size_t i=0; i<a.size() || carry; ++i) 
  {
   if (i == a.size())
    a.push_back (0);
   long long cur = carry + a[i] * 1ll * b;
   a[i] = int (cur % base);
   carry = int (cur / base);
  }
while (a.size() > 1 && a.back() == 0)
    a.pop_back();
return a;
}
 
bool checks(lnum a, lnum b)  // a>=b 
{
 if (a.size()>b.size()) return true;
 if (a.size()<b.size()) return false;
 for (size_t i=(int)a.size()-1;i>=0;i--)
  {
   if (a[i]>b[i]) return true;
   if (a[i]<b[i]) return false;
  }
 return true;
} 
 
int main()
{
  FILE *f=fopen("input.txt","r");
  int N, K;
  fscanf(f,"%d%d",&N,&K);
  for (int i=0;i<N;i++)
   {
    a[i].push_back(1); //äëÿ ГіГ¬Г*îæåГ*ГЁГї
    sign[i]=1;      //+
   }
  for (int i=0;i<K;i++)
   {
    for (int j=0;j<N;j++)
     {
      fscanf(f,"%d",&inp[j][i]);
      if (inp[j][i]<0) { sign[j]=-sign[j]; inp[j][i]=-inp[j][i]; } //åñëè "-", ГІГ® ìåГ*ГїГҐГ¬ Г§Г*Г*ГЄ
       else 
        if (inp[j][i]==0) sign[j]=0;
     }
   }
  fclose(f);
  int max_i=0;
  bool all_minus=true; //ïðîâåðêГ* ГҐГ±ГІГј ëè Г·ГЁГ±Г«Г* >=0
  for (int i=0;i<N;i++)
   if (sign[i]!=-1) { all_minus=false; break; } 
  if (!all_minus)
   {
    for (int i=0;i<N;i++)
     {
      if (sign[i]==1) //åñëè ïëþñ
       {
        for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
         {
          a[i]=mult(a[i],inp[i][j]);
         } 
        max_i=i; //Г§Г*ïîìèГ*Г*ГҐГ¬ ГЁГ*äåêñ äëÿ Г¬Г*êñèìóìГ*
       }
     else if (sign[i]==0) { a[i].clear(); a[i].push_back(0); max_i=i; }
    }
    lnum max=a[max_i];  
    for (int i=0;i<N;i++)
     {
      if (sign[i]!=-1) //åñëè ïëþñ
       {
        if (i!=max_i) //åñëè Г*ГҐ òîò æå ýëåìåГ*ГІ
        if (checks(a[i],max)) //Г*[i]>=max
         { 
          max_i=i; 
          max=a[i]; 
         }
       }
     }    
   } 
  else
   {
    for (int i=0;i<N;i++)
     {
      for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
       {
        a[i]=mult(a[i],inp[i][j]);
       } 
     }
    lnum max=a[max_i]; 
    for (int i=0;i<N;i++)
     {
      if (i!=max_i)
      if (!checks(a[i],max)) 
       { 
        max_i=i; 
        max=a[i]; 
       }
    }
  }    
  f=fopen("output.txt","w");
  fprintf(f,"%d\n",max_i+1);
  fclose(f);
  return 0;
}
 
Текущее время: 03:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru