Преимущества и недостатки метода последовательной детализации. Последовательная детализация, сборочный метод. I. Приёмы построения алгоритмов

Суть метода была описана выше. Сначала анализируется исходная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач (рис. 48).
Затем составляются алгоритмы (или программы), начиная с основного алгоритма (основной программы), далее - вспомогательные алгоритмы (подпрограммы) с последовательным углублением уровня, пока не получим алгоритмы, состоящие из простых команд.Вернемся к задаче «Интерпретатор», которая рассматривалась в разд. 3.16. Напомним условие: дана исходная символьная строка, имеющая следующий вид:а
b=На месте а и b стоят десятичные цифры; значком
обозначен один из знаков операций: +, -, *. Нужно, чтобы машина вычислила это выражение и после знака = вывела результат. Операция деления не рассматривается для того, чтобы иметь дело только с целыми числами.Сформулируем требования к программе Interpretator, которые сделают ее более универсальной, чем вариант, рассмотренный в разд. 3.16:1. Операнды а и b могут быть многозначными целыми положительными числами в пределах MaxInt.2. Между элементами строки, а также в начале и в конце могут стоять пробелы.3. Программа осуществляет синтаксический контроль текста. Ограничимся простейшим вариантом контроля: строка должна состоять только из цифр, знаков операций, знака = и пробелов.4. Проводится семантический контроль: строка должна быть построена по схеме а
b =. Ошибка, если какой-то элемент отсутствует или нарушен их порядок.5. Осуществляется контроль диапазона значений операндов и результата (не должны выходить за пределы MaxInt).Уже из перечня требований становится ясно, что программа будет непростой. Составлять ее мы будем, используя метод последовательной детализации. Начнем с того, что представим в самом общем виде алгоритм как линейную последовательность этапов решения задачи:1. Ввод строки.2. Синтаксический контроль (нет ли недопустимых символов?).3. Семантический контроль (правильно ли построено выражение?).4. Выделение операндов. Проверка операндов на допустимый диапазон значений. Перевод в целые числа.5. Выполнение операции. Проверка результата на допустимый диапазон.6. Вывод результата.Этапы 2, 3, 4, 5 будем рассматривать как подзадачи первого уровня, назвав их (и будущие подпрограммы) соответственно Sintax, Semantika, Operand, Calc

Урок: Информатика и ИКТ 9 класс

Учитель: Вафина Лейсан Александровна

Тема урока: Вспомогательные алгоритмы. Метод последовательной детализации и сборочный метод.

Цели:

Знакомство с новыми понятиями: вспомогательный алгоритм, метод пошаговой детализации алгоритма, исполнителем Стрелка;

формирование навыка работы со вспомогательными алгоритмами;

закрепление навыков по составления линейных алгоритмов, алгоритмов с ветвлениями и циклами, работы в группе;

Задачи:

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

развивающая – развитие алгоритмического мышления, памяти, внимания, логического мышления, познавательного интереса, коммуникативной культуры, учебно-познавательной компетенции;

воспитательная – развитие познавательного интереса, способствовать воспитанию в детях милосердия, ответственности, взаимопонимания, взаимоуважения, взаимопомощи и поддержки.

Оборудование и программное обеспечение: презентации PowerPoint . ( )

План урока:

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

Мотивация, целеполагание, постановка проблемы.

Объяснение нового материала.

Закрепление.

Итог урока.

Ход урока

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

Приветствие. Проверка присутствующих. Установление психологического и эмоционального контакта с детьми.

II. Мотивация, целеполагание, постановка проблемы

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

В результате диалога на доске возникает алгоритм :

Алгоритм:

Сесть в лодку двум туристам

Переплыть

Высадить одного туриста

Переплыть

Сесть в лодку одному туристу

Переплыть

Высадить одного туриста

Переплыть

Сесть в лодку одному туристу

Переплыть

Высадиться всем туристам

Какую особенность в этом алгоритме можно отметить?

(Отмечают повторение команд 2-9.)

Очень много времени мы потеряли на запись повторяющихся команд. Как же можно сократить запись данного алгоритма? Ответить мы сможем на данный вопрос после рассмотрения сегодняшней темы урока: «Вспомогательные алгоритмы».

Сегодня мы познакомимся с понятием «вспомогательный алгоритм», рассмотрим правила оформления вспомогательных алгоритмов.

Вопросы урока:

Какие алгоритмы называют вспомогательными?

Как оформляются такие алгоритмические структуры?

III. Объяснение нового материала.

Давайте повторяющиеся действия выведем в отдельный алгоритм, который назовем – Переправа. Посмотрите как будет выглядеть наш алгоритм:

