Алгоритм упорядочивания элементов массива

№___27____САБАҚТЫҢ ОҚУ-ӘДІСТЕМЕЛІК ЖОСПАРЫ

УЧЕБНО-МЕТОДИЧЕСКИЙ ПЛАН ЗАНЯТИЙ №__27___

Предмет _______________Основы алгоритмизации и программирования______________

Топ

Группа_________________________ПО-21_________________________________________

Күні

Дата___________________________6.12.2016______________________________________

Тақырыбы:Алгоритм упорядочивания элементов массива

Тема:

Сабақтың түрі:________________Комбинированный______________________________

Вид урока:

Сабақтың мақсаты:

Цели урока:

*Изучить основные методы работы с одномерными массивами на языке программирования

Pascal;

* Воспитать интерес к изучаемому предмету;

* Развить логическое мышление и навыки самостоятельной учебной деятельности;

Студент должен овладеть компетенциями:

Уметь:правильно описать массив; обращаться к элементам массива; задавать значения элементам массива; вводить и выводить значения элементов массива; создавать Паскаль-программы, используя основные алгоритмические конструкции;

Знать:операторы языка Паскаль для составления простых алгоритмов с использованием одномерных массивов;

Пәнаралық байланыс:

Межпредметные связи: Информатика, математика, основы информатизации;

Көрнекі құралдар,жабдықтар, үлестірме материалдар

Наглядные пособия, оборудования, раздаточный материал

Интерактивная доска, подиум, ноутбуки, программа для тестирования «HyperTest», карточки с заданями, презентация, программа PascalABC; приложение 1.1, приложение 1.2, приложение 2.1, приложение 2.2

САБАҚ БАРЫСЫ \ ХОД УРОКА

I.Ұйымдастыру кезеңі: Приветствие / Проверка посещаемости –2 минуты

Организационная часть

II.Өткен тақырыпты қайталау: Повторение пройденного материала – 13 минут

Опрос и проверка пройденного материала:(приложение 1.1, приложение 1.2)

Решение тестовых заданий на компьютере; - Павличенко Б., Сагитов Р., Сурин Р., Мейрманов Д., Нурболат Б., Махметова Э.

Решение задач по карточкам (составление алгоритма и блок-схемы); - Моисеев С., Носков М., Мальцев В., Пономаренко В.

Опрос у доски; - Смирнов Р., Селиверстов К., Леонгарди В.

III.Жаңа тақырыпты зерделеу

Изучение нового материала

Тақырыбы:Алгоритм упорядочивания элементов массива

Тема:

ЖОСПАР \ ПЛАН

1. Записать в тетрадях новую тему и дату.

2. Мотивирующий настрой студентов на работу

3. Изучение новой темы, изложение лекции (приложение 2.1)

* Для чего нужны массивы в программе;

*Что такое индекс ячейки массива;

*Изобразить в виде таблицы массив;– 25 минут;

*Что такое массив и способы создания;

*Обращение к элементам массива;

*Способы ввода данных в массив;

*Сортировка методом «Пузырька»;

*Записать словесный алгоритм;

*Расписать пример сортировки;

4. Совместно со студентами разобрать задачу,

составить алгоритм и блок-схему; -10 минут;

5 . Выполнение практической части: (приложение 2.2)

Решение задач и составление программ с использованием - 30 минут;

массива данных;

IV.Бекіту:

Закрепление:

Вопросы для закрепления: - 10 минут;

Как описать массив в разделе описаний переменных?

Как описать массив через создание типа?

Какой алгоритм используется для ввода данных в массив?

Какой алгоритм используется для вывода данных из массива?

Какие способы ввода данных в массив вы знаете?

Каким образом можно выполнить сортировку данных массива?

V.Үй тапсырмасы:

Домашнее задание: 5. 27-47; конспект;

VI.Өздік жұмысы:

Самостоятельная работа: Решение задач и составление алгоритмов в программе PascalABC;

Оқытушы:

Преподаватель:Шудабаев Р.М.

Приложение 1.1

Вопросы для фронтального опроса:

Что такое массив? Назовите способы описания одномерного массива? (выйти к доске и расписать фрагменты кода) - Леонгарди В.

