Основные данные о работе

 

     Содержание

 

     Введение…………………………………………………………………………….3

     1. Виды массивов…………………………………………………………………...6

        1.1. Одномерные массивы……………………………………………………….6

        1.2. Примеры задач………………………………………………………………7

        1.3. Двумерные массивы………………………………………………………...8

        1.4. Пример задачи……………………………………………………………..15

     2. Сортировка, параметры-массивы и параметры–строки …………………......17

        2.1. Метод простых обменов (Пузырьковая сортировка)……………………17

        2.2. Сортировка простым выбором……………………………………………18

        2.3. Сортировка простым включением (Метод вставки и сдвига)…………..19

        2.4. Параметры-массивы и параметры-строки………………………………20

     Заключение………………………………………………………………………...24

     Глоссарий…………………………………………………………………………26

     Список  использованных источников

     Приложения

     Введение

     Существуют  различные типы данных в языке Паскаль. Рассмотрим производные типы. Каждое значение любого из этих типов в общем случае представляет собой уже нетривиальную структуру, т.е. обычно это значение имеет более чем одну компоненту. При этом каждая компонента структуры может быть как отдельным данным, так и в свою очередь нетривиальной структурой, т.е, значением любого из производных типов. Таким образом, значения производных типов в общем случае имеют иерархическую структуру, на самом нижнем уровне которой фигурируют только отдельные данные. Этим компонентам нижнего уровня могут присваиваться значения и они могут присутствовать в выражениях, как и значения переменных скалярного типа. Данные, являющиеся значениями скалярных типов, занимают сравнительно мало места в памяти ЭВМ. Отдельная литера, например, обычно представляется одним байтом (8 двоичных разрядов). Для чисел различны типов в зависимости от реализации отводят несколько байтов. Данные же, составляющие значение производного типа, обычно занимают значительный объем памяти ЭВМ. В связи с этим при написании программ для ЭВМ, имеющих сравнительно небольшой объем памяти, встает проблема экономного ее использования. В паскале предусмотрена возможность указания транслятору на необходимость экономного представления значений производных типов. Для этого задание производного типа необходимо начать со служебного слова packed , что означает упакованный. Но введя требование на упакованность данных, необходимо четко представлять себе, что, с одной стороны, это требование не всегда может быть выполнено транслятором (если, например, более экономного представления, чем обычное неупакованное представление для данных этого типа, в ЭВМ просто не существует). А с другой стороны, если оно выполнимо, то приводит к увеличению времени исполнения программы. Поясним на примере, за счет чего это происходит. Как уже указывалось ранее, одна литера занимает один байт. Машинная ячейка памяти, с которой работают команды ЭВМ, в общем случае состоит из нескольких байтов. Поэтому, если в ячейку поместить одну литеру, го большая ее часть не будет использована. На самом деле в одну ячейку можно поместить несколько литер (упакованное представление). Но тогда каждый раз, когда необходимо выполнить действие над отдельной литерой, придется производить выделение этой литеры из ячейки (распаковку литеры из ячейки). Аналогично, при записи отдельной литеры в память машины придется определять то место в ячейке, куда ее необходимо поместить, и заносить литеру именно туда, не изменяя содержимое остальных разрядов (запаковка литеры в ячейку). Такие дополнительные действия могут занимать значительную часть общего времени работы программы. Поэтому принимать решение об использовании упакованного представления данных должен всегда программист, в зависимости от конкретных условий и целей, которые он преследует. Итак, значения производных типов могут быть представлены в памяти ЭВМ в упакованном и неупакованном виде. Упакованное представление требует, вообще говоря, меньшего объема памяти, но замедляет процесс выполнения программы. Мы рассмотрим наиболее употребительный производный тип, а именно регулярный тип. Значение регулярного типа обычно называют массивом. Итак, массив — это упорядоченный набор фиксированного количества некоторых значений (компонент массива). Все компоненты должны быть одного и того же типа, который называют типом компонент или базовым (для массива) типом.

     Тип данных Массив позволяет одному идентификатору задать несколько значений, которые отличаются порядковым номером. Номер элемента массива указывается после идентификатора в квадратных скобках {M[5] – пятый элемент массива М}. При описании массива указывается диапазон номеров элементов массива и тип, к которому относится каждый его элемент. Массивы могут быть одно-, двух- и многомерными. 

     Пример описания и заполнения элементов массива.

     Var {описание массивов}

     M: array [1..5] of integer; {одномерный массив М с номерами элементов от 1 до 5, состоящий из целых чисел}

     M1: array [2..3,11..15] of char; {двумерный массив М1 с номерами строк от 2 до 3, с номерами столбцов от 11 до 15, состоящий из символов}

     Begin {заполнение массива}

     М[2]:=100; {второму элементу численного массива М присвоено значение 100}

     М1[2,3]:=’d’; {элементу второй строки и третьего столбца символьного двухмерного массива М1 присвоено значение ’d’}

     End.

     Основная  часть

     1. Виды массивов

 

     1.1 Одномерные массивы

     Каждому используемому в программе конкретному  массиву должно быть дано свое имя. Это имя будем называть полной переменной, поскольку ее значение есть весь массив. Каждая компонента массива может быть явно обозначена путем указания имени массива, за которым следует селектор компоненты — взятый в квадратные скобки индекс, задающий правило вычисления номера нужной компоненты. Это отличие от привычной записи индекса в математике, когда он указывается справа в нижней позиции, объясняется необходимостью использования линейной записи программы, так что многоуровневая запись должна быть исключена. При ссылке на компоненты массива индекс записывается на одном уровне с именем и заключается в квадратные скобки. Таким образом, для ссылки на отдельные компоненты используется запись вида (имя массива) [<индекс>] которую будем называть частичной переменной (поскольку ее значением является не весь массив, а отдельная его компонента, номер которой задается индексом) — применительно к массивам она называется переменной с индексом. В нашем примере массив получит имя v, а ссылки на отдельные его компоненты производятся с помощью частичных переменных v[ 1], v[2], ..., v[1ОО]. В общем случае в качестве индекса может, быть использовано выражение, значение которого и определяет номер компоненты массива. При этом важно, что в индексное выражение могут входить переменные, так что при изменении их значений меняется и значение индекса, которое определяет номер компоненты массива. Таким образом, одна и та же переменная с индексом в процессе выполнения программы может обозначать различные компоненты массива. Тип значения индексного выражения называют типом индекса. Множество значений типа индекса должно быть перенумерованным множеством, тем самым определяя количество компонент и их упорядоченность. При задании регулярного типа кроме типа индекса необходимо задать тип компонент. Задание такого регулярного типа, как одномерный массив, т.е. вектор, имеет вид:

     аrrау [(тип индекса)] оf <тип компонент> ,где <тип компонент> — имя или задание типа. 

     1.2 Пример задачи

     Дан линейный массив целых чисел. Подсчитать, сколько в нем различных чисел.

     {Подсчет  количества различных чисел в  линейном массиве}.

     ИДЕЯ  РЕШЕНИЯ: заводим вспомогательный массив, элементами которого являются логические величины (False - если элемент уже встречался ранее, True - иначе)}

     Program Razlichnye_Elementy;

     Var I, N, K, Kol : Integer;

     A : Array [1..50] Of Integer;

     Lo : Array [1..50] Of Boolean;

     Begin

     Write('Введите количество элементов массива: '); ReadLn(N);

     FOR I := 1 TO N DO

     Begin

     Write('A[', I, ']='); ReadLn (A[I]);

     Lo[I] := True; {Заполняем вспомогательный  массив значениями True}

     End;

     Kol := 0; {переменная, в которой будет  храниться количество различных  чисел}

     FOR I := 1 TO N DO

     IF Lo[I] THEN

     Begin

     Kol := Kol + 1;

     FOR K := I TO N DO

     {Во  вспомогательный массив заносим  значение False, если число уже встречалось  ранее или совпадает с текущим  элементом A[I]}

     Lo[K] := (A[K] <> A[I]) And Lo[K];

     End;

     WriteLn('Количество различных чисел: ', Kol)

     END.

     Тест: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3. Ответ: 6. 

     1.3 Двумерные массивы

     Двумерный массив (прямоугольная таблица (матрица, набор векторов)) - это пример массива, в котором элементы нумеруются двумя индексами.

     В качестве номера (индекса) элемента массива  используется выражение порядкового  типа (чаще integer).

     Двумерным массивом называется таблица, состоящая  из строк и столбцов. Для описания массива используются два индекса.

     А11 А12 А13 … А1m

     A21 A22 A23 ... А2m

     ... ... ... ... ...

     ... ... ... ... ...

     ... ... ... ... ...

     An1 An2 An3 ... Anm 

     Описание  массива

     Способ 1. В разделе описания переменных

     var

     ИмяМассива: array [Верх.Гр.1..Ниж.Гр.1,Верх.Гр.2..Ниж.Гр.2] of ТипЭлементов;

     Способ 2. В разделе описания типов

     ИмяМассива: array [Верх.Гр.1..Ниж.Гр.1,Верх.Гр.2..Ниж.Гр.2] of ТипЭлементов;

     Способ 3. В разделе описания констант

     const

     ИмяМассива: array[1..3,1..3] of real=((1.2,2.4,0.4),(0.045,-0.47,0.003),(1.24,1,-7.4));

     Заполнение  массива данными (ввод элементов)

     Массив, описанный как типизированная константа, уже содержит данные. Массивы, объявленные  в разделе описания переменных, необходимо заполнить данными, прежде чем выполнять  с ними какие-либо действия.

     Значения  элементов массива также можно  задать следующими способами: при вводе данных с клавиатуры:

     write('Введите  количество строк и столбцов');

     readln(n,m);

     for i:=1 to n do

     for j:=1 to m do

     begin

     write('a[',i,',',j,']='); {Можно эту строчку в программе  не использовать}

     readln(a[i,j]);

     end; 

     с помощью датчика случайных чисел:

     randomize;

     writeln('Введите  количество элементов массива');

     readln(n);

     for i:=1 to n do

     begin

     a[i]:=random(50);

     writeln('a[',i,',',j,']=',a[i,j]);

     end; 

     присваением заданных значений (например по формуле i*i/i+2):

     writeln('Введите  количество элементов массива');

     readln(n);

     for i:=1 to n do

     begin

     a[i]:=i*i/i+2;

     writeln('a[',i,',',j,']=',a[i,j]);

     end; 

     Вывод массива

     вывод в столбец:

     for i:=1 to n do

     writeln(a[i,j]); 

     по строкам и столбцам:

     for i:=1 to n do

     begin

     for j:=1 to m do

     begin

     write(a[i,j]:3);

     end;

     readln;

     end; 

     Обработка массивов

     Часто требуется вычислить сумму элементов  массива, их среднее арифметическое значение или найти значения и  номера максимального и минимального элементов, а также изменить значения элементов массива и т.д. Особенность работы с двумерными массивами заключается в том, что расширяется возможность обработки массива (появились новые элементы: строки, столбцы - являющиеся одномерными массивами). Подробно все действия можно рассмотреть в задачах разобранных в этом разделе. 

     Квадратная  матрица

     Квадратной  называется такая матрица, в которой  количество строк равно количеству столбцов. Выделяют следующие элементы квадратной матрицы:

     главная диагональ;

     побочная  диагональ;

     элементы, расположенные выше главной диагонали;

     элементы, расположенные ниже главной диагонали;

     элементы, расположенные выше побочной диагонали;

     элементы, расположенные ниже побочной диагонали;

     Главная диагональ. Если значения индексов (i, j) элемента равны, то элементы расположены  на главной диагонали.

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     if i=j then <инструкции> 

     Побочная  диагональ. Если для значений индексов (i, j) элементов выполняется равенство: i+j=n+1, то элементы расположены на побочной диагонали.

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     if i+j=n+1 then <инструкции> 

     Для элементов, расположенных выше главной  диагонали необходимо использовать один из следующих фрагментов программы:

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     for i:=1 to n do

     for j:=1 to n do

     if i < j then <инструкции>

     for i:=1 to n-1 do

     for j:=i+1 to n do

     <инструкции> 

     Если  элементы расположены на главной  диагонали и выше её необходимо использовать следующий фрагмент программы: 

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     for i:=1 to n do

     for j:=1 to n do

     if i<=j then <инструкции> 

     Для элементов, расположенных ниже главной  диагонали необходимо использовать следующий фрагмент программы: 

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     for i:=1 to n do

     for j:=1 to n do

     if i>j then <инструкции> 

     Для элементов, расположенных ниже главной  диагонали и не ней необходимо использовать следующий фрагмент программы:

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     for i:=1 to n do

     for j:=1 to n do

     if i>=j then <инструкции> 

     Если  элементы, расположены выше побочной диагонали, то необходимо использовать следующий фрагмент программы:

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     for i:=1 to n-1 do

     for j:=1 to n-1 do

     if i+j<=n then <инструкции> 

     Если  элементы, расположены ниже побочной диагонали, то необходимо использовать следующий фрагмент программы:

     А11 А12 А13 А14

     A21 A22 A23 А24

     A31 A32 A33 А34

     A41 A42 A43 А44

     for i:=2 to n do

     for j:=2 to n-1 do

     if i+j>n+1 then <инструкции> 

     Транспонирование  матрицы

     Транспонированной матрицей называется матрица, у которой  столбцы соответствуют строкам  исходной квадратной матрицы. При этом элементы главной диагонали исходной и транспонированной матриц, одни и те же.

     Операция транспонирования сводится к обмену элементов матрицы, расположенных симметрично главной диагонали.

     Исходная  матрица

     Транспонированная матрица

     1

     5

     9

     13

     1

     2

     3

     4 

     Фрагмент  программы транспонирования матрицы:

     for i:=1 to n do {Просмотр всех строк матрицы}

     for j:=i+1 to n do {Просмотр всех элементов в строке, расположенных выше главной диагонали}

     begin

     k:=a[i,j];

     a[i,j]:= a[j,i];

     a[j,i]:= k;

     end;

     1.4 Пример задачи 

     Найти сумму всех элементов некоторого двумерного массива и сравнить их с произведением элементов некоторой строки.

     program zadacha;

     uses crt;

     var

     a: array[1..50,1..50] of integer; {массив}

     i,j: integer; {переменные счетчики}

     n,m: integer; {количество строк и столбцов  массива}

     s: integer; {сумма элементов массива}

     p: integer; {произведение элементов некоторой строки}

     q: integer; {некоторая строка}

     begin

     clrscr;

     write('Введите  количество строк: ');

     readln(n);

     write('Введите  количество столбцов: ');

     readln(m);

     for i:=1 to n do

     for j:=1 to m do

     begin

     write('a[',i,',',j,']=');

     readln(a[i,j]);

     end;

     writeln('Матрица:');

     for i:=1 to n do

     begin

     for j:=1 to m do

     begin

     write(a[i,j]:3);

     end;

     readln;

     end;

     for i:=1 to n do

     for j:=1 to m do

     begin

     s:=s+a[i,j];

     end;

     write('Введите  номер строки для работы: ');

     readln(q);

     p:=1;

     for j:=1 to m do

     begin

     p:=p*a[q,j];

     end;

     writeln('Сумма элементов матрицы: ',s);

     writeln('Произведение  элементов строки ',q,' равна ',p);

     if s>p then

     begin

     writeln('Сумма больше произведения');

     end

     else

     begin

     writeln('Произведение  больше произведения');

     end;

     readln;

     end.

     2. Сортировка, параметры-массивы и параметры-строки

 

     Сортировка

     Задача  сортировки (упорядочения) элементов  массива в соответствии с их значениями относится к классу классических задач, которые решались еще на первых е- mail –ах.

     В настоящее время разработано  достаточно много различных методов сортировки. Одни из них относятся к методам простых сортировок. Другие к улучшенным. Однако до сегодняшнего момента задача разработки метода, сочетал бы в себе все лучшие качества остается открытой. Договоримся, что линейный массив, который необходимо упорядочить уже задан, т.е. описан и сгенерирован.

     Различают следующие типы сортировок:

     1) по возрастанию

     2) по убыванию

     3) по не убыванию

     4) по не возрастанию

     При рассмотрении каждого метода будем  сортировать элементы по неубыванию. 

     2.1 Метод простых обменов (Пузырьковая сортировка)

     Идея  метода: Весь массив рассматривается  несколько раз, причем при каждом рассмотрении сравниваются значения 2-х  соседних элементов. Если они стоят  в неправильном порядке, то производится их перестановка. Так происходит до тех пор, пока не будет выполнено ни одной перестановки. Метод называют пузырьковой сортировкой потому что меньшие значения элементов постепенно "всплывают", как пузырьки воздуха в воде, перемещаясь в начало массива, а "тяжелые" элементы "оседают на дно".