Форум программистов, компьютерный форум, киберфорум
PascalABC.NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 09.02.2020
Сообщений: 2

Как оптимизировать код?

09.02.2020, 12:35. Показов 581. Ответов 4

Студворк — интернет-сервис помощи студентам
Условие задачи(для понимания):
Несколько учеников 10А класса физико-математической школы поспорили, кто из них
самый популярный в школе. В 10А были собраны самые способные ребята, поэтому они
сразу же осознали необходимость введения терминологической базы для того, чтобы спор
оставался конструктивным. После долгих обсуждений было принято следующее определение
популярности:
Популярность ученика X определяется числом P – количеством учеников, которые
являются друзьями ученика X или же являются друзьями друзей ученика X за исключением
самого ученика X.
Ваша задача – помочь ученикам 10А установить истину в их споре.

Мои действия:
У меня есть четыре одномерных массива и 1 матрица. Что я делаю в начале? - уже при вводе я беру пары и распределяю их в матрице, которая не имеет определенного размера, т.е. ее размеры зависят только от кол-ва человек, имеющих друзей(люди без друзей не учитываются). к ней приложены 2 одномерных массива, один из которых отвечает за связь между номером ученика и его друзьями, а другой показывает длинну массива в матрице с индексом. Т.е. все это нужно для экономии места и времени работы программы.

Теперь я беру и начинаю перебирать каждого ученика по-отдельности. Сначала я записываю его и его друзей в еще один одномерный, временный массив - массив исключений, сразу же записываю кол-во его друзей в массив результатов. Потом перебираю каждого его друга и результаты записываю в тот же массив результатов. В цикле перебора я сразу нахожу максимальное кол-во друзей.

Остается только вывести кол-во учеников с максимальной популярностью, а так же их номера В ПОРЯДКЕ ВОЗРАСТАНИЯ. Из-за последнего приходится создавать еще один массива и при нахождении людей с максимальной популярностью записывать их туда. Он нужен для экономии времени, опять же, да и мы не выведем без него все числа в порядке возрастания. Теперь при помощи еще одного алгоритма вывожу оставшийся массив в порядке возрастания. Ответ готов.

Программа:
Pascal
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
program n_4;
 
function FindI(para1:integer;A1:array of integer;schet:integer):integer;
var p:integer;
begin
  p:=-1;
  for var i:=0 to schet-1 do 
    if para1=A1[i] then
      p := i;
  FindI:=p;
end;
 
function Condition_0(A: integer; exceptions: array of integer; k: integer): boolean;
var
  boo: boolean;
begin
  boo := false;
  for var i := 0 to k - 1 do 
    if (A = exceptions[i])then if A<>0 then boo := true;
  Condition_0 := boo;
end;
 
 
var
  N, M, para1, para2,schet,ID,length,k,p,maxp,t,lya, max: integer;
  A2: array of array of integer;
  A1,X: array of integer;
  s: text;
  exceptions, total: array of integer;
  countManager: array of integer;
 
begin
  
{------------------------------------------------------------------------------------------}
  assign(s, 'input.txt');
  reset(s);
  read(s, N);
  readln(s, M);
  setlength(countManager, n);
  
  setlength(A1,1);
  setlength(A2,1);
  
  schet:=1;
  setlength(countManager,1);
  for var childCount:=0 to m-1 do
  begin
    read(s, para1);
    readln(s, para2);
    ID:=FindI(para1,A1,schet);
    if ID=-1 then 
    begin
      A1[schet-1]:=para1;
      setlength(A1,schet+1);
      setlength(countManager,schet);
      countManager[schet-1]:=2;
      setlength(A2,schet);
      setlength(A2[schet-1],1);
      A2[schet-1,0]:=para2;
      schet:=schet+1;
      end
    else if ID>=0 then
    begin
      length:=countManager[ID];
      setlength(A2[ID],length+1);
      A2[ID,length-1]:=para2;
      countManager[ID]:=countManager[ID]+1;
      end;
      
    ID:=FindI(para2,A1,schet);
    if ID=-1 then 
    begin
      A1[schet-1]:=para2;
      setlength(A1,schet+1);
      setlength(countManager,schet);
      countManager[schet-1]:=2;
      setlength(A2,schet);
      setlength(A2[schet-1],1);
      A2[schet-1,0]:=para1;
      schet:=schet+1;
      end
    else if ID>=0 then
    begin
      length:=countManager[ID];
      setlength(A2[ID],length+1);
      A2[ID,length-1]:=para1;
      countManager[ID]:=countManager[ID]+1;
      end;  
    end;
    
  //   /\                                                                              |\
  //  /  \                                                                             |  \
  //   ||   Это составление матрицы, которая связана с массивом при помощи ID, где ID    \\
  //   ||     показывает какие друзья есть у ученика под номером (организация ввода)      \\
  //   ||                                                                                  \\
  //   ||                                                                                   \\
  //   ||                                                                                    \\
    {---------------------------------------------------------------------------------------}
  
  setlength(total, schet-1);
  
  for var index := 0 to schet-2 do 
  begin
    k := 0;
    p:=0;
    setlength(exceptions, k);  //сброс исключений
    
    for var jndex := 0 to countManager[index] - 2 do
    begin
      setlength(exceptions, k + 1);
      k := k + 1;
      
      exceptions[jndex] := A2[index, jndex];
    end;
    
    {--------------------------} 
    setlength(exceptions, k + 1);
    k := k + 1;
    exceptions[k - 1] := A1[index];
    {--------------------------}
    
    for var jndex := 0 to countManager[index] - 2 do
    begin
      length:=countManager[FindI(A2[index,jndex],A1,schet)];
      for var fndex := 0 to length - 2 do
      begin
        if Condition_0(A2[FindI(A2[index,jndex],A1,schet), fndex], exceptions, k) = false then  //Ищутся друзья друзей, которые не являются исключением
        begin
          setlength(exceptions, k + 1);
          exceptions[k] := A2[FindI(A2[index,jndex],A1,schet), fndex];
          k := k + 1;
          p := p + 1;
        end;
      end;
      
      total[index] := p+countManager[index]-1;
      if maxp<total[index] then
        maxp:=total[index];
    end;
  end;
  {--------------------------------------------}
 
  write(maxp,' ');
  
  lya:=0;
  for var i := 0 to schet-2 do
    if maxp = total[i] then
    begin
      t := t + 1;
      setlength(x,lya+1);
      x[lya]:=A1[i];
      lya:=lya+1;
      end;
  writeln(t);
  
  for var i := 1 to lya-1 do
        for var j := 0 to lya-i-1 do
            if x[j] > x[j+1] then 
              begin
                t := x[j];
                x[j] := x[j+1];
                x[j+1] := t
            end;
    
  for var i:=0 to lya-1 do
    write(x[i],' ')
  end.