Как присвоить значение N-му элементу массива? Назовите способы ввода-вывода данных в массив. (на доске привести пример с блок-схемой) -Селиверстов К.

Расписать на доске алгоритмы нахождения суммы и произведения элементов одномерного массива. Составить к ним блок-схемы - Смирнов Р.

Приложение 1.2 (карточки)

Задача №1. Найти номер позиции, с которой в заданной строке в первый раз встретится некоторое введенное слово. (Моисеев С.)

Program P1;

Var st1, st2:string;

T:integer;

Begin

Write(‘Введитестроку: ’); readln(st1);

Write(‘Введитеслово: ’); readln(st2);

T:=pos(St2,st1);

Writeln(‘Введенное слово начинается с ',t,'позиции');

End.

Задача №2. Дан массив размером от 1-50. Заполнить массив случайными целочисленными значениями(от 1 до 100), вывести на экран все элементы из интервала от C и D. (Мальцев В.)

Program P2;

vara:array[1..50] of integer;

c,d,i:integer;

begin

Writeln('Массив заполнен случайными значениями от 1 до 100');

for i:=1 to 50 do

a[i]:=random(100);

writeln;

writeln('Введите интервал элементов C иD, который необходимо вывести на экран: ');

readln(c,d);

For i:=C to D do

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

end.

Задача №3. Составить программу вычисления заданного одномерного целочисленного массиваA=(a₁,a₂,…,a_n).(Носков М.)

Program P3;

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

I,sum:integer;

Begin

sum:=0;

Writeln(‘Введитецелыечисла: ’);

For i:=1 to 10 do begin

Write(‘a[‘,i,’]=’);

Readln(a[i]);

Sum:=sum+a[i];

End;

Writeln;

Writeln(‘Сумма элементов массива = ’,sum);

end.

Задача №4. Дан массив размером от 1-20. Заполнить массив случайными целочисленными значениями(от 1 до 100), вывести на экран все элементы. (Пономаренко В.)

Program P4;

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

c,d,i:integer;

begin

Writeln('Массив заполнен случайными значениями от 1 до 100');

for i:=1 to 50 do

a[i]:=random(100);

writeln;

writeln('Введите интервал элементов C иD, который необходимо вывести на экран: ');

For i:=C to D do

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

end.

Приложение 2.1

Новая тема:

«Алгоритм упорядочивания элементов массива»

Предположим, что программа работает с большим количеством однотипных данных. Скажем около ста разных целых чисел нужно обработать, выполнив над ними те или иные вычисления. Как вы себе представляете 100 переменных в программе? И для каждой переменной нужно написать одно и тоже выражение вычисления значения? Это очень неэффективно.

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

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

Итак, массив – это именованная группа однотипных данных, хранящихся в последовательных ячейках памяти. Каждая ячейка содержит элемент массива. Элементы нумеруются по порядку, но необязательно начиная с единицы (хотя в языке программирования Pascal чаще всего именно с нее). Порядковый номер элемента массива называется индексом этого элемента.

Помним, все элементы определенного массива имеют один и тот же тип. У разных массивов типы данных могут различаться. Например, один массив может состоять из чисел типа integer, а другой – из чисел типа real.

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

Массив можно создать несколькими способами.

…

const n = 200;

type

months = (jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec);

years = 1900..2100;

people = array[years]oflongint;

var

growth:array[months]ofreal;

hum: people;

notes:array[1..n]ofstring;

Обращение к определенному элементу массива осуществляется путем указания имени переменной массива и в квадратных скобках индекса элемента.

Простой массив является одномерным. Он представляет собой линейную структуру.

var ch: array [1..11] ofchar;

h:char;

i:integer;

begin

for i := 1 to 11 do read (ch[i]);

for i := 1 to 11 do write (ch[i]:3);

readln

end.

*** Показать способы ввода данных в массив

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

Алгоритм решения задачи: 

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

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

Алгоритм и особенности этой сортировки таковы:

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

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

При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.

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

В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.

После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.

Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).

При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

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

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

Программа на языке Паскаль: 

const

m = 10;

 var

arr:array[1..m]ofinteger;

i, j, k: integer;

