metod_15.03.04_atppp_oaip_up_2016 (Методические документы), страница 11

Самые легкие элементымассива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически этоможно реализовать следующим образом. Мы будем просматривать весь массив"снизу вверх" и менять стоящие рядом элементы в там случае, если "нижний"элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый"легкий” элемент всего массива.

Теперь повторим всю оперно для оставшихсянеотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого.Как видно, алгоритм достаточно прост, но, как иногда замечают, он являетсянепревзойденным в своей неэффективности. Немного более эффективным, нотаким наглядным является второй метод.2. Сортировка выборомНа этот раз при просмотре мaccива мы будем искать наименьший элемент,сравнивая его с первым. Если такой элемент найден, поменяем его местами спервым. Затем повторим эту операцию, но начнем не с первого элемента, а совторого.

И будем продолжать подобным образом, пока не рассортируем весьмассив.3. Метод ШеллаЭтот метод был предложен автором Donald Lewis Shеll в 1959 г. Основнаяидея этого алгоритма заключается в том, чтобы в начале ycтpанить массовыйбеспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Каквидно, интервал между сравниваемыми элементами (gap) постепенноуменьшается до единицы.

Это означает, что на поздних стадиях сортировкасводится просто к перестановкам соседних элементов (если, конечно, такиеперестановки являются необходимыми).4. Метод ХoopаЭтот метод, называемый также быстрой сортировкой (QuickSort), былразработан в 1962 г. (его разработал Charles Antony Richard Hoare). Суть методазаключается в том, чтобы найти такой элемент множества, подлежащегосортировке, который разобьет его на два подмножества: те элементы, что меньшеделящего элемента, и те, что не меньше его.

Эту идею можно реализоватьмногими способами.6.2. Многомерные массивыДо сих пор мы рассматривали массивы, каждый элемент которых содержалодин индекс. Такие массивы называют одномерными.Из многомерных массивов в математике наиболее часто используют двумерныемассивы – матрицы.Описание матрицы 3 х 4:1) Type T = Array [1..3,1..4] of Integer;Var A:T;2) Type T = Array [1..3] of Array [1..4] of Integer;Var A:T;Пример:Type T1 = Array [1..4] of Integer;T = Array [1..3] of T1;Var A:T;61B: T1;Здесь сначала описывается тип одной строки Т1, а затем, через тип строки Т1,описывается тип всей матрицы Т.

В разделе переменных указывается, что Аявляется двумерным массивом (т.е. матрицей), а В – одномерным массивом.Пример: Найти сумму положительных элементов массива D(n,m)n10, m20.Program Summa;Const n=10;m=20;Var i, j:Integer;Sum: Real;D: Array [1..n,1..m] of Real;BeginSum: = 0;For i: = 1 to n doFor j: = 1 to m doBeginRead (D[i,j]);If D[i,j] > 0 then Sum: = Sum + D[i,j];End;Writeln (‘Sum=’,Sum);End.Пример: Даны две матрицы: A[N*M], B[N*M].Найти их сумму C[N*M]= A + B.Cij = aij + bijProgram Summa;Const N=3; (*количество строк*)M=5; (*количество столбцов*)Type Mat = Array [1..N,1..M] of Real;Var A, B, C: Mat;I: Integer; (*индекс строки*)J: Integer; (*индекс столбца*)BeginWriteln (‘Ввести А, В’);For I: = 1 to N doBeginFor J: = 1 to M doBeginRead (A[I,J],B[I,J]);C[I,J]:= A[I,J] + B[I,J];End;Readln;End;Writeln (‘Матрица С’);For I: = 1 to N doBegin62For J: = 1 to M doWrite (C[I,J]:3:1, ‘ ‘:2);Writeln;End;End.6.3.

