Cортировка одномерного массива

№

Этапы урока

№ слайда

Действия учителя

Действия ученика

1

Сообщение темы и постановка целей урока

Здравствуйте, ребята! Сегодня мы продолжаем знакомство со способами обработки одномерных массивов. Наше занятие является логическим продолжением предыдущих. Его тема «Методы сортировки одномерных массивов». Цель урока – научиться сортировать массив и применять алгоритм сортировки для решения практических задач.

2

Актуализация опорных знаний учащихся

Давайте повторим материал, пройденный ранее.

1. Что такое одномерный массив?

1. В чем заключается главное свойство одномерного массива?

1. Какие вы знаете способы заполнения и вывода на экран одномерного массива?

1. Перечислите изученные типы задач на обработку одномерных массивов

Устные ответы учащихся:

1. Одномерный массив-это упорядоченная совокупность однотипных переменных, последовательно расположенных в памяти ЭВМ. Весь массив имеет одно общее имя, а каждый элемент массива- свой номер. Устный ответ учащегося

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

3. Ответы с записью на доске:

3.1 Способы заполнения массива:

• С клавиатуры:

for i:=1 to n do read(a[i]);

• Случайным образом:

randomize;

for i:=1 to n do

a[i]:= -10+random(21);

• Из файла:

assign(f,’input.dat’);

reset(f);

for i:=1 to n do read(f,a[i]);

close(f);

3.2 Способы вывода массива на экран:

• в строку:

for i:=1 to n do write(a[i],’ ‘);

• в столбец:

for i:=1 to n do writeln(a[i]);

Устный ответ:

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

№1

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

Учащийся при помощи ИД перетаскивает подписи к алгоритмам:

• алгоритм поиск суммы элементов:

s:=0;

for i:=1 to n do

if a[i]0 then s:=s+a[i];

writeln(s);

• алгоритм поиска количества

элементов:

k:=0;

for i:=1 to n do

if a[i]0 then k:=k+1;

writeln(k);

• алгоритм поиска максимального элемента:

m:=-maxint;

for i:=1 to n do

if a[i]m then m:=a[i];

writeln(m);

• алгоритм исследования массива:

f:=0;

for i:=1 to n do

if a[i]0 then f:=1;

if f=0 then write(‘yes’) else write(‘no’);

3

Проверка домашнего задания

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

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

Сравните приведенные варианты программ с точки зрения эффективности.

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

1. var a: array [1..30] of integer; f,i,k: integer;

begin f:=0;

for i:=1 to 30 do

begin

read(a[i]);

if (a[i] mod 2=0) and (f=0) then

begin f:=1; k:= i end;

end;

writeln;

if f=0 then write(‘четных нет’) else write(k);

1. const n=30;

var a: array [1..n] of integer; i: integer;

begin

for i:=1 to 30 do read(a[i]); writeln;

i:=1;

while (i0) do inc(i);

if in then write(‘четных нет’) else write(i);

Устный ответ:

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

4

Ознакомление с новым материалом

Итак, массив- это в некотором роде список. А списки, как вы знаете, часто приходится упорядочивать. Поэтому сегодня на уроке мы познакомимся с новым типом задач на обработку одномерных массивов – с их сортировкой. Существует несколько методов сортировки, мы рассмотрим два из них. Будем рассматривать сортировку элементов массива по возрастанию.

№2

Метод прямого выбора.

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

1. Просматривая массив с первого элемента, найти минимальный и поменять его местами с первым элементом.

2. Просматривая массив со второго элемента, найти минимальный и поменять его местами со вторым элементом.

3. И, так далее, до последнего элемента.

Учитель демонстрирует алгоритм при помощи ИД.

Давайте попробуем записать этот алгоритм на Паскале.

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

Учащийся записывает алгоритм на доске, весь класс ему помогает. Учащиеся записывают алгоритм в тетрадь:

for i:=1 to n-1 do

for j:= i+1 to n do

if a[i]a[j] then

begin

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

end;

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

Устный ответ учащегося:

нужно поменять в алгоритме знак «больше» на знак «меньше»

№3

Метод пузырька.

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

Учитель демонстрирует алгоритм при помощи ИД.

Давайте попробуем записать этот алгоритм на Паскале.

Учащийся записывает алгоритм на доске, весь класс ему помогает. Учащиеся записывают алгоритм в тетрадь:

for i:=1 to n-1 do

for j:=1 to n-i do

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

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

end;

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

Устный ответ учащегося:

нужно поменять в алгоритме знак «больше» на знак «меньше»

5

Первичное закрепление нового материала

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

