Примеры проектирования алгоритмов с использованием

технологий «сверху вниз» и «снизу вверх»

Этапы изучения учебного материала содержательной линии

«Алгоритмизация и программирование»

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

1. Пропедевтический (подготовительный) этап формирования основных понятий содержательной линии «Алгоритмизация и программирование»

На данном этапе овладение основными понятиями содержательной линии, основными управляющими командами организации действий проводится без использования величин. На этом этапе рассматриваются две технологии проектирования алгоритма «снизу вверх» и «сверху вниз». Задачи берутся из практической жизни школьников, задачи управления автоматическими устройствами (роботами). Использование исполнителей типа Робот и Чертёжник для решения поставленных на данном этапе целей позволяет длительное время обходиться без понятия величины. Для индивидуализации учения в задачах варьируется состояние обстановки на поле Робота. Бездумные исполнители позволяют сделать процесс введения величин плавным и естественным. Результаты работы исполнителей можно легко изобразить на классной доске, в тетради или в системе Кумир с использованием Пульта управления. Оказался плодотворным следующий методический приём исполнения алгоритма: на уроке один ученик исполняет роль устройства управления, а другой – роль автоматического исполнителя, изображая результаты исполнения алгоритма на доске или в системе Кумир.

2. Основной этап формирования понятий содержательной линии «Алгоритмизация и программирование».

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

Главная особенность при поэтапном изучении учебного материала содержательной линии «Алгоритмизация и программирование» заключается в том, что первоначальное знакомство с основными понятиями содержательной линии проводится с опорой на наглядные, житейские представления школьников, не привлекая на первых порах ни математической символики, ни математических понятий, что заметно упрощает овладение этими понятиями. К идее привлечения образно-наглядного мышления школьников при введении основных понятий рассматриваемой содержательной линии независимо пришли исследователи и педагоги разных стран: Сеймур Пейперт (США), Г.А. Звенигородский (СССР), А.Г. Кушниренко (СССР) и др.

Примеры проектирования алгоритмов с использованием технологии «сверху вниз»

Пример 1. Написать алгоритм рисования улицы из трех домиков, для исполнителя Чертёжника. (Пропедевтический этап изучения учебного материала содержательной линии «Алгоритмизация и програм­мирование»).

Решение. Для решения поставленной задачи хорошо бы уметь писать для Чертёжника алгоритмы рисования одного домика и перехода к рисованию другого домика, тогда решение поставленной задачи станет очевидным. Программа рисования улицы будет иметь вид – “алг улица”, табл. 1.Команды“домик” и “обход” в алгоритме“улица” – это команды обращения к вспомогательным, ещё не написанным алгоритмам. Эти алгоритмы необходимо написать. Как написать алгоритм рисования домика для Чертёжника? Чтобы Чертёжник нарисовал домик, хорошо бы написать алгоритмы рисования комнаты и крыши. Итак, алгоритм рисования одного домика можно написать как – “алг домик”, табл. 1. Команды“комната” и “крыша” в алгоритме “домик” – команды обращения к вспомогательным, ещё не написанным алгоритмам. Необходимо разработать эти алгоритмы. Алгоритмы “комната”, “крыша” и “обход” легко написать, это элементарные алгоритмы (программы). Алгоритм “комната” имеет вид “алг комната”, табл. 1. Алгоритм “крыша” имеет вид “алг крыша”, табл. 1. Алгоритм “обход” имеет вид “алг обход”, табл. 1. Поставленная задача решена, для её решения использовалась технология проектирования алгоритма «сверху вниз».

Пример 2. Написать программу упорядочения элементов данного массива a[1:n] целых чисел по возрастанию, используя сортировку простыми включениями. (Основной этап изучения учебного материала содержательной линии «Алгоритмизация и программирование»).

Замечание: Методы сортировки обычно разделяют на две категории: сортировки массивов и сортировки файлов. Эти два класса сортировок часто называют внутренними и внешними сортировками. Массивы располагаются во «внутренней» (оперативной) памяти компьютера, для этой памяти характерен быстрый произвольный доступ. Файлы хранятся в более медленной, но более вместительной «внешней» памяти, т. е. на запоминающих устройствах.

