Основы программирования (947332), страница 18
Текст из файла (страница 18)
Существуют методы быстрой сортировки, которые обеспечивают в среднем и даже в худшем вычислительную сложность 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{цикл по строкам}beginmax:-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 к dobeginforj:^l to m do Write(a[iJ]:4);WriteLn;end;endelseWriteLn(*Bce строки матрицы удалены');EndВ некоторых случаях применение приемов обработки одномерных массивов к матрицам результатов не дает.
В основном это задачи, связанные сразличными вариантами обхода матриц, и задачи обработки разных группэлементов в матрице.Обход элементов матрицы. На рис. 4.19 показано несколько способовобхода элементов матрицы. Для каждого из представленных способов, кромепоследнего, который выполняется по правилу выхода из лабиринта, можнопредложить закон, связывающий индексы между собой.Самые простые обходы: по строкам и столбцам. Их реализацию полезнопомнить.
Обход по строкам реализуется вложением циклов:for i:=l ton doforj:-l to m do<обработка элемента a[iJ]>При обходе по столбцам меняются местами циклы по строкам и столбцам:forj:=l to т dofor /.=7 to n do<обработка элемента a[ij]>1064, Структурные типы данныхЬг гф4 4+1Гt11шШши Jf лРис. 4Л9. Примеры вариантов обхода матрицы:А ~ обход по строкам; б ~ обход по столбцам; в - обход «змейкой»;г - обход по спирали; д - обход «змейкой по диагоналям»; е ~ «лабиринт»В прочих случаях закономерности формирования индексов приходитсяисследовагь, чтобы предложить соответствующий вариант реализации.В качестве примера рассмотрим закономерность формирования индексов диагоналей квадратной матрицы (рис.
4.20).Определив закономерности, сравнительно легко можно построить циклпрохода по диагонали матрицы. Например, для диагонали, проходящей черезэлемент [р,к] параллельно главной, получаем:к2,13.14,15,1у ^ Побочная диагональ: i + j = п+1Ч пч XX1.41,22J3.2х^5,27^\3.43,5/4,35,3Закономерность формирования индексовдиагоналей, проходящих чер^ элемент [р, к],а) параллельно главной: ! - j ' ^ p - k ,б) параллельно побочной: i + j = р + к.Количество элементов диагонали:а) параллельной главной: s ~ п - |р • к|,б) параллельной побочной: s = п - |п + I - (р + к).|2.54.55,45,5\Главная диагональ: i = jРис.
4.20, Закономерности формирования индексов диагоналейквадратной матрицы107Часть L Основы алгоритмизации и процедурное программирование123451098761112131415if р'к>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.Рис. 4.21. ЗаконДля решения задачи необходимо осуществитьформированияобход матрицы змейкой, присваивая его элементамматрицытребуемое значение. Из рисунка видно, что во всехнечетных строках значения элементов возрастаютмонотонно на единицу слева направо, а во всех четных - справа налево. Такое изменение можно описать формулами:для четной строки - (i-l)*n + п - j + 1,для нечетной - n*(i -1) + j ,где i - номер рассматриваемой строки, а j ~ номер столбца в ней.Значит, в программе можно построчно обойти все элементы и присвоитьим значения в соответствии с указанными формулами.Однако можно и просто реализовать данный вид обхода, присваивая элементам значение, которое каждый раз увеличивается на единицу.
Программа,приведенная ниже, реализует второй вариант.Program exiVar а: array[1..3J.A] of integer;k ij:integer;Begink:-l;for i:=l to 3 doif (i mod 2)=0 then {если номер строки четный}forj:-4 downto 1 do {обходим справа налево}beginФУЛ^^ к; к:=к+1;endelse{если номер строки нечетный }forj:=l to 4 do{обходим слева направо}beginafiJJ:=k; k:-k+I;end;WriteLn('Сформированный массив:');for i:=l to 3 dobeginforj:=l to 4 do Write (a[iJJ:3) ;WriteLn;end;End1084. Структурные типы данных1,1121,31,4!,51,11,2^^12,1222,32,42,52^%2-^ |2^^'1 \?v*1 iiJ;J>»^:7,*l'^ 4'^ s^P4,142^fi?A*4,;55,1521 "Х 1z1 Ч•..^-.
.;i»Ш ШШУXm1,5-^,5:Ш' Щ4>':0'0 4J^5.1 5 . ^Ш 4, 5,5Й 1 ..•зЖ':,pS'^,:tРис. 4.22. Варианты выборки элементов матрицы:а - фрагменты прямоугольной формы; б - фрагмент ромбовидной формыВыборочная обработка элементов матриц. Выборочная обработкаэлементов матриц, как и в случае одномерных массивов, требует определения законов изменения индексов как строк, так и столбцов.
Однако вариантов выборки, так же как и вариантов обхода, можно предложить множество(рис. 4.22).В каждом случае также приходится искать закономерности, которые могут быть использованы в программе.Пример 4.12. Разработать программу определения суммы элементов,расположенных в закрашенных областях (рис.
4.23), полученных при построении диагоналей, проходящих через элемент [р,к].Из рисунка видно, что диагональные элементы матрицы исключаются израссмотрения. Суммирование будем выполнятьв два последовательно выполняемых сложныхъг 1.3цикла. Это связано с тем, что выше элемента [р,к] суммировать необходимо элементы от 1 додиагонали, параллельной главной, и от диагона Ш^4'Ш:7^У\ ]Шли, параллельной побочной, до п, а ниже - диа3,3 O^i^гонали меняются местами. В каждом цикле от Ш;}дельно записываем циклы суммирования левой4.2 4,3 4,4 щ\х^и правой частей. Текст программы с комментариями приведен ниже.5.1 5,2 5,3 5,4 5,5~щ\Ж?Шц1 wviii-"mi"iiProgram 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 dobeginforj:=ltondoWrite(a[iJ]:4);WriteLn;end;s:-0; {начальное значение суммы верхней части}for i:-l toр do {цикл определения суммы верхней части}beginforj:—l to i'p-^k-l do {цикл обхода элементов левой части}s:=s+afiJJ;for j:-p^k'i-^l to n do {цикл обхода элементов правой части}s:^s+a[ij];end;for i:=p+l to n do {цикл определения суммы нижней части}beginforj:-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), не включающую наложений проп=6D524~6§2^S = Sj+SjРис.
4.24. Определение суммарной «тени»ПОX4, Структурные типы данныхтеньтень хкхкx[i,l]x[i,2]S:= S+x[i,2]-xkxk:=x[i,2]x[U]теньx[i,2]S:=S+x[i,2]-x[i,l]xk:=x[i,2]хкx[i,l] x[i,2]S и X- неменяютсяРис. 4.25. Три случая добавления i-ro отрезка к «тени»:а - отрезок частично перекрыт «тенью»; б - отрезок не перекрыт «тенью»;в - отрезок полностью перекрыт «тенью» (в);S - уже накопленная «тень», хк - правая граница этой «тени»екций.) Количество отрезков п. Отрезки заданы координатами начала и конца проекций на ось х.Анализ условия задачи и возможных вариантов отрезков показывает, чторешение задачи «в лоб» достаточно сложно. В то же время, если бы отрезкибыли сортированы по левой границе, то вычисление тени можно было выполнять, добавляя отрезки по одному.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
