Методика профессионального обучения

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

2. Массив

Массивы, как и циклы, – величайшее изобретение программирующего человечества. Массивы приходят на помощь, когда приходится иметь дело с наборами однотипных и однородных данных. Такой набор, имеющий общее для всех своих элементов имя, и называется массивом. Тип «массив» является представителем группы структурных типов Паскаля.

Одномерный массив – поименованная область памяти, доступ к которой осуществляется по общему имени и индексу соответствующей части.

3. Структура одномерного массива

Массив характеризует прежде всего  общим типом его элементов и их количеством, от которых зависит объем памяти, необходимый для размещения массива. Количество элементов массива, в свою очередь, определяется количеством индексов и диапазоном их изменения. В программировании количество индексов массива называют его размерностью (рангом), количество допустимых значений каждого индекса – его диапазоном (иногда используется термин «экстент»), а совокупность размерности и диапазонов – формой массива. Геометрическим образом массива можно считать многомерный параллелепипед. Каждое измерение этого параллелепипеда соответствует некоторому индексу, а его протяженность в каком-либо измерении – диапазону соответствующего индекса. При обращении к элементу массива индекс указывается в квадратных скобках после имени массива.

Пример: А[8]:=23, где А – это массив, [8] – элемент массива с индексом 8, а 23 – содержимое этого элемента.

Массив – поименованная область  памяти доступ к отдельным частям, которой, осуществляется по общему имени  и индексу соответствующей части.

Синтаксис: Var

<Имя массива> : array[<Нижний индекс>..<Верхний индекс>] of <Тип>

<Имя  массива> - идентификатор, соответствующий правилам обозначения идентификатора.

<Нижний  индекс> и <Верхний индекс> - константы задающие диапазон значения массива.

Например: <Нижний индекс> = 3, <Верхний индекс> = 7, то массив будет состоять из 5 элементов.

В качестве <Типа> элемента массива может использоваться любой для решения тип данных.

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

4. Работа с массивом и его элементами

Элементы массива  можно заполнять (с клавиатуры, задавать программно, либо случайным образом), выводить на экран массива, также работать с отдельными его элементами, сортировать массив.

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

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

Дан массив размерностью [1..10], присвоить каждому элементу 6.

Код программы	Комментарии
Program zapolnenie1;	{имя программы}
Var a:array[1..10] of integer;	{массив 1..10 целого типа }
i:integer;	{индекс массива}
Begin	{начало тела программы}
for i:=1 to 10 do	{в цикле от 1 до 10}
a[i]:=6;	{каждому элементу  массива присваивается число  6}
End.	{конец тела программы}

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

Дан массив размерностью [1..10], заполнить его с клавиатуры целыми числами.

Код программы	Комментарии
Program zapolnenie2;	{имя программы}
Var a:array[1..10] of integer;	{массив 1..10 целого типа }
i:integer;	{индекс массива}
Begin	{начало тела программы}
for i:=1 to 10 do	{в цикле от 1 до 10}
Readln(a[i]);	{на новой  строке вводим элемент массива}
End.	{конец тела программы}

Пример заполнения элементов массива случайным  образом.

Дан массив размерностью [1..10], заполнить его случайно сгенерированными числами в диапазоне от -50 до +50.

Код программы	Комментарии
Program zapolnenie3;	{имя программы}
Var a:array[1..10] of integer;	{массив 1..10 целого типа }
i:integer;	{индекс массива}
Begin	{начало тела программы}
Randomize;	{подключения модуля случайных чисел}
for i:=1 to 10 do	{в цикле от 1 до 10}
a[i]:=random(101)-50;	{элементу массива  присваиваем случайно выбранное число функцией random в диапозоне от -50 до +50}
End.	{конец тела программы}

Функция Random.

Random[(range:Word)]. В квадратных скобках указывается необязательный параметр конструкции Turbo Pascal. Тип результата: Real или Word, в зависимости от наличия параметра. Если параметр не задан, то результатом является число типа Real в диапазоне 0<=x<1. При наличии параметра возвращается число типа Word в диапазоне 0<=x<range. Обратите внимание на то, что верхняя граница диапазона не достигается – строгое неравенство.

Пример вывода массива на экран.

Дан массив размерностью [1..10], заполнить его числом 6 и вывести на экран.

Код программы	Комментарии
Program vivod;	{имя программы}
Var a:array[1..10] of integer;	{массив 1..10 целого типа }
i:integer;	{индекс массива}
Begin	{начало тела программы}
for i:=1 to 10 do	{в цикле от 1 до 10}
a[i]:=6;	{каждому элементу  массива присваивается число  6}
for i:=1 to 10 do	{в цикле от 1 до 10}
Write(a[i]:4);	{вывод элемента  массива на экран, для которого  отводится 4 позиции}
Writeln;	{задержка вывода}
End.	{конец тела  программы}

Пример работы с элементами массива.

Дан массив размерностью [1..10], заполнить его заполнить его случайно сгенерированными числами в диапазоне от -50 до +50 и вывести на экран минимальный элемент массива.