Известные алгоритмы сортировок данных, расположенных в оперативной памяти, чрезвычайно разнообразны. Их анализ очень полезен с точки зрения обучения, так как в них используются практически все универсальные приемы конструирования алгоритмов любой сложности. По словам Н. Вирта, «создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки». Интересен этот класс алгоритмов еще и тем, что на нем наглядно демонстрируются богатейшие возможности программирования: насколько разными путями можно прийти к одной цели – получению упорядоченного массива. На множестве алгоритмов сортировки становится понятной необходимость оценки качества алгоритма, критериями которого являются экономии памяти и увеличение быстродействия. Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировок – облегчить последующий поиск элементов в отсортированном массиве. Упорядоченные объекты содержатся в телефонных книгах, в ведомостях подоходных налогов, в оглавлениях, в библиотеках, в словарях, на складах, да и почти всюду, где их нужно разыскивать.

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять в этом же массиве. Классификацию алгоритмов сортировки проводят в соответствии с их эффективностью. Удобная мера эффективности получается при подсчете числа C – необходимых сравнений элементов и числа M – числа пересылок элементов. Эти числа определяются некоторыми функциями от n – числа сортируемых элементов. Хотя хорошие (быстрые) алгоритмы сортировки требуют порядка n×log n сравнений, в школьном предмете информатики желательно рассмотреть несколько несложных и очевидных способов сортировки, называемых простыми сортировками, которые требуют порядка n² сравнений элементов. Необходимость рассмотрения простых методов сортировок массивов, прежде чем перейти к более быстрым сортировкам, обусловлена следующими важными причинами:

1. Простые методы особенно хорошо подходят для разъяснения принципов работы сортировок. Программы, основанные на этих методах, легки для понимания и компактны в написании.

2. Хотя быстрые методы сортировок требуют меньшего числа операций, но при достаточно малых n простые методы работают быстрее.

Простые сортировки массивов можно разбить на три основных класса, в зависимости от лежащего в их основе приема сортировки:

1. Сортировки простыми включениями.

2. Сортировки простым выбором.

3. Сортировки простым обменом.

Решение. Механизм сортировки простыми включениями можно описать так. Элементы массива условно разделим на две последовательности: a[1], a[2], … , a[i-1] – последовательность элементов уже отсортированную и не отсортированную последовательность a[i], a[i+1], … , a[n]. Чтобы отсортировать элементы второй последовательности поступают следующим образом, берут i-ый элемент этой последовательности и вставляют его на нужное место в отсортированную первую последовательность, i изменяется от 2 до n. Вставку элемента a[i] на нужное место в отсортированную первую последовательность производят тремя шагами.

1. Найди k – позицию (место) дляэлемента массиваa[i] в упорядоченной последовательности элементов.

2. Сдвинь элементы a[k], a[k+1], … , a[i-1] вправо на одну позицию.

3. Поставь элемент a[i] на k место в отсортированной последовательности элементов.

Эту последовательность шагов необходимо повторить n-1 раз при i, изменяющимся от 2 до n. В начале цикла необходимо предусмотреть сохранение a[i], h:=a[i].

Алгоритмы, реализующие первый и второй шаги, оформим как вспомогательные, в основном алгоритме вместо команд алгоритмического языка, описывающих эти шаги, запишем команды обращения к вспомогательным алгоритмам. Аргументами первого вспомогательного алгоритма «алг место …» являются: цел n,i, целтаб a[1:n]. Результатами исполнения алгоритма являются: целтаб a[1:n] и цел k – место a[i] в упорядоченной последовательности целых чисел a[1], a[2], …, a[i-1]. Аргументами второго вспомогательного алгоритма «алг сдвиг вправо …» являются: цел k,n,i, целтаб a[1:n]. Результатом исполнения алгоритма являются: целтаб a[1:n]. Основной алгоритм – «алг сортировка включениями …» приведён в таблице 2. Данные n, i, k, массив a можно описать перед первым алгоритмом как глобальные объекты.

