Практическая работа в языке программирования Pascal. Одномерный массив (вектор). Двумерный массив (матричный). Сортировка массивов.

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ДОПОЛНИТЕЛЬНОГО ОБРАЗОВАНИЯ ДЕТЕЙ

«СТАНЦИЯ ЮНЫХ ТЕХНИКОВ ГОРОДА ЕВПАТОРИИ РЕСПУБЛИКИ КРЫМ»

(МБОУДОД "СЮТ")

297402, Российская Федерация, Республика Крым, город Евпатория, ул. Революции, д. 75, тел. (06569) 3-03-30,

е-mail: [email protected]

План-конспект учебного занятия

кружок «Компьютер и информационные технологии», группа 2 – А

Тема учебного занятия: «Практическая работа в языке программирования Pascal. Одномерный массив (вектор). Двумерные массив (матричный).

Сортировка массивов».

Цель учебного занятия: формирование у детей знаний и умений работы с языком программирования Pascal, организация работы по усвоению детьми основных понятий, принципов работы с данным языком.

Задачи учебного занятия:

Образовательная:

• проконтролировать степень усвоения основных понятий, принципов работы с языком программирования Pascal, изученных и сформированных на предыдущих занятиях;

• обеспечить усвоение основных задач, входящих в содержание темы учебного занятия;

• научить создавать программы с использованием одномерного и двумерного массивов, а также научатся сортировать массивы, применяя различные методы;

• формировать умение правильно и грамотно выражать свои мысли.

Развивающая:

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

Воспитательная:

• воспитывать аккуратность, внимательность, вежливость, дисциплинированность и бережное отношение к вычислительной технике.

Тип учебного занятия: формирование новых знаний, навыков и умений.

Методы работы: объяснительно-иллюстративный, практическая работа.

Формы работы: индивидуальная, групповая.

Оборудование: персональные компьютеры, доска, мел.

Дидактические материалы: карточки с заданиями.

Ход учебного занятия.

• Организационный момент;

• ТБ при работе за компьютером;

• Актуализация опорных знаний:

• Мотивация учебной деятельности обучающихся:

• Выполнение практической работы;

• Физкультминутка;

• Итоги учебного занятия:

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

1. Организационный момент.

Приветствие, проверка присутствующих. Объяснение хода учебного занятия.

2. ТБ при работе за компьютером.

3. Актуализация опорных знаний:

Основные принципы работы с языком Pascal.

Pascal – один из самых известных языков программирования. Создан в 1968 – 1969 годах швейцарским ученым Никлаусом Виртом, был назван в честь французского математика и физика Блеза Паскаля, и используется для обучения программированию по сей день.

Перед началом работы следует напомнить, что язык Pascal – это совокупность трёх составляющих: алфавита, синтаксиса (правил написания объектов языка) и семантики (правил использования этих объектов).
Алфавит Pascal состоит из:

1. Прописных и строчных букв латиницы: A...Z, a…z;

2. Цифр: 0...9;

3. Специальных символов: + — * / = .,:; ‘ # ( ) { } [ ] и их комбинаций: «=» «

Задача же синтаксиса и семантики состоит в том чтобы, правильно написать раздел программы и правильно составить ее структуру, в противном же случае ваша программа будет работать неправильно (или же не работать вовсе!).

Структура программы выглядит так:

Program «имя программы»; — заголовок программы;
(Примечание: в конце строки ставится точка с запятой, не во всех, но в большинстве) 
Uses (название библиотеки); здесь подключаются библиотеки, которые дают дополнительные возможности при создании программ;
Label (имя метки); здесь, если необходимо, прописываются метки, позволяющие переходить в разные места программы (о них позже);
Const тут указываем переменные с постоянной величиной, например, p=3.14;
Var тут через запятую перечисляем все переменные, а затем, указываем тип данных (Пример: Var: K, L, M: integer; N, O: real; (если несколько типов));
Begin (здесь без точки с запятой)
Дальше следует основной блок программы;
end. – конец программы (обязательно после “end” точка, если только это конец программы, а не операторные скобки).