Вопрос: Как можно оптимизировать работу программы так, чтобы при больших значениях она работала меньше 1-ой секунды (большие значения - это около 7тыс. пар). Вот. Спасибо.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
09.02.2020, 12:35
Ответы с готовыми решениями:

Как оптимизировать код?
ch : char; ... If ch='1' then Write(F2, ch); If ch='2' then Write(F2, ch); If ch='3' then Write(F2, ch); If ch='4' then...

Нужно оптимизировать код
Не могу понять как можно оптимизировать данную программу: var s: string; s1, s2, s3, i, n: integer; a: arrayof string; ...

Как оптимизировать код?
Есть такой кусок кода: for j:=0 to Memo2.Lines.Count-1 do begin if Pos('кв.А', Memo2.Lines.Strings) &gt;0 then ...

4
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
09.02.2020, 13:19
Ограничения? Пример входных/выходных данных.
0
0 / 0 / 0
Регистрация: 09.02.2020
Сообщений: 2
09.02.2020, 13:27  [ТС]
Ограничения:
По памяти:<64MB;
По времени:<1sec;
Данные(буквы в коде отличаются от описанного ниже, например k в условии = m в коде):
Входные данные
В первой строке входного файла через пробел записаны два целых числа N и K
(1 ≤ N ≤ 103
, 1 ≤ K ≤ 105
) – общее кол-во учеников в школе и количество пар друзей.
В каждой из следующих K строк через пробел записано по два целых числа Xi и Yi
(1 ≤ Xi, Yi ≤ N) – номера учеников, которые являются друзьями (если Xi дружит с Yi, то Yi также
дружит с Xi).
Выходные данные
В первой строке выходного файла необходимо через пробел вывести два целых числа
P и M, где P – максимальная популярность среди учеников школы, а M – количество
учеников, имеющих максимальную популярность.
Во второй строке выходного файла через пробел необходимо вывести по возрастанию
значений M целых чисел Zi – номера учеников школы, имеющих наибольшую популярность.

Например:
Входные данные:
10 5
1 3
6 5
3 5
6 3
5 1
Выходные данные:
4 3
3 5 6
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
09.02.2020, 13:50
Судя по ограничениям должно O(n2) зайти. Пробуйте статическую матрицу NxN, а не динамические массивы.
1
 Аватар для Sun Serega
2355 / 1458 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
09.02.2020, 21:04
Статические массивы всегда медленнее динамичных. Но array[,] будет таки быстрее чем array of array. Но подойдёт только если нужна именно матрица, а не массив массивов.

А ещё глобальные переменные (var до begin) всегда в несколько раз медленнее локальных (var после begin). Во сколько раз - зависит от процессора, у меня раз в 5.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
09.02.2020, 21:04
Помогаю со студенческими работами здесь

как оптимизировать код?
Есть несколько dbf файлов. Из них в разные обьекты нужно получить список строк. Для этого написал класс public class connDBF { ...

Как оптимизировать код?
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;iomanip&gt; using...

Как оптимизировать код
Доброй ночи господа у меня к вам такая просьба как можно упростить данный код? #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...

Как оптимизировать код?
как привести это в красивый вид? если учесть что таких label будет over 100 А название будут содержать Label++Название строки ...

Как оптимизировать код?
Вот такой код, написанный для микроконтроллера импульсного блока питания. Просто интересно мнение, что можно поменять и изменить для...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru