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:=1to n doread (a[i]);
writeln (‘sortirovka’);
for j:=1to n dobeginfor i:=n downto j+1dobeginif a[i]<a[i-1] thenbegin
t:=a[i];
a[i]:=a[i-1];
a[i-1]:=t;
end;
end;
for i:=1to n dowrite (a[i], ‘ ‘);
writeln;
end;
writeln;
writeln (‘massiv otsortirovan’);
(***** *****)
i:=0;
j:=1;
repeatwhile (j<=n)and(a[j-1]=a[j]) do
j:=j+1;
if j<=n thenbegin
i:=i+1;
a[i]:=a[j];
j:=j+1;
end;
until j>n;
(***** *****)for j:=1to n i dowrite (a[j],’ ‘);
readkey;
end.
объясните пожалуйста как можно подробнее суть выделенной части программы (в этой части убираются числа с одним и тем же значением) если нужно, напоминаю задание (дан массив целых чисел размера n=10. получить упорядоченный по возрастанию массив, содержащий все различные числа данного массива)
Lapp
1.11.2006 4: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 thenbegin{ Проверка, что счетчик не вышел за границы массива }
i:=i+1; { Увеличиваем счетчик различных элементов }
a[i]:=a[j]; { Перекладываем элемент со старого места j на новое i }
j:=j+1; { Увеличиваем счетчик главного цикла}end;
until j>n; { Условие остановки процесса по достижении границы массива}
Я честно разобрал работу фрагмента, но только все же хочу сказать, что он весьма неоптимален (вложено два цикла, что влечет увеличение числа проверок..). Буде мне пришлось бы делать нечто подобное, я сделал бы примерно так:
i:=1; { Подготавливаем счетчик различных элементов}for j:=2to n dobegin{ Цикл по всем элементам, кроме первого }if a[j]>a[i] thenbegin{ Если следующий элемент не равен предыдущему, ..}
i:=i+1; { .. то увеличиваем счетчик различных элементов и ..}
a[i]:=a[j] { .. перекладываем элемент со старого места j на новое i }endend; { Закрываем тело цикла }
volvo
1.11.2006 12:44
Цитата
но только все же хочу сказать, что он весьма неоптимален (вложено два цикла, что влечет увеличение числа проверок..)
За проверки считать только сравнения между элементами массива? Тогда у меня делается всего на 1 проверку больше... И что? Все остальное - только контроль выхода за пределы массива... По скорости вообще не будем сравнивать (while/repeat даст выигрыш в 30% относительно for)... Так что, в следующий раз, просьба приводить критерии оптимальности...
Lapp
2.11.2006 6: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
Таким образом, скорость исполнения кодов различается: 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.
Извиняюсь за приведение критериев задним числом..
Примечание: Точный код программ, использованных для тестирования, доступен по требованию.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.