Пример карточек на «5» баллов:

1. Известны среднемесячные температуры за год. Вывести на экран список номеров месяцев, в которых средняя температура была выше 7 градусов. Список номеров месяцев расположить в порядке убывания среднемесячных температур.

1. Ввести в массив n произвольных чисел (n

Пример карточек на «4» балла:

1. Заданы 2 списка: в одном – фамилии спортсменов-участников турнира, в другом – занятые ими места. Переставить фамилии спортсменов в первом списке в соответствии с занятыми местами и вывести его на экран. В турнире участвовало n спортсменов (n

1. Известны сведения о результатах сдачи ЕГЭ n учениками класса(n

Пример карточек на «3» балла:

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

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

Учащиеся выполняют за компьютерами задания.

var m,t: array[1..12] of integer; i, j, c:integer;

begin

for i:=1 to 12 do

begin

m[i]:=i; write(‘введите температуру’,i,’месяца’); readln(t[i]);end;

for i:=1 to 11 do

for j:= i+1 to 12 do

if (t[i]7) and ( t[j]7) and (t[i]

begin

c:=t[i]; t[i]:=t[j]; t[j]:=c;

c:=m[i]; m[i]:=m[j]; m[j]:=c;

end;

for i:=1 to 12 do

if t[i]7 then writeln(m[i]);

end.

var m: array[1..30] of integer; i, j, c:integer;

begin

readln(n);

for i:=1 to n do readln(m[i]);

for i:=1 to n do write(m[i],’ ‘); writeln;

for i:=1 to n-1 do

for j:= i+1 to n do

begin

if (m[i]0) and ( m[j]0) and (m[i]m[j]) then

begin

c:=m[i]; m[i]:=m[j]; m[j]:=c;

end;

if (m[i]

begin

c:=m[i]; m[i]:=m[j]; m[j]:=c;

end;

end;

for i:=1 to n do write(m[i],’ ‘);

end.

var f: array[1..20] of string; m: array[1..20] of integer;k: string; i, j, c:integer;

begin

readln(n);

for i:=1 to n do

begin

write(‘введите фамилию’); readln(f[i]);

write(‘введите место’); readln(m[i]);

end;

for i:=1 to n-1do

for j:= i+1 to n do

if (m[i]m[j]) then

begin

k:=f[i]; f[i]:=f[j]; f[j]:=k;

c:=m[i]; m[i]:=m[j]; m[j]:=c;

end;

for i:=1 to ndo

writeln(f[i]);

end.

var f: array[1..20] of string; m: array[1..20] of integer; k: string; i, j, c:integer;

begin

readln(n);

for i:=1 to n do

begin

write(‘введите фамилию’); readln(f[i]);

write(‘введите балл’); readln(m[i]);

end;

for i:=1 to n-1do

for j:= i+1 to n do

if (f[i]f[j]) then

begin

k:=f[i]; f[i]:=f[j]; f[j]:=k;

c:=m[i]; m[i]:=m[j]; m[j]:=c;

end;

for i:=1 to ndo

if m[i]=41 then writeln(f[i]);

end.

var m: array[1..10] of integer; i, j, c:integer;

begin

for i:=1 to 10 do readln(m[i]);

for i:=1 to 9 do

for j:=1 to 10-i do

if m[j]

c:=m[j]; m[j]:=m[j+1]; m[j+1]:=c;

end;

for i:=1 to 10 do

if m[i] mod 2=0 then write (m[i],’ ‘);

end.

var m: array[1..10] of integer; i, j, c:integer;

begin

for i:=1 to 10 do readln(m[i]);

for i:=1 to 9 do

for j:= i+1 to 10 do

if (m[i]m[j]) then

begin

c:=m[i]; m[i]:=m[j]; m[j]:=c;

end;

for i:=1 to 10 do

if m[i] mod 2=1 then write (m[i],’ ‘);

end.

6

Подведение итогов урока

Проверка работающих программ и выставление оценок за урок.

7

Постановка домашнего задания

Составить программу на Паскале для решения следующих задач:

1. Каждая из 30 групп студентов имеет свой процент успеваемости(от 0 до 100%). Составить список номеров групп, которым необходимо повысить успеваемость до фактического среднего уровня. Список расположить в порядке убывания процента успеваемости групп.

2. Известно название, себестоимость и цена каждого из к изделий(к не более 30). Выдать на экран названия убыточных изделий. Список расположить в порядке уменьшения себестоимости. Учесть, что среди рассматриваемых изделий убыточных может не быть.

Текст задач находится в почтовом ящике класса.