Иванова Г.С. - Основы программирования
.pdf4, Структурные типы данных
ReadLn(n); WriteLnCВведите массив.'); for /V=7 to п do Read(a[i]); ReadLn;
for i:-2 to n do {начиная со второго элемента до конца массива} begin
B:-a[i]; {запоминаем i-й элемент}
afOJ:=^B; {этот же элемент записываем в а[0] - это барьер} j:=i'l; {индекс i запоминаем в j}
while B<a[/J do {пока очередной рассматриваемый элемент
больше i-ro элемента}
begin
^//"^^/•'"^//У/ {сдвигаем элемент} у;=у-7; {уменьшаем j на 1}
end;
а[/+1]:=В; {как только найдено место, туда записывается В} end;
WriteLnCОтсортированный массив:'); for i:=l to п do Write(a[i]:6:2); WriteLn;
End
Оценим временную сложность данного метода, также определив коли чество операций сравнения.
Для поиска места i-ro элемента каждый раз потребуется выполнить от 1 до i-1 операций сравнения, т.е. в среднем i/2 операций сравнения. Значение i изменяется от 2 до п, т.е. выполняется п-1 проход, в каждом из которых про исходит в среднем от 1 до п/2 сравнений. Таким образом, суммарно в сред нем для решения задачи требуется выполнить (п-1)(п/2 + 1)/2 = (п^ + п - 2)1А операций сравнения. Откуда вычислительная сложность метода в среднем также равна О^рСп^), хотя время выполнения примерно в два раза меньше, чем у предыдуш.его метода. Интересно, что в данном случае вычислительная сложность зависит от исходного расположения элементов массива.
Так, в лучшем случае, когда массив уже упорядочен, поиск места встав ки требует одного сравнения для каждого элемента, и количество сравнений равно п-1. Соответственно, вычислительная сложность равна 0^(n).
В худшем случае, если элементы массива в исходном состоянии распо ложены в обратном порядке, поиск места вставки для каждого элемента по требует: 1, 2, 3, ..., п-1 сравнения, следовательно, всего потребуется п(п-1)/2 операций сравнения, т. е. время выполнения программы примерно совпадет со временем программы, реализующей метод выбора. Значит вычислитель ная сложность в худшем, так же как в среднем, равна Oj^(n2).
Таким образом, за счет ускорения сортировки в лучших случаях данный метод имеет лучшие временные характеристики, чем предыдущий.
101
Часть 1. Основы алгоритмизации и процедурное программирование
Метод обменов» Алгоритм прямого обмена основывается на сравнении пары соседних элементов. Если расположение элементов не удовлетворяет условиям сортировки, то их меняют местами. Сравнения и перестановки продолжают до тех пор, пока не будут упорядочены все элементы. Опреде лить, что элементы упорядочены, можно, считая количество выполненных перестановок: если количество перестановок равно нулю, то массив отсорти рован (рис. 4.17).
Простейший алгоритм сортировки с помощью обмена представлен на рис. 4.18. Ниже приведена программа, реализующая данный алгоритм.
7.8 -6.3 5.8 1.2 8.4 4.5
1-й |
|
|
|
|
|
|
|
к |
|
|
|
-6.3 |
5.8 |
1.2 |
7.8 |
4.5 |
8.4 |
Ш |
|
||||
проход |
|
||||||||||
2-й |
|
|
|
ГТл |
Ш П} |
|
|||||
-6.3 |
1.2 |
5.8 |
4.5 |
7.8 |
|
||||||
проход |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
п-1 |
|
|
|
|
|
|
|
|
3-й |
|
|
^-—^ |
|
|
к |
|
|
|||
-6.3 1 |
1.2 1 4.5 1 |
5.8 1 |
7Л 1 |
8.4 1 |
1 1 |
1 |
|||||
проход |
|||||||||||
|
п-2 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|||
4-й |
|
|
|
|
5.8 ( 1Л { |
к |
|
|
|||
-6.3 1 |
1.2 1 4.5 1 |
8.4 | |
1 0 1 |
|
|||||||
проход |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
||
п-З
-6.3 1.2 4.5 5.8 7.8 8.4
Рис. 4.17. Сортировка обменом |
Рис 4.18. Схема алгоритма |
сортировки обменом |
102
|
|
|
4. Структурные типы данных |
||
Program ex; |
|
|
|
|
|
Var а: array[L.20] |
of Real; |
ij,nj,k: integer; |
b:real; |
||
Begin |
|
|
|
|
|
WriteLn(*Введите размер массива N< =20'); |
|
||||
ReadLn(n); |
|
|
|
||
for i := 1 ton do Read(a[i]); |
|
|
|||
ReadLn; |
|
|
|
|
|
WriteLnCИсходный массив:'); |
|
||||
for i := J to n do Write(a[i]:7:2); |
|
||||
WriteLn; |
|
|
|
|
|
k:-l; |
{количество перестановок, начальное значение не равно О } |
||||
i;=7; |
{номер очередного просмотра, в начале равен 1} |
||||
while koQ |
do |
{пока есть перестановки} |
|
||
begin |
|
|
|
|
|
к:-0; |
{обнуляем количество перестановок} |
||||
forj:-l |
to п4 do {цикл сравнения соседних элементов} |
||||
|
if (^Ш^^О'^Ч ^f^^^ {если предыдущий элемент больше, то} |
||||
|
|
begin |
{осуществляем перестановку} |
||
b:=a[j];
a[i+lj:^b;
к:=к-^1; {счетчик перестановок увеличиваем на 1} end;
i;=/+i; {увеличиваем номер просмотра на 1} end;
WriteLn('Отсортированный массив *); for i := J to п do Write(a[i]:7:2); WriteLn;
WriteLnC Количество проходов \ i:3); End
Оценим вычислительную сложность данного метода. Очевидно, что она сильно зависит от исходного расположения элементов массива. Так, в луч шем случае, если массив был уже отсортирован, потребуется выполнить п-1 сравнение для проверки правильности расположения элементов массива, т. е. вычислительная сложность в лучшем 0^(п).
В худшем случае, если массив отсортирован в обратном порядке, будет выполнено п-1, п-2, ...1 операций сравнения, т. е. всего (п2-п)/2 операций сравнения, следовательно, вычислительная сложность в худшем определяет ся как Ох(п2).
Выполнить усредненную оценку данного метода достаточно сложно, так как в отличие от предыдущих случаев зависимость времени выполнения от количества неправильно стоящих элементов не является линейной. Напри мер, два элемента, стоящие на своем месте в начале массива, практически не
103
4. Структурные типы данных
Проверка и удаление строк:
к:=0
Для i:=l, п, 1
Определение максимального элемента max i-й строки. Если тах?^В,
то к:=к+1
Перемещение i-й строки на к-е место
все-если Все-цикл
Все.
Определение максимального элемента строки - уже известная нам опе рация (см. пример 4.1).
Перемещение строки выполняется поэлементно.
Перемещаем i-ю строку на к-е место: Для]= 1,т, 1
A[kJ]:=A[ij]
Все-цикл.
Все.
Ниже представлен полный текст программы.
Program ex;
Var а: arrayfI..JO,LJOJ of integer; В, max, n, m, k, i,j: integer;
Begin
WriteLnCВведите размеры матрицы n,m<=10'); ReadLn(n,m);
WriteLnCВведите \n:4,' строк no \m:4,' элементов '); for i:'=l to n do
begin
forj:=l to m do ReadfafiJJJ; ReadLn;
end;
WriteLnCВведите значение В:'); ReadLn(B);
WriteLnCИсходный массив'); for i:=l to n do
begin |
|
forj:=l |
to m do Write(a[iJ]:4); |
WriteLn; |
|
end; |
|
k:=0; |
{количество остающихся строк} |
105
Часть 1. Основы алгоритмизации и процедурное программирование
повлияют на время сортировки, а два элемента, стоящих на своем месте в конце массива, вызовут ее досрочное завершение. По результатам тестирова ния можно считать, что в среднем этот метод сортировки требует примерно в два раза меньше времени, чем предыдущий. Вычислительная сложность в среднем данного метода О^рСп^).
Примечание. По материалам данного раздела можно сделать ошибочный вывод, что все методы сортировки в среднем имеют вычислительную сложность 0(п2). Методы сортировки, рассмотренные в данном разделе, не являются самыми быстрыми, они просто самые простые и потому используются чаще всего. Существуют методы быстрой сортировки, которые обес печивают в среднем и даже в худшем вычислительную сложность 0(п log2 п). Разработаны также методы, обеспечивающие для специальных данных вычислительную сложность Оср(п) [3,5]. Один из методов быстрой сортировки будет рассмотрен в разделе 7.5.
4.4. Практикум. Обработка матриц
Рассмотрим наиболее распространенные приемы программирования об работки матриц. Следует отметить, что программирование операций всех классов для матриц имеет свою специфику, связанную с тем, что матрица, фактически, является массивом одномерных массивов. Это значит, что для каждой операции существует гораздо больше различных вариантов выполне ния.
Использование приемов обработки одномерных массивов. При ре шении некоторых задач обработки многомерных массивов могут быть выде лены подзадачи, при программировании которых можно использовать при емы обработки одномерных массивов.
Декомпозицию целесообразно выполнять, используя метод пошаговой детализации.
Пример 4.10. Разработать программу, удаляющую из матрицы A(n,m), где п < 10, m < 10, строки, максимальный элемент которых равен В.
На первом этапе определяется структура программы:
Программа:
Ввод исходной матрицы. Проверка и удаление строк. Вывод матрицы.
Конец программы.
Из выделенных подзадач ввод и вывод матрицы представляют достаточ но простые фрагменты, реализующиеся вложенными счетными циклами. Детализируем подзадачу проверки и удаления строк. Для удаления строки будем использовать прием, рассмотренный в примере 4.6.
104
Часть 1. Основы алгоритмизации и процедурное программирование
for i:=l to п |
do |
{цикл по строкам} |
begin |
|
|
max:-a[ij]; |
{исходное значение максимума строки} |
|
forj:-l to т do |
{цикл поиска максимума строки} |
|
if a[ij]>max then max:-afiJJ; |
||
ifmaxoB |
then {если максимум строки не равен В} |
|
begin |
|
{то оставляем строку} |
к:=к+1; |
{увеличиваем количество остающихся строк} |
|
forj:=l to т do afkjj:=afi,jj; {копируем строку на место} |
||
end; |
|
|
end; |
|
|
ifkoO then |
{если в матрице осталась хоть одна строка} |
|
begin |
|
|
ШгИеЬп('Сформированная матрица *); |
||
for |
i:^l to к do |
|
begin |
|
|
|
forj:^l |
to m do Write(a[iJ]:4); |
|
WriteLn; |
|
end; |
|
|
end |
|
|
else |
|
|
WriteLn(*Bce строки матрицы удалены');
End
В некоторых случаях применение приемов обработки одномерных мас сивов к матрицам результатов не дает. В основном это задачи, связанные с различными вариантами обхода матриц, и задачи обработки разных групп элементов в матрице.
Обход элементов матрицы. На рис. 4.19 показано несколько способов обхода элементов матрицы. Для каждого из представленных способов, кроме последнего, который выполняется по правилу выхода из лабиринта, можно предложить закон, связывающий индексы между собой.
Самые простые обходы: по строкам и столбцам. Их реализацию полезно помнить. Обход по строкам реализуется вложением циклов:
for i:=l |
ton |
do |
forj:-l |
to m do |
|
|
<обработка элемента a[iJ]> |
|
При обходе по столбцам меняются местами циклы по строкам и столб |
||
цам: |
|
|
forj:=l |
to т do |
|
for |
/.=7 to n do |
|
|
<обработка элемента a[ij]> |
|
106
4, Структурные типы данных
Ьг гф |
Г |
t |
44+ |
|
1 |
1 1 |
|
шШ
ш
и Jf л
Рис. 4Л9. Примеры вариантов обхода матрицы:
А~ обход по строкам; б ~ обход по столбцам; в - обход «змейкой»;
г- обход по спирали; д - обход «змейкой по диагоналям»; е ~ «лабиринт»
Впрочих случаях закономерности формирования индексов приходится исследовагь, чтобы предложить соответствующий вариант реализации.
Вкачестве примера рассмотрим закономерность формирования индек сов диагоналей квадратной матрицы (рис. 4.20).
Определив закономерности, сравнительно легко можно построить цикл прохода по диагонали матрицы. Например, для диагонали, проходящей через элемент [р,к] параллельно главной, получаем:
к |
|
Ч1.4 |
у ^ |
Побочная диагональ: i + j = п+1 |
|||
1,2 |
2.5 |
Закономерность формирования индексов |
|||||
2,1 |
|
|
2J |
|
|
|
|
ч3.2 |
X3.4 |
п диагоналей, проходящих чер^ элемент [р, к], |
|||||
3.1 |
|
3,5 |
а) параллельно главной: |
! -j'^p-k, |
|||
|
|
|
7^\ |
X |
/ |
б) параллельно побочной: i + j = р + к. |
|
4,1 |
|
|
4,3 |
Количество элементов диагонали: |
|||
х^ |
|
4.5 |
а) параллельной главной: |
s ~ п - |р • к|, |
|||
5,1 |
5,2 |
|
5,3 |
5,5 |
б) параллельной побочной: s = п - |п + I - (р + к).| |
||
|
5,4 |
|
|
||||
|
|
|
|
|
\ |
Главная диагональ: i = j |
|
Рис. 4.20, Закономерности формирования индексов диагоналей квадратной матрицы
107
Часть L Основы алгоритмизации и процедурное программирование
if р'к>0 then s:=n-p+k else s:=n-k-^p; for i:=l to s do
<обработка элемента a[i,i-p+k]>
Пример 4.1L Разработать программу, которая формирует матрицу, представленную на рис. 4.21.
Для решения задачи необходимо осуществить обход матрицы змейкой, присваивая его элементам требуемое значение. Из рисунка видно, что во всех нечетных строках значения элементов возрастают
монотонно на единицу слева направо, а во всех четных - справа налево. Та кое изменение можно описать формулами:
для четной строки - (i-l)*n + п - j + 1, для нечетной - n*(i -1) + j ,
где i - номер рассматриваемой строки, а j ~ номер столбца в ней.
Значит, в программе можно построчно обойти все элементы и присвоить им значения в соответствии с указанными формулами.
Однако можно и просто реализовать данный вид обхода, присваивая эле ментам значение, которое каждый раз увеличивается на единицу. Программа, приведенная ниже, реализует второй вариант.
Program exi |
|
|
|
|
Var а: array[1..3J.A] |
of integer; |
|||
k |
ij:integer; |
|
|
|
Begin |
|
|
|
|
k:-l; |
|
|
|
|
for |
i:=l |
to 3 do |
|
|
|
if (i mod 2)=0 then {если номер строки четный} |
|||
|
|
forj:-4 |
downto 1 do {обходим справа налево} |
|
|
|
begin |
|
|
|
|
|
ФУЛ^^ к; к:=к+1; |
|
|
else |
|
end |
|
|
{если номер строки нечетный } |
|||
|
|
forj:=l |
to 4 do |
{обходим слева направо} |
|
|
begin |
|
|
|
|
|
afiJJ:=k; k:-k+I; |
|
|
|
end; |
|
|
WriteLn('Сформированный массив:'); |
||||
for |
i:=l |
to 3 do |
|
|
|
begin |
|
|
|
|
|
forj:=l |
to 4 do |
Write(a[iJJ:3); |
|
|
WriteLn; |
|
|
End |
end; |
|
|
|
|
|
|
|
|
108
4. Структурные типы данных
|
1,1 |
1 |
2 |
1,3 |
1,4 |
!,5 |
1,1 |
|
1,2^^1 |
|
1,5 |
|
2,1 |
2 2 |
2,3 |
2,4 |
2,5 |
2 ^ |
%2-^ |2^^' m -^,5 |
||||
|
|
|
|
X |
Щ |
||||||
1 |
\?v* |
J |
z |
;J>»^ |
:7,*l |
^P |
Й1 |
..•зЖ' :Ш' |
|||
1 |
"Х 1 |
1 |
ii |
1 Ч |
'^ 4 |
'^ s |
|
|
|
:,pS'^,:t |
4J |
|
4,1 |
4 2 |
^fi? |
A* 4,;5 |
4 > |
|
':0' |
||||
|
5,1 |
52 |
ШШШУ |
5.1 |
5.^ Ш4, |
5,5 |
|||||
|
|
|
|
|
•..^-. .;i» |
|
|
^ |
|
0 |
|
Рис. 4.22. Варианты выборки элементов матрицы:
а - фрагменты прямоугольной формы; б - фрагмент ромбовидной формы
Выборочная обработка элементов матриц. Выборочная обработка элементов матриц, как и в случае одномерных массивов, требует определе ния законов изменения индексов как строк, так и столбцов. Однако вариан тов выборки, так же как и вариантов обхода, можно предложить множество (рис. 4.22).
В каждом случае также приходится искать закономерности, которые мо гут быть использованы в программе.
Пример 4.12. Разработать программу определения суммы элементов, расположенных в закрашенных областях (рис. 4.23), полученных при пост роении диагоналей, проходящих через элемент [р,к].
Из рисунка видно, что диагональные элементы матрицы исключаются из
рассмотрения. Суммирование будем выполнять |
\Ж ъг |
|
|
~щ |
||
в два последовательно выполняемых сложных |
1.3 |
|
||||
цикла. Это связано с тем, что выше элемента [р, |
|
|||||
к] суммировать необходимо элементы от 1 до |
Ш^4'Ш:7^У\ |
]Ш Шц |
||||
диагонали, параллельной главной, и от диагона |
||||||
ли, параллельной побочной, до п, а ниже - диа |
Ш;} |
? |
3,3 |
|
1 wviii-"mi"ii |
|
O^i^ |
|
|||||
гонали меняются местами. В каждом цикле от |
щ\ |
|||||
дельно записываем циклы суммирования левой |
х^ |
4,3 |
4,4 |
|||
и правой частей. Текст программы с коммента |
4.2 |
|||||
|
|
|
|
|
||
риями приведен ниже. |
5.1 |
5,2 |
5,3 |
5,4 |
5,5 |
|
Program ex; |
Рис. 4.23. Пример |
|||||
Var a:array[LJ5,L,15] of integer; |
||||||
разбиения матрицы на |
||||||
s,nXpXj:integer; |
||||||
области диагоналями, |
||||||
Begin |
проходящими через |
|||||
WriteLn('Beedume размер матрицы n< ==15 *); |
элемент [2,3] |
|
||||
109
Часть 1, Основы алгоритмизации и процедурное программирование
ReadLn(n); |
|
|
|
|
|
WriteLnCВведите \п/строк(и) |
по \п/ элемента(ов):*); |
||||
for i:=J to п doforj:=^l to n do |
ReadfafiJJ); |
|
|||
ReadLn; |
|
|
|
|
|
WriteLnCВведите индексы элементаp,k:'); |
ReadLn(p,k); |
||||
WriteLn(*McxodHbiu массив'); |
|
|
|||
for i:=l |
ton |
do |
|
|
|
begin |
|
|
|
|
|
forj:=ltondo |
Write(a[iJ]:4); |
WriteLn; |
|||
end; |
|
|
|
|
|
s:-0; {начальное значение суммы верхней части} |
|||||
for i:-l |
toр |
do {цикл определения суммы верхней части} |
|||
begin |
|
|
|
|
|
forj:—l |
to i'p-^k-l do {цикл обхода элементов левой части} |
||||
for j:-p^k'i-^l |
s:=s+afiJJ; |
|
|||
to n do {цикл обхода элементов правой части} |
|||||
|
|
|
s:^s+a[ij]; |
|
|
end;
for i:=p+l to n do {цикл определения суммы нижней части} begin
forj:-l to p+k-i'l do {цикл обхода элементов левой части} s:-s+a[ij];
for j.'-i'p+k'l to п do {цикл обхода элементов правой части} s:=s+afiJJ;
end;
WriteLn(VyMMa элементов равна \s); End
Связанная сортировка матриц. Сортировка матриц имеет свои осо бенности. На практике в виде матрицы представляют таблицы, поэтому, ес ли какую-либо строку или столбец таблицы надо сортировать, соответствую щие элементы остальных строк или столбцов перемещаются вместе с ними.
Пример 4.13. Разработать программу, определяющую суммарную «тень» отрезков, параллельных оси х, на оси х. (Тенью будем называть сум му проекций отрезков на ось х (рис. 4.24), не включающую наложений про-
|
|
|
п=6 |
|
2 |
5 |
|
|
D |
~ |
6 |
|
||
4 |
|
|||
|
|
|||
|
^ |
|
§2 |
X |
|
|
|
S = Sj+Sj
Рис. 4.24. Определение суммарной «тени»
ПО