Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ убираем дубликаты после сортировки в одномерном массиве

Автор: 18192123 31.10.2006 21:48

uses crt;
const n=10;
type
vect=array[1..n] of integer;
var
a:=vect;
i,j,t:integer;
begin
clrscr;
writeln (‘vvedite elementy massiva’);
for i:=1 to n do read (a[i]);
writeln (‘sortirovka’);
for j:=1 to n do
begin
for i:=n downto j+1 do
begin
if a[i]<a[i-1] then
begin
t:=a[i];
a[i]:=a[i-1];
a[i-1]:=t;
end;
end;
for i:=1 to n do write (a[i], ‘ ‘);
writeln;
end;
writeln;
writeln (‘massiv otsortirovan’);
(***** *****)
i:=0;
j:=1;
repeat
while (j<=n)and(a[j-1]=a[j]) do
j:=j+1;
if j<=n then
begin
i:=i+1;
a[i]:=a[j];
j:=j+1;
end;
until j>n;
(***** *****)
for j:=1 to n i do write (a[j],’ ‘);
readkey;
end.


объясните пожалуйста как можно подробнее суть выделенной части программы (в этой части убираются числа с одним и тем же значением)
если нужно, напоминаю задание (дан массив целых чисел размера n=10. получить упорядоченный по возрастанию массив, содержащий все различные числа данного массива)

Автор: lapp 1.11.2006 8:21

Суть в том, что, поскольку к этому моменту массив уже отсортирован, то если есть два или более одинаковых элементов, они все будут стоять рядом. Мы проходим по массиву с начала до конца, увеличивая счетчик j. Другой счетчик, i, служит для подсчета различных элементов.

i:=0;                                     { Подготавливаем счетчик различных элементов}
j:=1; { Подготавливаем счетчик всех элементов }
repeat { Цикл по всем элементам (главный) }
while (j<=n)and(a[j-1]=a[j]) do j:=j+1; { Пропуск одинаковых элементов. j увеличивается, i - нет}
if j<=n then begin { Проверка, что счетчик не вышел за границы массива }
i:=i+1; { Увеличиваем счетчик различных элементов }
a[i]:=a[j]; { Перекладываем элемент со старого места j на новое i }
j:=j+1; { Увеличиваем счетчик главного цикла}
end;
until j>n; { Условие остановки процесса по достижении границы массива}

Я честно разобрал работу фрагмента, но только все же хочу сказать, что он весьма неоптимален (вложено два цикла, что влечет увеличение числа проверок..). Буде мне пришлось бы делать нечто подобное, я сделал бы примерно так:
  i:=1;                        { Подготавливаем счетчик различных элементов}
for j:=2 to n do begin { Цикл по всем элементам, кроме первого }
if a[j]>a[i] then begin { Если следующий элемент не равен предыдущему, ..}
i:=i+1; { .. то увеличиваем счетчик различных элементов и ..}
a[i]:=a[j] { .. перекладываем элемент со старого места j на новое i }
end
end; { Закрываем тело цикла }

Автор: volvo 1.11.2006 16:44

Цитата
но только все же хочу сказать, что он весьма неоптимален (вложено два цикла, что влечет увеличение числа проверок..)
За проверки считать только сравнения между элементами массива? Тогда у меня делается всего на 1 проверку больше... И что? Все остальное - только контроль выхода за пределы массива... По скорости вообще не будем сравнивать (while/repeat даст выигрыш в 30% относительно for)... Так что, в следующий раз, просьба приводить критерии оптимальности...

Автор: lapp 2.11.2006 10:05

Цитата(volvo @ 1.11.2006 13:44) *
просьба приводить критерии оптимальности...

Извини, volvo, я не знал, что это твой код.
Согласен, критерии оптимальности весьма важны, и они могут варьироваться в зависимости от поставленной задачи. В данном случае я судил "на глазок", и мое замечание о циклах и проверках объясняет далеко не все. Скорее, я имел в виду логику алгоритма (о чем, собсно, и был вопрос), и, с моей точки зрения, вложенные циклы и многочисленные проверки затрудняют понимание новичком программы (думаю, мои комментарии - см. выше - являются к этому иллюстрацией). Я имел в виду это, но, помимо того, я думаю, что в чисто вычислительном контексте, все же мой вариант более предпочтителен. В данном случае я исхожу из компактности кода (при наглядности воплощения алгоритма) и скорости вычислений. Твое утверждение,
Цитата
while/repeat даст выигрыш в 30% относительно for

- на чем оно основано, и распространяется ли оно на использование переменной цикла с ее инкриминированием?
Так или иначе, желательно провести измерения, что я и сделал..

Я произвел сравнительный анализ, запуская этот фрагмент программы в двух вариантах (var 0, оригинальный, и var 1, модифицированный мной) в цикле (потребовалось более миллиона обращений цикла, чтобы надежно отловить разницу). Время выполнения измеряю по системным часам. Программа запускалась последовательно, несколько раз, разброс значений составил не более 10%. Результаты (наиболее характерные) приведены ниже (в единицах сек/100). Range check везде отключен. Процессор - Р4 ранних выпусков (кажется, 1.7ГГ).

FPC:
Running "c:\andreyk\pas\t034\to34.exe "
Var 0, t=153
Running "c:\andreyk\pas\t034\to34-1.exe "
Var 1, t=63

BP 7.0:
Borland Pascal  Version 7.0  Copyright © 1983,92 Borland International
Var 0, t=192
Var 1, t=121

Таким образом, скорость исполнения кодов различается:
FPC: 2.43 раза,
ВР: в 1.58 раза.

Далее, размеры кода программы, скомпилированный FPC, не отличаются и составляют:
11/01/2006 06:38 PM 30,208 to34-1.exe
11/01/2006 06:37 PM 30,208 to34.exe

Размеры программ, скомпилированные ВР7 показывают небольшое отличие:
11/01/2006 06:45 PM 3,424 TO34-1.EXE
11/01/2006 06:45 PM 3,456 TO34.EXE
- снова в пользу варианта 1.

Извиняюсь за приведение критериев задним числом.. smile.gif

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