Упакованные массивыКак правило, одно целое число или один символ занимают в памяти ЭВМдва байта. В то же время для изображения символа достаточно одного байта. Сцелью экономии памяти машины в языке программирования Паскаль введенопонятие упакованного массива. Элементы упакованного массива хранятся по двав двух байтах ЭВМ. И хотя при этом экономится место в памяти, ноувеличивается время доступа к компонентам массива.Элементы упакованного массива используются в программе точно так же,как элементы не упакованного массива. Только память машины при этомавтоматически выделяется меньше.Например, массивы А и АР описаны какVar AP: Packed Array [1..3] of Boolean;A: Array [1..3] of Boolean;Обычнвй м упакованный массивы идентичны в смысле объема и характерахранимой информации, но различаются способами представления в памяти ЭВМ.Упакованный массив можно описывать в разделе переменных или сиспользованием раздела типов.Описание в разделе типов:Type имя типа = Packed Array [имя индекса] of тип элемента;Var имя переменной:имя типа;Здесь служебное слово Packed указывает на то, что массив данных являетсяупакованным.К упакованным символьным массивам в языке программирования Паскальотносится строки символов, которые задаются либо в разделе операторов, либо вразделе констант (строки символов, а не символьные строки String, о которыхречь пойдет дальше).

Как известно, тип константы однозначно определяется еезаписью. Поэтому если, например, в разделе констант определена константаS=’end’, то она принадлежит к типу: Packed Array [1..3] of Char.Считается, что символьные константы имеют тип упакованных массивов:Packed Array [1..n] of Char;где n - длина строки.Символьные массивы и константы могут участвовать в операцияхприсваивания и сравнения.Пусть, например, описание символов массива имеет вид:Type Mas= Packed Array [1..7] of Char;Var A:Mas;Тогда, можно записать такой оператор:A:=’ZADACHA’;Если к строкам и упакованным символьным векторам применяют операциисравнения, то при этом аргументы обязательно должны содержать одинаковое63количество символов, т.е.

их типы д/б идентичными. Операции сравнениявыполняются посимвольно, слева направо.Пример: ‘String’ < ’Strong’, т.к. в алфавите символ ‘i’ стоит раньше, чем ’o’ и егокод меньше, т.е. ’i’<’o’.Пусть, например, имеется строка: “ABCDEFG”. Эту строку можно считатьмассивом символов, состоящим из 8 символов, включая пробел. Если этот массивсимволов обозначить именем Sim, то описание примет вид:Type T = Packed Array [1..8] of Char;Var Sim:T;Один элемент массива принимает значение одного символа, например:Sim[1]=’A’;Sim[6]=’ ’.Элементы массива могут принимать свои значения с помощью оператораввода Read, который располагается внутри цикла.Пример: ввода.1) I: = 1;While I<=10 do BeginRead (A[I]); I:= I+1; End;2) For I:= 1 to 46 do Read (A[I]);Вывод массива символьных данных также организуется с использованиемцикла.Пример: Дана строка символов, обозначенная именем S1.‘To be or not to be’Требуется сформировать новый массив с именем S2, который содержитпредставленную строку символов с добавлением в конце вопросительного знака.Program Hamlet;Type Stroka = Packed Array [1..20] of Char;Var S1, S2: Stroka;I: Integer; (*счетчик символов*)K: Integer; (*параметр цикла*)BeginWrite (‘Ввести S1=’);I; = 0;While I <= 18 doBeginI:= I+1;Raed (S1[I]); Readln;End;S2:= S1;S2[I+1]:= ‘?’;For K:= 1 to I+1 do Write (S2[K]);End.Разрешается ввод и вывод символьных массивов целой строкой, без организациицикла.Пример: Даны два символьных массива: А1= ‘Suvorov’ и А2= ‘Suhanov’.Требуется поменять их местами.Program Zamena;64Const N =12;Type Mas = Array [1..N] of Char;Var A1,A2,X: Mas;BeginWriteln (‘A1-Who?’);Readln (A1); {Суворов}Writeln (‘A2-Who?’);Readln (A1); {Суханов}Writeln (‘происходит замена’);X:=A1;A1:=A2;A2:=X;Writeln (‘A1=’,A1);Writeln (‘A2=’,A2);End.Обратите внимание, что для ввода и вывода символьных массивов здесь неприменяется цикл!6.4.

