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
Таким образом, скорость исполнения кодов различается: 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.
Извиняюсь за приведение критериев задним числом..
Примечание: Точный код программ, использованных для тестирования, доступен по требованию.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.