Разработка урока по теме "Двумерные массивы. Алгоритмы сортировки"

Разделы: Информатика

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

Задачи:

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

План урока.

  1. Организационный момент.
  2. Самостоятельная работа.
  3. Решение задач на обработку двумерных массивов.
  4. Объяснение нового материала «Алгоритмы сортировки»
  5. Закрепление изученного материала при решении задач.

Ход урока.

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

Объявление целей, задач и плана урока.

2. Самостоятельная работа (Приложение 1).

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

3. Решение задач

В Приложении 2 находятся: тестирование программы, исполнение алгоритма и блок-схема к задачам, программные коды на языках программирования Pascal и Basic. Разны цвета кода обозначают исполнение отдельного цикла.

Пример 3.1. Вычислить суммы элементов столбцов заданной матрицы A(N, M).

Пример 3.2. Подсчитать, сколько раз встречается в заданной целочисленной матрице A(N, M) максимальное по величине число.

Пример 3.3. В заданной матрице A(N, M) поменять местами строки с номерами P и Q (1 <= P <= N, 1 <= Q <= N).

4. Объяснение нового материала по теме «Алгоритмы сортировки».

Рассмотрим простой алгоритм сортировки, называемый пу­зырьковой сортировкой или сортировкой методом обмена. Задача заключается в том, чтобы отсортировать исходный мас­сив целых чисел так, чтобы элементы располагались в нем в по­рядке возрастания. В пузырьковой сортировке последовательно просматриваются пары соседних элементов массива, и если левый элемент пары больше правого, то есть порядок нарушен, то они меняются местами (отсюда происходит название «метод обмена»). В результате самый большой элемент массива оказы­вается на своем законном последнем месте. Он как бы «всплы­вает» наверх подобно пузырькам в стакане газировки, самые большие из которых проталкиваются к поверхности (отсюда второе название метода - пузырьковая сортировка). Для того чтобы все элементы оказались на своих местах, надо проделать процедуру просмотра и обмена элементов несколько раз. Сколь­ко именно, выясним на примере.

Пусть задан антиупорядоченный массив В = (20,10,8,7,5,2), тогда шаги сортировки будут выглядеть следующим образом:

На первом шаге вначале сравниваются 1-й и 2-й элементы массива - 20 и 10. Так как 20 > 10, они меняются местами, в ре­зультате элемент 20 оказывается на 2-м месте. Затем сравнива­ются 2-й и 3-й элементы массива, а именно 20 и 8, и они меня­ются местами. В результате элемент 20 оказывается уже на 3-м месте и т.д. Последними сравниваются 5-й и 6-й элементы массива (на 5-м месте к этому моменту находится 20) и также меняются местами. После выполнения 1-го шага элемент 20 пе­ремещается на последнее место. Запомним, что на первом шаге выполнялось сравнение следующих элементов: 1-го и 2-го, 2-го и 3-го, 3-го и 4-го, 4-го и 5-го, 5-го и 6-го.

На втором шаге все действия первого шага повторяются, но последними сравниваются 4-й и 5-й элементы, т.е. 10 и 2, и они меняются местами: 5-й и 6-й элементы сравнивать не имеет смысла, так как на предыдущем шаге на 6-е место был передви­нут самый большой элемент.

На третьем шаге выполняется сравнение элементов 1-го и 2-го, 2-го и 3-го, 3-го и 4-го, так как 5-й и 6-й элементы уже сто­ят на своих местах.

На четвертом шаге выполняется сравнение элементов только в двух парах, а именно 1-го и 2-го, 2-го и 3-го.

На пятом шаге сравниваются и переставляются первый и второй элементы массива - 5 и 2, остальные элементы, начиная с третьего, уже располагаются в порядке возрастания.

После того как правильно расставлены 5 элементов масси­ва, 6-й (наименьший элемент) «автоматически» оказывается на 1-м месте.

Итак, для сортировки массива из 6 элементов понадобилось выполнить 5 шагов. Легко догадаться, что отсортировать мас­сив, состоящий из п чисел, можно, выполнив п — 1 шагов.

Перейдем к построению алгоритма. Задан массив А[1..n] из п элементов. Обозначим переменной i номер шага выполнения сортировки, а переменной j - номер первого элемента в паре элементов A[j], A[j +1], которые надо сравнивать.

i = 1: просматриваются пары, в которых номер j изменяется от 1 до п -1 (последними сравниваются элементы, A[n-1],A[n]).

i = 2: просматриваются пары, в которых номер j изменяется от 1  до   n-2  (последними сравниваются элементы   A[n-2],  А[п-1]).

i= 3 : просматриваются пары, в которых номер j изменяется от  1  до   п — 3 (последними сравниваются элементы   A[n —3], А[п-2]).

…

i = n-1: просматриваются пары, в которых номер j изменя­ется от 1 до п - (п -1) = 1 (сравниваются только элементы А [1], A[2]).

