Цель: Закрепление и отработка навыков составления алгоритмов работы с табличными величинами. Закрепление навыков общения с ЭВМ.
Обеспечение урока:
а) Программа KUMIR.EXE.
б) Программа: UPRD.E
Проверку домашнего задания не проводить из-за дефицита времени необходимого на объяснение нового материала. Проверку умений и навыков составления алгоритмов обработки табличных величин проведем на последующих уроках.
а) Упорядочение (сортировка) таблиц одна из необходимых задач информатики. Упорядоченные таблицы значительно сокращают впоследствии время на поиск нужной информации. Алгоритмов сортировки таблиц довольно много. Все они оладают определенными достоинствами, а также и недостатками. Единого алгоритма сортировки не существует т.к. информация в таблицах может быть самая разная и задачи сортировки также самые разные.
б) Идея простейшего алгоритма сортировки линейной таблицы с числовыми величинами такова: Найти минимальный элемент и поменять его местами с первым элементом таблицы. Затем рассматривать укороченную таблицу (без первого элемента), снова найти минимальный элемент и, снова поменять его местами с первым элементом теперь уже укороченной таблицы и т.д., пока не будет просмотрена вся таблица.
Для наглядности рассмотрим сортировку линейной таблицы целых чисел состоящей
из пяти элементов. Лучше всего объяснение проводить на магнитной доске на которой
заранее начертить МЕЛОМ таблицу. Бумажными листами, рижимая их магнитами, закрывать
и открывать начало таблицы, демонстрируя полную и укороченную таблицу. При перестановке
элементов таблицы нам придется стирать старое значение элеменов и здесь надо
обратить внимание учащихся на то, что для временного хранения значений элементов
таблицы при перестановке нам понадобится промежуточная величи-
на. Рисуем рядом с таблицей прямоугольник, подписываем его каким нибудь именем,
например r. Объяснение начинает учитель и в сильном классе третий и четвертый
шаг можно поручить кому либо из учащихся с обязательным проговариванием всех
действий вслух.
1 шаг.
|
1
|
2
|
3
|
4
|
5
|
|
8
|
6
|
4
|
2
|
7
|
а) найдем МИНЭЛЕМЕНТ в таблице с номерами от 1 до 5. Им
оказался элемент с номером 4 (число 2).
б) Поменяем местами элемент с номером 4 (число 2) и элемент
с номером 1 (число 8).
В результате получим таблицу:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
6
|
4
|
8
|
7
|
2 шаг. Теперь рассмотрим укороченную таблицу со 2-го по 5-й
элемент:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
6
|
4
|
8
|
7
|
а) найдем МИНЭЛЕМЕНТ в таблице с номерами от 2 до 5. Им
оказался элемент с номером 3 (число 4).
б) Поменяем местами элемент с номером 3 (число 4) и элемент
с номером 2 (число 6).
В результате получим таблицу:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
8
|
7
|
А в целом виде таблица в конце этого шага будет выглядеть так:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
8
|
7
|
3 шаг. Теперь рассмотрим укороченную таблицу с 3-го по 5-й
элемент:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
8
|
7
|
а) найдем МИНЭЛЕМЕНТ в таблице с номерами от 3 до 5. Им
оказался элемент с номером 3 (число 6).
б) Поменяем местами элемент с номером 3 (число 6) и элемент
с номером 3 (число 6). (Этот шаг покажется на первый
взгляд ненужным, но при внимательном рассмотрении он
просто необходим для формализации действий. Ведь испол-
нение алгоритма в конечном счете мы будем поручать "иди-
оту".)
В результате получим таблицу:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
8
|
7
|
А в целом виде таблица в конце этого шага будет выглядеть так:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
8
|
7
|
4 шаг. Теперь рассмотрим укороченную таблицу с 4-го по 5-й
элемент:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
8
|
7
|
а) найдем МИНЭЛЕМЕНТ в таблице с номерами от 4 до 5. Им
оказался элемент с номером 4 (число 8).
б) Поменяем местами элемент с номером 4 (число 8) и элемент
с номером 5 (число 7).
В результате получим таблицу:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
7
|
8
|
А в целом виде таблица в конце этого шага будет выглядеть так:
|
1
|
2
|
3
|
4
|
5
|
|
2
|
4
|
6
|
7
|
8
|
Мы видим, что таблица оказалась упорядоченной и на это потре-
бовалось 4 шага т.е. n-1 шаг где n-число элементов в таблице.
а) Выделяем аргументы и результаты. Из постановки задачи видно, что аргументом
пусть будет целтаб а [1:5] и результа-
том будет эта же таблица с этим же именем, но только упорядоченная. Значит заголовок
алгоритма будет таким:
алг упорядочение (целтаб а [1:5])
дано а
надо а
нач
|
кон
б) Теперь структура алгоритма. Для работы с табличными величинами, как правило,
требуется циклическая структура и
счетчик для просмотра элементов таблицы, который будет изменятся от 1 до n-1.
В цикле обязательно должна стоять команда изменяющая условие ПОКА. (Это команда
i:=i+1.) Дополним наш заголовок этими соображениями.
алг упорядочение (целтаб а [1:5])
дано а
надо а
нач цел i
| i:=1
| пока i<5
| нц
| |
| |
| | i:=i+1
| кц
кон
в) Замечаем, что на каждом шаге упорядочения мы обращались к одним и тем же действиям: поиску минэлемента и перестановки элементов таблицы. Дополним наш алгоритм этими соображениями.
алг упорядочение (целтаб а [1:5])
дано а
надо а
нач цел i
| i:=1
| пока i<5
| нц
| | поиск номера минэлемента
| | перестановка элементов таблицы
| | i:=i+1
| кц
кон
г) И, наконец, осталась самая малость: поиском минэлементапусть занимается алгоритм МИНЭЛЕМЕНТ. Вызовем его командойминэлемент (i,5,а,l), где i-номер начала укороченной таблицы, 5-номер последнего элемента, а-перечень самих элементов таблицы с именем а, l-номер минэлемента.Перестановкой элементов пусть занимается следующая серия команд:
r:=а[i]
а[i]:=а[l]
а[l]:=r
Замечаем, что r и l некие промежуточные величины, требующиеописания.
Окончательно с учетом всех соображений имеем следующий вид
алгоритма:
алг упорядочение (целтаб а [1:5])
дано а
надо а
нач цел i,l,вещ r
| i:=1
| пока i<5
| нц
| | минэлемент (i,5,а,l)
| |
| | r:=а[i]
| | а[i]:=а[l]
| | а[l]:=r
| |
| | i:=i+1
| кц
кон
Здесь необходимо сравнить полученный текст алгоритма с текстом в учебнике. Учащиеся
должны увидеть, что в тексте учебника в заголовке описаны еще две величины:
номер начала таблицы и номер конца таблицы. Дальнейшее усовершенствование алгоритма
в сильном классе поручить учащимся, в слабом это необходимо сделать самому учителю.
Но итогом работы должен стать в конечном счете текст алгоритма из учебника.
Это повышает уверенность в
понимании учебного материала.