Следует заметить, что из вышеперечисленных разделов обязательными есть только «Var», «Begin» и «end», остальные же могут применяться, если это требуется в ходе выполнения поставленной задачи. 

Массивы.

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

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

Представим работу такой программы, как нахождение среднего арифметического среди 100 чисел. Что нам понадобится для написания такой программы? Конечно, сами числа. Для хранения 100 чисел мы должны использовать 100 переменных. Описать их можно, скажем, следующим образом: var n1,n2,n3,n4,n5, n6,n7, ..., n100: Integer; Это будет выглядеть крайне громоздко.

Вот здесь и возникает понятие массивов.

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

Массив - это переменная и как все переменные описывается в разделе var программы.

Описание переменной - массива состоит из:

• Имени переменной;

• Служебного слова Array, означающего "массив";

• Описания размера массива. Диапазон записывается в квадратных скобках - [ ]. Внутри пишется сам диапазон, в виде двух чисел, разделенных двоeточием: начало..конец;

• Задание типа начинается со служебного слова of.

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

Массив относится к так называемым структурированным данным, то есть таких, которые имеют фиксированную внутреннюю структуру (организацию).
    Массив характеризуется:
      1. Количеством размерностей (количеством координат, необходимых для определения местонахождения нужного элемента массива).
      2. Общим идентификатором (именем) для всех элементов массива.
      3. Индексом или совокупностью индексов, которые определяют каждый отдельный элемент массива.
  

Одномерный массив (вектор) - имеет одну размерность.

При обращении к отдельному элементу массива необходимо указать его индекс (местонахождение в массиве):
    

  A[7]    i:=7; A[i]

      Здесь i - индекс элемента массива, может быть только целого или натурального типа.

 Двумерные массивы (матричные) - имеют две размерности, m*n.

Доступ к отдельному элементу массива осуществляется путем определения двух его координат: номера строки i=1..m и столбца j=1..n
    Операции предоставления выполняются аналогично:
      

a[3,9]=8; B:=A[1,1]

В трехмерном массиве для доступа к элементу необходимо указать три индекса A[i,j,k].

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

Сортировка массивов

Методы сортировки можно разбить в соответствии с определяющими их принципами на три основные группы:
    1. Сортировка с помощью вставки (by Іnsertіon) или с помощью включения
    2. Сортировка с помощью выбора (by Selectіon) или с помощью выделения
    3. Сортировка с помощью обмена (by Exchange) или пузырьковая.

Каждая группа имеет прямой метод (самый простой) и улучшенный (усложненный) методы сортировки.

  I. Сортировка с помощью вставки.

Принцип сортировки: массив распределяется на отсортированную и неотсортированную части. На первом шаге за отсортированную часть (последовательность) принимается первый элемент массива. Каждый следующий элемент из неотсортированной части вставляем в заранее отсортированную последовательность так, чтобы эта последовательность оставалась отсортированной.
При этом надо:
    1. Найти место, куда нужно вставить этот элемент
    2. Сдвинуть элементы, которые стоят справа в отсортированной части на одну позицию вправо.
    3. На освобожденное место поставить элемент, который анализируется (вставляется).
  Два способа выполнения этих действий:
    1) каждый следующий элемент сравнивается с элементами в отсортированной части, находится место вставки, все следующие элементы сдвигаются на одну позицию вправо и после этого вставляется элемент;
    2) элемент, который вставляется, последовательно, слева направо, сравнивается с любым из элементов в отсортированной части. Если нужно, элемент в отсортированной части сразу сдвигается на одну позицию вправо. Как только найдено нужное место вставки, элемент, который анализируется, вставляется на нужную позицию.
 

II. Сортировка с помощью прямого выбора.

Принцип сортировки: массив также делится на отсортированную и неотсортированную части. На первом шаге весь массив - неотсортированный. В неотсортированной части находится минимальный (или максимальный) элемент и меняется местами с первым элементом неотсортированной части. Граница отсортированной части сдвигается вправо на 1. Процедура выполняется циклически, n-1 раз (последний элемент передвигать не надо).

III. Сортировка с помощью прямого обмена (пузырьковая).