Код программы	Комментарии
Program rabota;	{имя программы}
Uses crt;	{подключение модуля}
Var a:array[1..10] of integer;	{массив 1..10 целого типа}
i,c:integer;	{индекс массива, переменная минимума}
Begin	{начало тела программы}
Clrscr;	{очистка экрана}
Randomize;	{подключения модуля случайных чисел}
for i:=1 to 10 do	{в цикле от 1 до 10}
a[i]:=Random(101)-50;	{каждому элементу  массива присваивается случайное  число в диапазоне от -50 до 50}
c:=a[1];	{переменной  минимум присваивается значение первого элемента массива}
for i:=2 to 10 do	{в цикле от 2 до 10}
if c>a[i] then	{Если переменная  минимума больше элемента массива,  тогда}
c:=a[i];	{переменной  минимум присваивается элемент  массива}
Writeln(‘min=’,c:4);	{вывод минимального  элемента массива на экран, для которого отводится 4 позиции}
Readkey;	{задержка вывода}
End.	{конец тела  программы}

 

Тема: Одномерный массив. Сортировка массива..

План:

1. Сортировка массива методом выбора;
2. Сортировка массива методом вставки;
3. Сортировка массива методом «пузырька».

Продолжительность занятия: два академических часа.

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

1. Сортировка массива методом выбора

Хотя этот алгоритм и не является самым быстрым, но на мой взгляд он наиболее прост для  понимания. Суть алгоритма состоит в том, что бы в исходном массиве найти наименьший элемент, а затем поменять местами первый элемент в списке с найденным. После того, находиться наименьший их оставшихся и меняется со вторым элементом. И так до тех пор пока весь список не будет отсортирован.

Таким образом понадобиться N+(N-1)+(N-2)+...+1 или N*N проходов чтобы отсортировать  список.

procedure SellectionSort( var a: array of integer; min,

max: Integer);

var

i, j, best_value, best_j: longint;

begin

for i:=min to max do

begin

best_value:=a[i];

best_j:=i;

for j:=i+1 to max do

begin

if a[j]<best_value then

begin

best_value:=a[j];

best_j:=j;

end;

end;

a[best_j]:=a[i];

a[i]:=best_value;

end;

end;

Переменными min и mах можно ограничить область списка в которой, будет выполнена сортировка. Что бы отсортировать весь массив необходимо записать следующее:

Код Delphi/Pascal - SellectionSort(a, 0, high(a));

2. Сортировка массива методом вставки

Это тоже предельно  простой для понимания алгоритм. Идея в том, что бы создать новый массив, а затем последовательно вставлять в новый массив элементы из старого массива, чтобы созданный массив был всё время упорядоченным.

procedure InsertionSort( var a: array of integer; N: integer);

var

B: array [0..10000] of integer;

i, j: integer;

begin

for i:=0 to N do

begin

j:=i;

while (j>1) and (B[j-1]>A[i]) do

begin

B[j]:=B[j-1];

j:=j-1;

end;

B[j]:=A[i];

end;

for i:=0 to N do

A[i]:=b[i];

end;

Если внимательно  посмотреть на реализацию алгоритма, то сразу же заметим что для его выполнения необходимо больше, чем N*N проходов, поэтому в приложениях, где скорость выполнения кода критична, подобный алгоритм использовать не актуально.

3. Сортировка массива методом «пузырька»

Чаще всего используется для сортировки частично упорядоченных  списков, так как именно для них скорость выполнения максимальна и может равняться O(N), где N количество элементов массива, а во время одного прохода через цикл. Этот алгоритм в исходном списке ищет пары цифр, которые следуют не по порядку и затем меняет их местами. Процесс повторяется до тех пор, пока весь список не будет отсортированным. На рисунке изображен пример сортировки данным методом.

На рисунке  можно проследить за перемещение  элемента, который изначально был  ниже чем после сортировки. Во время  прохода цикла, элемент изменяет свою позицию на одну позицию ближе к своему конечному месту. На рисунке элемент двигается к вершине, как пузырёк воздуха к поверхности воды. Этот эффект и дал название алгоритму пузырьковой сортировке.

Пузырьковая сортировка:

procedure BubbleSort( var a: array of integer; min, max: Integer);

var

i, j, tmp: integer;

begin

for i:=min to max do

for j:=min to max-i do

if A[j]>A[j+1] then

begin {Обмен элементов}

tmp:=A[j];

A[j]:=A[j+1];

A[j+1]:=tmp;

end;

end;

 

2. СТРУКТУРНО-ЛОГИЧЕСКИЙ АНАЛИЗ
1. СПЕЦИФИКАЦИЯ УЧЕБНЫХ ЭЛЕМЕНТОВ

№ п/п	Название  учебных элементов (понятий)	Опорное понятие	Новое понятие	Символьное обозначение	Уровень усвоения
1	2	3	4	5	6
1	Тип данных	+			III
2	Простой тип  данных	+			III
3	Целочисленный тип данных	+		INTEGER	III
4	Вещественный  тип данных	+		REAL	III
5	Символьный  тип данных	+		CHAR	III
6	Логический  тип данных	+		BOOLEAN	III
7	Структурированный тип данных	+			II
8	Массив		+	ARRAY	I
9	Строки		+	STRING	I
10	Множества		+	SET OF	I
11	Записи		+	RECORD	I
12	Файлы		+	FILE	I
13	Одномерный  массив		+		I
14	Объявление  массива		+		I
15	Имя массива		+		I
16	Нижний индекс		+		I
17	Верхний индекс		+		I
18	Тип массива		+		I
19	Ввод массива		+		I
20	Генератор чисел		+	Random	I
21	Вывод массива		+		I