Алгоритм:

Сесть в лодку двум туристам

Выполнить алгоритм Переправа

Переплыть

Высадиться всем туристам

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

Переплыть

Высадить одного туриста

Переплыть

Сесть в лодку одному туристу

Сесть в лодку двум туристам

Выполнить алгоритм Переправа

Переплыть

Высадиться всем туристам

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

IV. Закрепление

У исполнителя Стрелочка допустимые действия:

Нарисовать линию длинной 1 см в направлении стрелки.

Переместиться по направлению стрелки на 1 см, не рисуя линию.

Повернуться на 90º влево вокруг начала стрелки.

Шаг.

Прыжок.

Поворот

Задача. Составьте алгоритм построения изображения Стрелкой:

Алгоритм:
Шаг
Поворот

Поворот

Поворот
Шаг

Поворот
Шаг
Поворот

Поворот

Поворот
Шаг

Поворот
Шаг
Поворот

Поворот

Поворот
Шаг

Поворот

Поворот
Шаг

– будет отмечать начальное положение стрелки на рисунке.

Применим к данному алгоритму теорию вспомогательных алгоритмов.

Определите повторяющийся элемент в алгоритме.

Составьте алгоритм «Ступенька»

Как будет выглядеть основной алгоритм?

Алгоритм Ступенька:
Шаг
Поворот

Поворот

Поворот
Шаг
Поворот
Шаг
Поворот

Поворот

Поворот
Шаг
Основной алгоритм:
Выполнить алгоритм Ступенька
Поворот
Выполнить алгоритм Ступенька

Способ разбиения сложной задачи на несколько простых задач называется последовательной детализацией алгоритма.

V. Итог урока.

Какие вопросы были поставлены перед нами?

Получены ли ответы на поставленные вопросы?

Анализ, контроль, выставление оценок.

Суть метода была описана выше. Сначала анализируется исходная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач (рис. 48).

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

Вернемся к задаче «Интерпретатор», которая рассматривалась в разд. 3.16. Напомним условие: дана исходная символьная строка, имеющая следующий вид:

На месте а и b стоят десятичные цифры; значком

обозначен один из знаков операций: +, -, *. Нужно, чтобы машина вычислила это выражение и после знака = вывела результат. Операция деления не рассматривается для того, чтобы иметь дело только с целыми числами.

Сформулируем требования к программе Interpretator, которые сделают ее более универсальной, чем вариант, рассмотренный в разд. 3.16:

1. Операнды а и b могут быть многозначными целыми положительными числами в пределах MaxInt.

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

3. Программа осуществляет синтаксический контроль текста. Ограничимся простейшим вариантом контроля: строка должна состоять только из цифр, знаков операций, знака = и пробелов.

4. Проводится семантический контроль: строка должна быть построена по схеме а

b =. Ошибка, если какой-то элемент отсутствует или нарушен их порядок.

5. Осуществляется контроль диапазона значений операндов и результата (не должны выходить за пределы MaxInt).

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

1. Ввод строки.

2. Синтаксический контроль (нет ли недопустимых символов?).

3. Семантический контроль (правильно ли построено выражение?).

4. Выделение операндов. Проверка операндов на допустимый диапазон значений. Перевод в целые числа.

5. Выполнение операции. Проверка результата на допустимый диапазон.

6. Вывод результата.

Этапы 2, 3, 4, 5 будем рассматривать как подзадачи первого уровня, назвав их (и будущие подпрограммы) соответственно Sintax, Semantika, Operand, Calc

В свою очередь, для их реализации потребуется решение следующих подзадач: пропуск лишних пробелов (Propusk), преобразование символьной цифры в целое число (Cifra). Кроме того, при выделении операндов понадобится распознавать операнд, превышающий максимально допустимое значение (Error). Обобщая все сказанное в схематической форме, получаем некоторую структуру подзадач. Этой структуре будет соответствовать аналогичная структура программных модулей (рис. 49).

Первый шаг детализации. Сначала наметим все необходимые подпрограммы, указав лишь их заголовки (спецификации). На месте тела подпрограмм запишем поясняющие комментарии (такой вид подпрограммы называется «заглушкой»). Напишем основную часть программы. А потом вернемся к детальному программированию процедур и функций. На первом этапе программирования вместо тела подпрограммы опишем ее назначение в форме комментария. Окончательно объединив тексты подпрограмм с основной программой, получаем рабочий вариант программы Interpretator. Теперь ее можно вводить в компьютер.

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