Принцип сортировки: слева направо поочередно направляется сравнение двух соседних элементов. Если они не упорядочены между собою, то меняются местами. В базовом алгоритме прохождения массива и очередное приведение в порядок повторяются n-1 раз.

Пример программы:

1. Нахождение среднего арифметического ста чисел.

Program N1;

var M: Array [1..100] of Integer; A: Real; I: Byte;

begin Randomize;

For I := 1 to 100 do M[I] := Random(500);

For I := 1 to 100 do

A := A + M[I];

A := A / 100;

Write('Среднее арифметическое всех чисел массива: ', A);

end.

1. Найдите максимальное число среди введенных чисел и выведите его на экран.

Program N2;

var M: Array [1..10] of Integer; Max: Integer; I: Byte;

begin Writeln('Введите 10 чисел: ');

For I := 1 to 10 do

begin Write('N',i,': ');

Readln(M[i]);

end;

Max := M[1];

For I := 1 to 10 do

if Max

Write('Максимальное число: ', Max);

Readln;

end

4. Мотивация учебной деятельности обучающихся:

Создавая Паскаль, Вирт преследовал 2 цели:

• во-первых, разработать язык, пригодный для обучения программированию как систематической дисциплине;

• во-вторых, реализация языка должна быть эффективной и надежной на существующих вычислительных машинах.

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

Это был самый первый простой язык (ord pascal) для программирования, помогающий решить множество практических задач прошлого столетия (1970 год). Он был разработан группой ученых. С расширением платформ были созданы новые версии этой программы, а Pascal стал классическим языком программирования.

5. Выполнение практической работы.

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

То есть, если у нас 10 чисел, то сначала первое из них будет сравниваться до тех пор, пока не будет найдено другой, например, большее его (если мы сортируем просто по возрастанию). Далее так же будет сравниваться 2, 3, 4 … элементы с последующими, но не с теми, которые уже отсортированы.

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

Program SortMas;

var

i, j, k: integer;

mas: array[1..20] of integer;

Begin

randomize;

for i := 1 to 20 do mas[i] := random(100);

writeln;

writeln('массив до сортировки');

for i := 1 to 20 do write(mas[ i], ' ');

for i := 1 to 19 do

for j := i + 1 to 20 do

if mas[i] < mas[j] then

begin

k := mas[i];

mas[i] := mas[j];

mas[j] := k;

end;

writeln('массив после сортировки');

for i := 1 to 20 do write(mas[ i], ' ');

End.

Обратите внимание на 2 первые строки после Begin. Здесь мы вызываем процедуру генерации случайных чисел. То есть просто заполняем наш массив числами от 1 до 100. Далее в цикле выводится для пользователя первоначальный массив.

Далее следует сам алгоритм сортировки, для новичков объясним, что это 2 цикла for, первый из них, в данной случае, идет с самого начала и до N-1 (1 первого до предпоследнего элемента).

Далее вложенный for, где используется уже другой счетчик j. Он изменяется от текущего i-того, увеличенного на 1 и до конца. И далее мы проверяем 2 элемента массива в условии и, если все нас устраивает, то производим обмен переменными. В последнем цикле мы выводим отсортированный массив.

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

Program SortPopolam;

var

i, j, k: integer;

mas: array[1..10] of integer;

begin

randomize;

for i := 1 to 10 do mas[i] := random(101);

writeln('массив до сортировки');

for i := 1 to 10 do write(mas[ i], ' ');

for i := 1 to 4 do

for j := i + 1 to 5 do

if mas[ i] > mas[ j] then

begin

k := mas[ i];

mas[i] := mas[j];

mas[j] := k;

end;

for i := 5 to 9 do

for j := i + 1 to 10 do

if mas[ i] < mas[ j] then

begin

k := mas[ i];

mas[ i] := mas[j];

mas[j] := k;

end;

writeln;

writeln('массив после сортировки');

for i := 1 to 10 do write(mas[ i], ' ');

end.

Вы, конечно, заметили, что здесь 2 алгоритма сортировки, первый идет с первого элемента по 5, а второй — с 5 по 10. Они отличаются только условиями, в этом и заключается этот нехитрый способ.