СтрокиТип String (строка) в Паскале широко используется для обработки текстов иво многом похож на одномерный массив символов Array [0..N] of Char. Однако вотличие от массива количество символов в строке – переменной может менятьсяот 0 до N, где N – максимальное количество символов в строке. Значение Nопределяется в разделе объявления типа String [N] и может быть любойконстантой порядкового типа, но не больше 255: N 255.

Можно не указывать N,в этом случае длина строки принимается максимально возможной: N = 255.Строка трактуется как цепочка символов. К любому символу в строкеможно обратится точно так же, как к элементу одномерного массива Array [0..N]of Char.Пример:Var st: String;-------------if st[5]= ‘A’ then …….Самый первый байт в строке имеет индекс 0 и содержит текущую длинустроки.

Первый значащий символ строки занимает второй и имеет индекс 1. Наддлиной строки можно совершать необходимые действия и таким способом менятьдлину строки.Пример:Var st:String[10];I:Integer;-------------st[0]:=5;Значение Ord (st[0]), то есть текущую длину строки можно получить спомощью функции length (st).К строке можно применить операцию + (сцепление строк), например:St:=’a’+’b’;{ ab}65St:=st+’c’; { abc}Если длина сцепленной строки превысит максимально допустимую длинуN, то «лишние» символы отбрасываются.Пример:Var st :String [1];Begin st:=’123’;Writeln(st); { 1}End;Кроме сцепления строк, все остальные действия над строками (исимволами) реализуются с помощью встроенных функций.1)Concat (S1<, S2, S3,…SN>)– функция типа String, сцепление строк;2)Copy (имя строки,№ нач. символа, кол-во символов)– функциякопирования;3) Delete (имя строки,№ нач. символа, кол-во символов)– функция удаления;4) Insert (имя подстроки, имя строки, № нач.

символа в строке)– вставка;5) Length (имя строки)– функция типа Integer, вычисляет длину строки;6) Pos (имя подстроки, имя строки)- функция типа Integer, отыскивает в строкепервое вхождение подстроки и дает № позиции, с которой она начинается;если подстрока не найдена, значение функции будет = 0;7) Str (число Real или Integer <: общая ширина поля<: кол-во симв. в дроб.части>>, имя строки) – процедура, преобразующая число типа Real или Integerв строку символов так, как это делает процедура Writeln перед вызовом;параметры, если они присутствуют, задают формат преобразования;8) Val (имя строки, число Real или Integer, параметр) – процедура,преобразующая строку символов во внутреннее представление целое иливещественное числа; параметр = 0, если преобразование проведено успешно, впротивном случае он содержит № позиции в строке, где обнаруженошибочный символ;9) Upcase (символ) – функция типа Char, возвращает символ в верхнем регистре,если он определен для него, либо сам символ, если для него нет верхнегорегистра.Пример: Upcase(‘a’) даст A,Upcase(‘2’) даст 2.Пример:Varx: Real;y: Integer;st, st1: String;- ---------------st:= concat (‘12’,’345’); (*получится st  12345*)st1:= copy (st, 3, lenght(st)-2); (*получится st1  345*)insert(‘-’,st1,2); (*получится st1  3-45*)delete(st, pos(‘2’,st),3); (*получится st  15*)str(pi:6:2,st); (*получится st  3.14*)st1:=’3.1415’; (*получится st1  3.1415*)66val(st1,x,y); (*получится y=2, x – какой был*)Операции отношения= <> > < >= <=выполняются над двумя строками посимвольно, слева направо, с учетомвнутренней кодировки символов.