IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> убираем дубликаты после сортировки в одномерном массиве
сообщение
Сообщение #1


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


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. получить упорядоченный по возрастанию массив, содержащий все различные числа данного массива)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Суть в том, что, поскольку к этому моменту массив уже отсортирован, то если есть два или более одинаковых элементов, они все будут стоять рядом. Мы проходим по массиву с начала до конца, увеличивая счетчик 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; { Закрываем тело цикла }


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 1:27
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name