Ошибки могут быть «языковые», могут быть алгоритмические. Первый тип ошибок, как правило, помогает обнаружить компилятор с Паскаля. Это ошибки, связанные с нарушением правил языка программирования. Их еще называют ошибками времени компиляции, ибо обнаруживаются они именно во время компиляции. Алгоритмические ошибки приводят к различным последствиям. Во-первых, могут возникнуть невыполнимые действия. Например, деление на нуль, корень квадратный из отрицательного числа, выход индекса за границы строки и т.п. Это ошибки времени исполнения. Они приводят к прерыванию выполнения программы. Как правило, имеются системные программные средства, помогающие в поиске таких ошибок.

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

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

Успешное прохождение всех тестов есть необходимое условие правильности программы. Заметим, что при этом оно необязательно является достаточным. Чем сложнее программа, тем труднее построить исчерпывающий план тестирования. Опыт показывает, что даже в «фирменных» программах в процессе эксплуатации обнаруживаются ошибки. Поэтому проблема тестирования программы - очень важная и одновременно очень сложная проблема.

ТЕМА: "ВЕТВЛЕНИЕ И ПОСЛЕДОВАТЕЛЬНАЯ ДЕТАЛИЗАЦИЯ АЛГОРИТМА"

Цели урока:

Образовательные:

1.познакомить учащихся с командой ветвления.

2.показать пример задачи с двухшаговой детализацией.

Воспитательные:

воспитание информационной культуры, внимания, аккуратности, усидчивости.

Развивающие:

1.развитие самоконтроля;

2.развитие познавательных интересов

Тип урока: комбинированный

Вид урока: урок объяснения и первичного закрепления материала

Оборудование: доска, компьютеры, проектор

Учебник: Семакин «Информатика и ИКТ» 9 класс

План урока:

Организационный момент, проверка домашнего задания.

Объяснение нового материала.

Практическая часть.

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

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

Ход урока

Деятельность учителя

Деятельность учащихся

Здравствуйте, ребята! Присаживайтесь! Сегодня мы будем изучать алгоритм ветвления.

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

Команда ветвления

Познакомимся еще с одной командой ГРИС. Она называется командой ветвления. Формат команды ветвления такой:

если <условие>
то <серия 1>
иначе <серия 2>
кв

Служебное слово кв обозначает конец ветвления.

По-прежнему ГРИС может проверять только два условия: «впереди край?» или «впереди не край?». <Серия> - это одна или несколько следующих друг за другом команд. Если <условие> справедливо, то выполняется <серия 1>, в противном случае - <серия 2>.

Давайте изобразим блок-схему.

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

Неполная форма ветвления

В некоторых случаях используется неполная форма команды ветвления

Например:

если впереди край
то поворот
кв

Блок-схема:

Неполная команда ветвления имеет следующий формат:

если <условие>
то <серия>
кв

Здесь <серия> выполняется, если <условие> справедливо.

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

Пример задачи с двухшаговой детализацией

Задача 6. Построить орнамент, состоящий из квадратов, расположенных по краю поля. Исходное положение ГРИС - в верхнем левом углу, направление на юг.

Процедуру, рисующую цепочку квадратов от края до края поля, назовем РЯД. Процедуру, рисующую один квадрат, назовем КВАДРАТ. Сначала напишем основную

программа Орнамент
нач
сделай РЯД
поворот
сделай РЯД
поворот
сделай РЯД
поворот
сделай РЯД
кон

Теперь напишем процедуры РЯД и КВАДРАТ:

В процедуре РЯД в теле цикла содержится неполное ветвление. Структуру такого алгоритма можно назвать так: цикл с вложенным ветвлением.

Процедуры РЯД.

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

Теперь вам известны все команды управления графическим исполнителем. Их можно разделить на три группы: простые команды; команда обращения к процедуре; структурные команды. К третьей группе относятся команды цикла и ветвления.

Приложение 1.

Переходим к практической части нашего урока.

Загружайте файл Ц_1 уровень

Разработайте алгоритм перемещения из точки А в точку Б по прямой с рисованием следа. Расстояние от А до Б заранее неизвестно. Но точно известно, что за точкой Б на расстоянии одной клетки от нее находится стенка. Воспользуйтесь этой стенкой для того чтобы завершить перемещение именно в точке Б: запрыгнув вперед проверяйте нет ли впереди стенки и, если стенки нет, то возвращайтесь и оставляйте след.

Загружайте файл Ц_2 уровень

Разработайте алгоритм перемещения исполнителя из точки А в точку Б с преодолением возникающих на пути трех пар «прыгающих» стенок. След должен быть виден. Используйте процедуру для преодоления одной пары стенок.

Загружайте файл Ц_3 уровень

Приложение 2

