Иванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ (1075619), страница 4
Текст из файла (страница 4)
рисунок 3.6).НачалоВводn, А(n)k:=3i:=1,n div 3нетA[k]mod2=0A[k]:=A[k] mod 5даA[k]:=0k:=k+3ВыводA(k)КонецРисунок 3.6 – Схема алгоритма замены каждого третьего элемента массива243.1.3 Изменение порядка следования элементов без изменения размеров исходного массива. Сортировка массиваПримерами подобной обработки служат: замена значений некоторых элементов на другие в соответствии с определенными правилами, сортировка массивов по убыванию, возрастанию, и по любому другому признаку, перестановки исдвиги элементов различного характера и др.
Особенностью этого класса задачявляется то, что, несмотря на постоянство количества элементов массива, для перестановки или замены элемента сначала его необходимо найти. Таким образом,чтобы преобразовать массив, требуется несколько раз его просмотреть. Поэтомудаже для одномерного массива требуется применение нескольких вложенныхциклов. Рассмотрим несколько типовых приемов.Пример 3.7. Переформировать массив таким образом, чтобы сначала шливсе положительные элементы, затем отрицательные и в конце – нулевые.Прежде всего, задачу сложно решить, не используя дополнительный массив,поскольку запись элементов происходит в заранее неизвестном порядке.Также необходимо учитывать, что номера элементов в исходном и новоммассиве не совпадают.
В качестве индекса исходного массива мы, как и ранее, будем использовать переменную цикла. А для указания номера элемента в новоммассиве нам понадобится специальный индекс(ы), который придется изменятьотдельным оператором.И последнее, осуществить требуемое переформирование массива за одинпроход невозможно, поскольку количество элементов каждого типа неизвестно.Задачу можно решить, используя три цикла, в которых в новый массив последовательно переписываются сначала положительные элементы, затем отрицательныеи наконец – нулевые. Однако возможно и использование двух циклов: в первомперепишем в начало нового массива положительные элементы, а в конец – нулевые, начиная с последнего, а во втором просто допишем в середину отрицательные элементы.Окончательный вариант алгоритма приведен на рисунке 3.7.25НачалоВводn, А(n)k:=1m:=ni:=1,nA[i] > 0данетдаB[k]:=A[i]A[i] = 0нетB[m]:=A[i]k:=k+1m:=m-1i:=1,nA[i] < 0нетдаB[k]:=A[i]k:=k+1ВыводB(n)КонецРисунок 3.7 – Схема алгоритма перестановки элементов массиваОднако наиболее распространенными задачами второго класса являютсясортировки массивов.Сортировка – это изменение порядка элементов в массиве таким образом,что значения элементов становятся упорядоченными по некоторому закону.
Напрактике сортируемые массивы обычно имеют большую размерность, поэтомудля любого алгоритма сортировки оценивают вычислительную сложность, которая определяется зависимостью времени сортировки от количества сортируемыхэлементов. Чем меньше это время, тем более эффективен алгоритм. По той жепричине интерес представляют такие методы сортировки, которые позволяютэкономно использовать оперативную память, т.е.
не требуют дополнительныхмассивов.Сортировка с помощью выбора. Сортировка с помощью выбора представляет собой один из самых простых методов сортировки. Он предполагаетследующую последовательность действий:26 выбирается наименьший элемент из всего массива; найденный наименьший элемент меняется местами с первым элементом; затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент массива.Пример алгоритма сортировки с помощью выбора приведен на рисунке3.8.Н ачал оВводn, A (n)j:= 1,n-1 ,1m in := A [j]im in:= ji:= j+ 1,n ,1A [i]< m inн етдаm in := A [i]im in:= iA [im in ]:= A [j]A [j]:= m inВы во дA [n ]Кон ецРисунок 3.8 – Схема алгоритма сортировки выборомСортировка с помощью обмена.
Алгоритм прямого обмена основываетсяна сравнении и смене мест для пары соседних элементов. Сравнения продолжаютдо тех пор, пока не будут упорядочены все элементы. Такой метод широко известен под именем «пузырьковая сортировка», т. к. элементы массива можно рассматривать как пузырьки, которые поднимаются к началу массива.Пусть, например, массив состоит из элементов (2, 5, 12, 1, 8, 4). Если сортировать массив по возрастанию, то после первого «прохода» по массиву мы получим следующий массив (2, 5, 1, 8, 4, 12).
После второго «прохода» - (2, 1, 5, 4, 8,12), после третьего – (1, 2, 4, 5, 8,12).Анализ показывает, что сортировку можно прекратить, когда при очередномпроходе не понадобилось выполнить ни одной перестановки. Кроме того, следуетучесть, что после каждого прохода по меньшей мере один элемент становится наместо, поэтому можно каждый раз сокращать количество просматриваемых элементов. Схема алгоритма сортировки с помощью обмена представлена на рисунке3.9.27Начал оВводn, A (n)k:= 1i:= 0н етk< > 0даk:= 0j:= 1,n-i,1A[j]> A[j+ 1]н етдаb:= A[j]A[j]:= A[j+ 1 ]A[j+ 1]:= bk:= k+ 1Вы во дA(n )Кон ецРисунок 3.9 – Схема алгоритма обменной сортировкиСортировка методом вставки.
Алгоритм сортировки с помощью вставкиможно описать следующим образом. При каждом шаге, начиная с i=2, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность на нужное место. В реальном процессе поиска подходящего места удобно сначала сравнивать извлеченный элемент с очередным элементом aj, азатем либо aj сдвигается вправо, либо ai вставляется на освободившееся место.Процесс поиска может закончиться при выполнении одного из двух следующихусловий: либо найден элемент aj меньший, чем ai, либо достигнут левый конецмассива.Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом «барьера». Дляэтого необходимо расширить диапазон индекса в описании массива от 0 до n. Алгоритм сортировки приводится на рисунке 3.10.28Н ачалоВв одn, A (n)i:= 2, n, 1B:= A [i]A [0 ]:= Bj:= i- 1A [j]> Bн етдаA [j+ 1]:= A [j]j:= j- 1A [j]:= BВы в о дA (n )Кон ецРисунок 3.10 – Схема алгоритма сортировки вставкамиМетод Шелла.
Метод состоит в том, что упорядочиваемый массив делитсяна группы таким образом, что в каждой группе находятся элементы, отстоящиедруг от друга на расстоянии d. Каждая группа сортируется методом вставки, затеммассив делится на новые группы с шагом d-1 и т.д. пока количество групп не станет равным единице. Обычно d выбирается таким образом, чтобы в каждой группе находилось два элемента, т.е. d=[n/2].3.1.4Переформирование массива с изменением его размеровПримерами этого класса задач могут служить: вычеркивание и вставка элементов, отвечающих определенным условиям или обладающих заданными признаками и т. д.
При этом, для удаления или добавления элемента может производиться как поэлементная, так и выборочная обработка элементов массива. Особенностью этого класса задач является изменение размеров исходного массива.Кроме того, вычеркивание или вставка элементов требуют сдвига всех элементовтой части массива, которая расположена после удаляемого или вставляемого элемента.
Реализация алгоритмов решения задач этого типа, как правило, требуетвложенных циклов. При этом, внутренний цикл для сдвига можно выполнить, используя счетный цикл. Внешний цикл обхода содержит переменную верхнююграницу, поэтому лучше использовать циклы с пред или пост условием. Если насоответствие условию проверяются все элементы, то параметр внешнего цикламеняется на 1. Однако после сдвига на месте старого анализируемого элементаможет оказаться элемент, отвечающий требуемому условию.
Поэтому для определения количества повторений цикла сдвигов необходим цикл с пост условием, ане оператор ветвления (используется три вложенных друг в друга цикла). При выборочном анализе элементов массива параметр внешнего цикла меняется на раз-29ную величину, в зависимости от наличия или отсутствия сдвига и для определения выполнять сдвиг или нет, можно использовать оператор условной передачиуправления. При большом количестве удаляемых или вставляемых элементов вычислительная сложность таких алгоритмов достаточно велика.Пример 3.7.
Пусть необходимо вычеркнуть из массива целых чисел все числа, кратные 5.Для решения задачи можно предложить два алгоритма: просматривая массив, будем находить очередной удаляемый элемент, азатем путем сдвига переносить все элементы, расположенные после него, затираяудаляемый элемент. Полученный массив окажется на 1 элемент меньше. Изменивразмер массива, следует продолжить просмотр элементов (см.
рисунок 3.11, а); просматривая массив, будем переписывать все остающиеся элементы наочередное место. В этом случае потребуется две переменные индекса: в качествепервой будем использовать переменную цикла, а вторую будем менять независимо после записи очередного остающегося элемента (см. рисунок 3.11, б).НачалоВводn, А(n)НачалоВводn, А(n)i: = 1нетiÖnдаk:=0даA[i]mod5=0нетi:=2,nj:=i+1,nдаA[j-1]:=A[j]i:=i+1A[i]mod5=0нетдаk:=k+1A[k]:=A[i]n := n-1ВыводA(n)ВыводA(k)КонецКонецабРисунок 3.11 – Схемы алгоритма решения задачи:а – с двумя циклами; б – с одним цикломВ первом алгоритме внешний цикл не может быть счетным, поскольку всчетном цикле переменная i меняется при каждой итерации, а нам не надо ее менять, если i-й элемент удаляется, поскольку на его место в результате сдвига переносится следующий, еще не проверенный элемент.
Замена цикла на цикл-покапозволяет менять i только, когда это необходимо.Несложно видеть, что вычислительная сложность второго алгоритма меньше, чем первого. Но первый алгоритм легче воспринимается. Практика показыва-30ет, что второй способ практически всегда применим, если элементы из массиваудаляются. При добавлении элементов второй способ не применим, посколькупри отсутствии дополнительного массива переписываемые элементы рано илипоздно начнут затирать еще не проверенные элементы массива.Пример 3.8. Предположим, нам необходимо переформировать массив вещественных чисел, добавив в него нулевые элементы после положительных элементов, стоящих на четных местах.В данной задаче без второго цикла не обойтись. Причем необходимоучесть, что при сдвиге элементов ни один элемент не должен быть затерт, поэтому двигать элементы придется с последнего.Кроме того, необходимо обеспечить обход элементов, расположенных начетных местах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