Из описанного выше можно сделать следующие выводы:

  1. всего выполняется (п —1) шагов, то есть переменная i из­меняется от 1 до (n -1);
  2. на i-м шаге просматриваются пары, в которых номеру из­меняется от 1 до (n-1) .

Опишем алгоритм в словесно-пошаговой форме (t - пере­менная для обмена значений элементов).

  1. Задать массив A[1..n] (элементы массива можно ввести с клавиатуры, задать с помощью генератора псевдослучайных чи­сел или прочитать из файла).
  2. i:=1.
  3. Если i < п, то перейти к пункту 4, иначе перейти к пункту 9.
  4. j:=1.
  5. Если j < п - i, то перейти к пункту 6, иначе i-й шаг сорти­ровки выполнен, перейти к пункту 8.
  6. Если  A[j]>A[ j + 1], то поменять их местами:  t:=A[j]; A[j]: =A[j + 1];A[j +1l]: = t.
  7. Увеличить номеру (j:=j+1) и перейти к пункту 5.
  8. Увеличить номер / (i:=i+1) и перейти к пункту 3.
  9. Сортировка массива завершена. Вывод массива.

Для перехода к программной реализации обратим внимание на то, что пункты 4, 5, 6, 7 составляют внутренний цикл, в кото­ром переменная j изменяется от 1 до (п -1), а в пунктах 2, 3 и 8 записаны условия выполнения внешнего цикла, в котором пе­ременная iизменяется от 1 до (n—1).

Программа пузырьковой сортировки массива

Program Bubble;

Const   n=10;

Var A: array [l..n] of real; {массив вещественных чисел}

i,   j:integer;

t: real; {переменная для обмена должна быть та­кого же типа,   как и элементы массива!}

begin                                                                                                    

for i:=l to n do read(A[i]);   {создание массива}

{сортировка}

for  i:=l  to n-1  do for j:=1   to n-i  do

if A[j]>A[j+l]   then                                                           £>

begin       

t:=  A[j] ;  

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

A[j+1] :=t;                                                                                           

end;

for  i:=l   to  n  do 

write(A[i] :3:1,    '   ');   {вывод отсортированного массива}

end.

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

Еще один вариант пузырьковой сортировки базируется на сле­дующем наблюдении. Если на очередном шаге не было сделано ни одного обмена, то массив уже упорядочен и выполнять осталь­ные шаги не надо (особенно эффективен этот подход, если нам дан уже упорядоченный массив). Для определения, что не было произведено ни одного обмена, используют булеву переменную, значение которой делают равным trueпри выполнении условия A[j]>A[j + 1], а перед выполнением очередного шага сорти­ровки ее значение изменяют на false. Если после выполнения шага ее значение так и осталось равным false, то сортировку за­вершают.

Выводы:

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

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

Последовательно сравниваются пары соседних элементов аk и a k+1 (k=1,2,…,n-1)  и, если аk> a k+1, то они переставляются; таким образом наибольший элемент окажется на своем месте в конце массива. Затем этот метод применяется ко всем элементам, кроме последнего и т. д.

Метод вставок.

Пусть первые k элементов массива уже упорядочены по возрастанию. Берется (k+ 1)-й элемент и размещается среди первых к элементов так, чтобы упорядоченными оказались уже (k + 1) первых элементов. Этот метод применяется при k от до (n - 1).

Упражнения.

Упражнения этого раздела помогут вам глубже понять и за­помнить два важных метода сортировки: метод выбора и метод «пузырька».

  1. Какой смысл имеет фраза: «Выполнить сортировку дан­ных»?
  2. В каком из известных вам методов на каждом шаге сорти­ровки выбирается минимальный элемент?
  3. Задан массив целых чисел A[1..7]. Требуется упорядочить элементы в нем по возрастанию, применяя метод «пузырька» так, чтобы на каждом шаге алгоритма очередной наибольший элемент передвигался на свое место. Покажите, как будет выглядеть массив после каждого шага сортировки.

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

Что является затруднительным. Проговорить алгоритм выполнения домашнего задания.

5. Домашнее задание.

1. Заполните схему алгоритма сортировки элементов массива A[1..n] по возрастанию методом «пузырька»

2. Провести сортировку списка фамилий учеников класса по алфавиту.

Описание: Будем считать, что фамилии учеников начинаются с разных букв. Тогда задача сводится к сравнению первых букв фамилий и сортировке фамилий в алфавитном порядке. Будем использовать следующие обозначения: а — массив строкового типа, содержащий фамилии учеников класса; n — размер массива (количество элементов в массиве).

Литература

  1. Андреева Е.В. Методика обучения основам программирования на уроках информатики. М.: Педагогический университет «Первое сентября», 2006.
  2. Ракитина Е.А., Бешенков С.А., Галыгина И.В., Милохина Л.В. Сборник типовых задач по информатике. М.: Образование и информатика, 2005
  3. Тимошевская Н.Е. Задачник по программированию на языке Pascal. Томск, 2004