begin

randomize;

write ('Исходныймассив: ');

for i := 1 to m dobegin

arr[i] := random(256);

write (arr[i]:4);

end;

writeln; writeln;

  for i := 1 to m-1 do

for j := 1 to m-i do

if arr[j] > arr[j+1] thenbegin

k := arr[j];

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

arr[j+1] := k

end;

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

for i := 1 to m do

write (arr[i]:4);

writeln;

end.

Приложение 2.2

Задачи

Уровень 1. Легкий

Задача №1.Дан одномерный массив (1-20). Заполнить массив случайными целочисленными значениями в диапазоне от 0-50 и вывести на экран данный массив. Выполнить сортировку массива и вывести на экран.

programp1;

constm=20;

var a:array[1..m] of integer;

i,j,n:integer;

begin

writeln('==========Массив==========');

for i:=1 to m do begin

a[i]:=random(51);

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

end;

writeln;

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

for j:=1 to m-1 do

for i:=1 to m-j do

if a[i]>a[i+1] then begin

n:=a[i];

a[i]:=a[i+1];

a[i+1]:=n;

end;

for i:=1 to m do

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

end.

Вопрос: «Как сделать сортировку по убыванию?»

Уровень 2. Средний

Задача №1.Составить программу, в которой пользователю предлагается ввести слово. После чего данное слово разбивается на символы и которые заполняют элементы массива. Вывести на экран отсортированный массив по алфавиту.

programp2;

constm=50;

var a:array[1..m] of char;

i,j:integer;

st:string;

n:char;

begin

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

readln(st);

for i:=1 to length(st) do begin

a[i]:=st[i];

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

end;

writeln;

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

for i:=1 to length(st)-1 do

for j:=1 to length(st)-i do

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

n:=a[j];

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

a[j+1]:=n;

end;

for i:=1 to length(st) do

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

end.

Вопрос: «Как сделать сортировку по убыванию?»

Запасная задача:

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

Уровень 3. Сложный

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

Описание переменных: 

goods - массив-константа названий товаров;

price - массив-константа цен товаров;

i - счетчик;

g - введенный пользователем номер товара;

q - введенное пользователем количество товара;

sum - сумма покупки.

Алгоритм решения задачи: 

Присвоить переменной sum значение 0, после чего в цикле выполнять действия:

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

Если был введен 0, то выйти из цикла.

Запросить количество данного товара.

Добавить к переменной sum произведение цены товара на его количество.

После завершения цикла вывести значение sum на экран.

Программа на языке Паскаль: 

const

N = 10;

goods:array[1..N]ofstring = ('Груши','Яблоки','Огурцы','Помидоры','Укроп','Петрушка','Курица','Сыр','Масло','Молоко');

price:array[1..N]ofreal = (40.50,31.20,21.80,35.00,150.00,145.00,200.00,400.00,81.40,53.35);

var

i, g: byte;

sum, q: real;

begin

for i:=1 to N do

writeln(i,') ', goods[i], ' - ',price[i]:5:2,' руб.');

  writeln('Что берём? (вводите № товара; если ничего, то 0)');

sum := 0;

whileTruedobegin

write('Товар: '); readln(g);

if g = 0 thenbreak;

write('Количество: '); readln(q);

sum := sum + price[g] * q;

end;

writeln('Сумма к оплате: ',sum:6:2);

end. Проверка работы программы:

1) Груши - 40.50 руб.

2) Яблоки - 31.20 руб.

3) Огурцы - 21.80 руб.

4) Помидоры - 35.00 руб.

5) Укроп - 150.00 руб.

6) Петрушка - 145.00 руб.

7) Курица - 200.00 руб.

8) Сыр - 400.00 руб.

9) Масло - 81.40 руб.

10) Молоко - 53.35 руб.

Что берём? (вводите № товара; если ничего, то 0)

Товар: 2

Количество: 0.5

Товар: 5

Количество: 0.1

Товар: 7

Количество: 1.2

Товар: 8

Количество: 0.3

Товар: 10

Количество: 1

Товар: 0

Сумма к оплате: 443.95

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/231015-algoritm-uporjadochivanija-jelementov-massiva