Приложение 3

Приложение 4

Подведение итогов урока, выставление отметок.

Домашнее задание п.31,

Приложение 1.

Приложение 2

Приложение 3

Приложение 4

Тип урока: урок закрепления знаний и изучение нового материала.

Вид урока: комбинированный урок (лекция и практика). Цели урока: Общеобразовательные:

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

сформировать навыки разработки алгоритмов с ветвлением в ГРИС «Стрелочка»;

Развивающие:

развитие информационного видения явлений и процессов окружающего мира;

Воспитательные:

воспитание информационной культуры учащихся, внимательность, аккуратность, дисциплинированности, усидчивости;

воспитание познавательного интереса школьников

Структура урока:

I .Организационный момент (2 мин.)

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

Письменный опрос 2 варианта работ

III

Объяснение с помощью презентации

Пример задачи с двух шаговой детализацией

Объяснение с помощью презентации «Демонстрация алгоритма с ветвлением «Орнамент» в среде исполнителя Стрелочка».

V . Итог урока (2 мин.)

VI . Домашнее задание (1 мин.)

Ход урока:

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

Тема урока: “ Ветвление и последовательная детализация ”

Основные темы параграфа:

♦ команда ветвления;
♦ неполная форма ветвления;
♦ пример задачи с двух шаговой детализацией. (слайд 2)

II . Актуализация знаний (5 мин.)

Тест на тему: Циклические алгоритмы

Вариант 1

1.В какой из фигур выполняется проверка условия:

2. Циклический алгоритм это:

нц
шаг
кц

пока впереди не край, повторять
нц
шаг
поворот
кц

нач
шаг
кон

нц
шаг
кц

4. Тело цикла – это:

графический способ описания алгоритма

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

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

5.Нарисовать структуру цикла (блок-схема)

Тест на тему: Циклические алгоритмы

Вариант 2

1.В какой из фигур выполняется процедура:

2. Цикл - это:

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

3. Требуется нарисовать горизонтальную линию через весь экран. Выберите правильную программу:

нач
шаг
кон

нц
шаг
кц

нц

шаг

поворот

кц

пока впереди не край, повторять

нц

шаг

кц

4. Блок-схема – это:

последовательность команд, входящая в алгоритмическую структуру “цикл”.

графический способ описания алгоритма

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

5. Написать программу зацикливание алгоритма.

III . Теоретическая часть (20 мин.)

Команда ветвления

Познакомимся еще с одной командой ГРИС. Она называется командой ветвления. Формат команды ветвления такой:

если <условие>
то <серия 1>
иначе <серия 2>
кв (слайд 3)

Служебное слово кв обозначает конец ветвления.

(слайд 4)

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

Неполная форма ветвления

В некоторых случаях используется неполная форма команды ветвления (рис. 5.13). Например:

если впереди край
то поворот
кв

(слайд 4)

Неполная команда ветвления имеет следующий формат:

если <условие>
то <серия>
кв

Здесь <серия> выполняется, если <условие> справедливо. слайд 5)

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

Пример задачи с двухшаговой детализацией

Задача 6. Построить орнамент, состоящий из квадратов, расположенных по краю поля. Исходное положение ГРИС - в верхнем левом углу, направление на юг (рис. 5.14).

(слайд 6)

Процедуру, рисующую цепочку квадратов от края до края поля, назовем РЯД. Процедуру, рисующую один квадрат, назовем КВАДРАТ. Сначала напишем основную программу.

программа Орнамент
нач
сделай РЯД
поворот
сделай РЯД
поворот
сделай РЯД
поворот
сделай РЯД
кон (слайд 7)

Теперь напишем процедуры РЯД и КВАДРАТ:

(слайд 8)

На рис. 5.15 приведена блок-схема процедуры РЯД.

(слайд 9)

IV . Закрепление знаний (15 мин.)

Проработка алгоритма «Орнамент»

V . Итог урока (2 мин.)

Оценивание работы учеников на уроке.

VI . Домашнее задание (1 мин.)

§31, вопросы. Готовится к контрольной работе (слайд 10)

Вопросы и задания

1. Что такое пошаговая детализация?
2. Из каких команд могут состоять вспомогательные алгоритмы последнего уровня детализации?
3. Какой формат имеет команда ветвления? Какие действия исполнителя она определяет?
4. Чем отличается полное ветвление от неполного?
5. Путем пошаговой детализации составьте программы управления графическим исполнителем для решения следующих задач:
расчертить все поле горизонтальными пунктирными линиями;
нарисовать квадраты во всех четырех углах поля;
расчертить все поле в клетку со стороной, равной шагу.