Сценарий урока Сортировка массива

Урок по информатике по теме «Методика обучения сортировке одномерного массива».

Цели урока:

·        Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом пузырька; повторение алгоритмов ввода/вывода массива, основных изученных алгоритмов обработки массивов

·        Развивающая: развитие познавательного интереса учащихся

·        Воспитательная: привитие учащимся навыков самостоятельности в работе; воспитание чувства коллективизма, ответственности.

Тип урока: урок ознакомления с новым материалом

Вид урока: урок-практикум.

Формы обучения: коллективная, индивидуальная.

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

Оборудование:

• компьютеры,
• проектор,
• программное обеспечение – презентация по теме “Методы сортировки массивов”, АВС-Pascal

Используемые технологии: компьютерные технологии обучения, технология личностно-ориентированного обучения

№	Этапы урока	№  слайда	Действия учителя	Действия ученика
1	Сообщение темы и постановка целей урока		Здравствуйте, ребята! Сегодня мы продолжаем знакомство со способами обработки одномерных массивов. Наше занятие является логическим продолжением предыдущих. Его тема «Методы сортировки одномерных массивов». Цель урока – научиться сортировать массив и применять алгоритм сортировки для решения практических задач.
2	Актуализация опорных знаний учащихся		Давайте повторим материал, пройденный ранее. 1.     Что такое одномерный массив? 2.     В чем заключается главное свойство одномерного массива? 3.     Какие вы знаете способы заполнения и вывода на экран одномерного массива? 4.     Перечислите изученные типы задач на обработку одномерных массивов	Устные ответы учащихся: 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); 2. 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 (i<=n) and (a[i] mod 2 <>0) do inc(i); if i>n 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 градусов. Список номеров месяцев расположить в порядке убывания среднемесячных температур. 2. Ввести в массив n произвольных чисел (n<=30) Отсортировать отрицательные по убыванию, положительные – по возрастанию, оставив отрицательные на местах, принадлежащих отрицательным, а положительные – на местах, принадлежащих положительным. Вывести на экран исходный и полученный массивы. Дополнительных массивов не использовать Пример карточек на «4» балла: 1. Заданы 2 списка: в одном – фамилии спортсменов-участников турнира, в другом – занятые ими места. Переставить фамилии спортсменов в первом списке в соответствии с занятыми местами и вывести его на экран. В турнире участвовало n спортсменов (n<=20) 2. Известны сведения о результатах сдачи ЕГЭ n учениками класса(n<=20). О каждом учащемся известны: фамилия и набранный балл. Вывести в алфавитном порядке фамилии тех, кто набрал не менее минимального балла (41). Пример карточек на «3» балла: 1. Дан целочисленный массив из 10 элементов. Вывести на экран все его четные элементы, предварительно расположив их по убыванию методом пузырька. 2. Дан целочисленный массив из 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]<t[j]) then 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]<0) and ( m[j]<0) and  (m[i]<m[j]) then 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]<m[j+1] then begin                          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). Выдать на экран названия убыточных изделий. Список расположить в порядке уменьшения себестоимости. Учесть, что среди рассматриваемых изделий убыточных может не быть. Текст задач находится в почтовом ящике класса.

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

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

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;

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

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

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;

• 1 слайд

  Методы сортировки одномерных массивов.
  

• 2 слайд

• 3 слайд

  Метод прямого выбора.
  
  Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:
  Просматривая массив с первого элемента, найти минимальный и поменять его местами с первым элементом.
  Просматривая массив со второго элемента, найти минимальный и поменять его местами со вторым элементом.
  И, так далее, до последнего элемента.
  
  

• 4 слайд

• 5 слайд

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

• 6 слайд

  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;
  

• 7 слайд

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

• 8 слайд

  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» баллов:

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

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]<t[j]) then

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.

1.Ввести в массив n произвольных чисел (n<=30) Отсортировать отрицательные по убыванию, положительные – по возрастанию, оставив отрицательные на местах, принадлежащих отрицательным, а положительные – на местах, принадлежащих положительным. Вывести на экран исходный и полученный массивы. Дополнительных массивов не использовать.

Задача  на «4» балла:

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

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.

2.Известны сведения о результатах сдачи ЕГЭ n учениками класса(n<=20). О каждом учащемся известны: фамилия и набранный балл. Вывести в алфавитном порядке фамилии тех, кто набрал не менее минимального балла (41).

Задача  на «3» балла:

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

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]<m[j+1] then begin

                         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.

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

Самостоятельная работа: « Сортировка массивов».

Задача на «5» баллов:

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

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]<t[j]) then

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.

1.Ввести в массив n произвольных чисел (n<=30) Отсортировать отрицательные по убыванию, положительные – по возрастанию, оставив отрицательные на местах, принадлежащих отрицательным, а положительные – на местах, принадлежащих положительным. Вывести на экран исходный и полученный массивы. Дополнительных массивов не использовать.

Задача  на «4» балла:

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

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.

2.Известны сведения о результатах сдачи ЕГЭ n учениками класса(n<=20). О каждом учащемся известны: фамилия и набранный балл. Вывести в алфавитном порядке фамилии тех, кто набрал не менее минимального балла (41).

Задача  на «3» балла:

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

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]<m[j+1] then begin

                         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.

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