Как видите, здесь нет ничего особенного. И еще один пример по сортировке выбором. Пусть нужно отсортировать массив таким образом, чтобы числа в нем располагались в порядке возрастания своих последних разрядов. Допустим, если у нас массив 17 23 18 70, то после сортировки он должен выглядеть так: 70 23 17 18. Вот код этой программы.

Program SortOstatok;

var

a: array[1..10] of Integer;

i, j, k: Integer;

begin

randomize;

for i := 1 to 10 do a[ i] := random(100);

writeln('массив до сортировки');

for i := 1 to 10 do write(a[ i], ' ');

for i := 1 to 9 do

for j := i + 1 to 10 do

if a[i] mod 10 > a[j] mod 10 then begin

k := a[i];

a[i] := a[j];

a[j] := k;

end;

writeln('массив после сортировки');

for i := 1 to 10 do write(a[i], ' ');

end.

Эта программа схожа с первой, их отличие лишь в том, что разное условие для перестановки элементов массива. В первой это «if mas[i]  «, а во втрой «if a[i] mod 10 a[j] mod 10 then» То есть мы располагаем наши элементы в таком необычном порядке благодаря тому, что просто проверяем остатки их деления на 10, то есть и сравниваем их последние цифры.

Теперь подробнее о сортировке пузырьком. Его сущность заключается в том, что мы сравниваем соседние элементы парами : 1 и 2, 2и 3,3 и 4,4 т.д. И если наш элемент удовлетворяет условию сортировки, то мы его проталкиваем в конец массива, он как бы всплывает, прямо как «пузырек». От этого и название этого алгоритма.

Вот пример программы с этим алгоритмом.

Program SortPusirkom;

var

mas: array[1..20] of integer;

i, j, k: integer;

begin

randomize;

for i := 1 to 20 do mas[i] := random(100);

writeln('массив до сортировки');

for i := 1 to 20 do write(mas[ i], ' ');

for i := 1 to 19 do

for j := 1 to 20 - i do

if mas[j] > mas[j + 1] then begin

k := mas[j];

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

mas[j + 1] := k;

end;

writeln;

writeln('Отсортированный массив: ');

for i := 1 to 20 do

write(mas[i], ' ');

end.

Ее алгоритм чем-то похож на сортировку выбором. Здесь так же 2 цикла for, но второй цикл идет с 1 до 20 — i.

Кроме того существует второй, не менее известный алгоритм сортировки «пузырьком» с флагом. Флаг — это переменная типа boolean. Из-за этого меняется структура алгоритма, но сущность остается прежней. Вот он:

program SotrSFlagom;

var

a: array[1..20] of integer;

i, j, L: integer;flag: boolean;

begin

randomize;

for i := 1 to 20 do

a[i] := random(100);

writeln('массив до сортировки');

for i := 1 to 20 do write(a[i], ' ');

i:=0;

repeat

i := i + 1;

flag:=false;

for j := 19 downto i do

if a[j] < a[j + 1] then begin

L := a[j]; a[j] := a[j + 1]; a[j + 1] := L;

flag := true;

end;

until not flag;

writeln;

writeln('массив после сортировки');

for i := 1 to 20 do write(a[i], ' ');

end.

Этот алгоритм наиболее сложный для запоминания. Здесь используется внешний цикл repeat … until not flag; Он существует до тех пор, пока флаг не окажется истинным, то есть flag := true; А это может произойти, если наше условие сортировки выполняется. И наш элемент тоже всплывает, как пузырек.

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

Задание № 1. Найдите среднее арифметическое первых двухсот чисел.

Задание № 2. Найдите минимальное число среди введенных 10 чисел.

Задание № 3. Найдите максимальное число среди введенных 15 чисел.

Задание № 4. Расположите в порядке возрастания 10 введенных чисел и выведите их на экран.

Задание № 5. Расположите в порядке убывания 15 введенных чисел и выведите их на экран.

6. Физкультминутка.

7. Итоги учебного занятия

Ответьте на следующие вопросы:

1. Что нового Вы узнали, решив задания на учебном занятии?

2. Задания были сложными? Задания были интересными?

3. Над изучением каких тем в разделе «Изучение языка программирования Pascal» Вы хотели бы ещё поработать?