1. Детализируем вспомогательный алгоритм «алг место …». Как найти k, номер a[i] в упорядоченной последовательности целых чисел a[1], a[2], …, a[i-1].

1 способ. Будем сравнивать a[i] по порядку со всеми элементами первой упорядоченной последовательности справа налево, начиная с элемента a[i-1]. Сравнение будем производить пока a[j]>a[i], где j изменяется от i-1 до 1, следовательно, сравнение нужно проводить в цикле. Как только найдётся элемент a[j]<=a[i], то и номер k будет найден, k = j+1. Из цикла в этом случае необходимо выйти. Возможен случай, когда все a[j]>a[i], тогда k = 1, при написании алгоритма эту ситуацию надо запрограммировать. Перед циклом сравнений проведём инициализацию цикла – переменной k присвоим значение 1, а j присвоим значение i-1: k:=1 и j:=i-1.

Условие, при котором цикл будет выполняться, можно записать так: пока k=1 и j>=1. Детализированный вспомогательный алгоритм «алг место …», реализующий эти рассуждения, дан в табл. 2.

Замечание: При программировании поиска места k, когда элемент a[i] нужно ставить на первое место, можно воспользоваться методом «барьера», названным так Н. Виртом. Расширим диапазон индексов исходного массива a[0:n], и перед циклом сравнений, при поиске места для a[i] в упорядоченной последовательности, запишем команду a[0]:=a[i]. Сравнение в этом случае нужно производить пока a[j]>a[i], где j изменяется от i-1 до 0.

2 способ. Первая последовательность элементов массива a[1:n] – a[1], a[2], … , a[i-1] – отсортированная последовательность элементов. Следовательно, поиск места элемента a[i] необходимо проводить в отсортированной последовательности элементов. В этом случае для поиска можно использовать другой алгоритм. Сравним a[i] со средним элементом отсортированной последовательности. Результат сравнения позволит определить либо место элемента a[i], либо в какой половине последовательности следует искать позицию этого элемента. Далее, если позиция не определена, процедуру сравнения со средним элементом выбранной подпоследовательности нужно повторить. Позиция будет определена после проведения не более чем log2 i сравнений. Такой алгоритм поиска элемента в отсортированном массиве называется «бинарным поиском» или «логарифмическим поиском», а сортировка с использованием бинарного поиска места элемента a[i] в отсортированной последовательности называется сортировкой бинарными включениями. Напишем вспомогательный алгоритм «алг место1…», табл. 3.

Обозначим x номер наименьшего элемента упорядоченной последовательности, x:=1, y – номер наибольшего элемента этой последовательности, y:= i-1. Так же будем обозначать соответствующие номера выделяемых её частей (подпоследовательностей). Место включения найдено, если a[x]<=a[i]<a[y]. Итак, найдём номер c равный div(x+y, 2). Сравним элемент a[c] с элементом a[i], если значение элемента a[i]<a[c], то y:=c-1, иначе x:=c+1. Интервал поиска в конце должен быть равен 1 и k:=x. Значение k, это место a[i] в упорядоченной последовательности.

2. Детализируем вспомогательный алгоритм «алг сдвиг вправо…».

Для сдвига элементов упорядоченной последовательности a[k], a[k+1], … , a[i-1] вправо на одну позицию нужно последовательно по одному сдвигать элементы, начиная с конца на одну позицию. Детализированный вспомогательный алгоритм «алг сдвиг вправо…», реализующий этот шаг дан в таблице 2.

3. Алгоритм, реализующий третий шаг, элементарный алгоритм.

Для организации вывода элементов массива после выполнения команд тела основного цикла воспользуемся вспомогательным алгоритмом «алг вывод_элементов массива …». Алгоритм «алг вывод_элементов массива …» дан в таблице 2.

Программа сортировки простыми включениями

на языке Turbo Pascal

Замечание: Программа на VBA для Microsoft Excel, имитирующая механизм исполнения сортировки методом простых включений, представлена в приложении 1.

Примеры проектирования программ (алгоритмов) с использованием технологии «снизу вверх»

Примеры приведены при решении задач 33, стр. 63; 35, стр. 64; при рассмотрении сортировки выбором, стр. 175.