Меню
ГлавнаяПоломки

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

Метод последовательной детализации.

Информатика 11 класс

МОУ «Школа-лицей №1»

г Алушта

Учитель: Литвинович В.П.


Метод последовательной детализации является одним из основных методов структурного программирования.

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

подзадач.


Суть метода:

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


Пример 1 Вычислить площадь выпуклого N- угольника, заданного координатами своих вершин.

Найти площадь выпуклого многоугольника:

Площадь многоугольника

определяется, как сумма

площадей N-2 треугольников.

S- треугольника определяется:

по формуле Герона

S =√(p(p-a)(p-b)(p-c)


Первый шаг детализации Стороны треугольника определяются по теореме Пифагора: Исходные данные, координаты вершин треугольника можно задать с помощью массива:

Организация данных


Второй шаг детализации: Запрограммируем процедуру Treugolnik. В разделе подпрограмм этой процедуры запишем лишь интерфейс подпрограммы Line, создав функцию.


Третий шаг детализации Запрограммируем функцию Line. Координаты концов отрезка задаем параметрами: x a, Y a –первая точка, x b, У b – вторая.

Собираем все проделанные шаги и составляем программу:

………………………………………………………………………………………… ..



Применение метода последовательной детализации

  • Над большим программным проектом работает несколько специалистов.
  • Руководитель группы проектирует многоуровневую структуру алгоритма и составляет основную программу, а написание подпрограмм поручает другим программистам.
  • Программистам необходимо договорится об интерфейсе подпрограмм: именах, параметрах.
  • Внутренне устройство подпрограммы работа программиста
  • Большие проекты подпрограмм объединяются в МОДУЛИ.

Домашнее задание. § 2.2.11 чит. Запомнить …


Практическая работа № 6. Проверить работу программы N ugolnik

Задать N = 4

Вычислить площадь квадрата с длинами сторон равными 2 и координатами вершин:

Получить результат.

Суть метода была описана выше. Сначала анализируется исходная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач (рис. 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

«Выполнение алгоритмов компьютером» - Формальный исполнитель Алгоритм и программа Особенности выполнения программы. Какие особенности выполнения программы на ЯМК компьютером? Основные вопросы: Ски. Особенности выполнения программы компьютером, написанной на ЯПВУ? трансляция с ЯПВУ на ЯМК. Этапы выполнения программы. Устройство вывода. Компьютер.

«Алгоритмы в информатике» - Действие N. Желаю успехов в изучении ИНФОРМАТИКИ. Разветвляющийся алгоритм. Вывод результата. Ввод исходных данных. Хорошо понял тему и хорошо поработал на уроке. Какой алгоритм называется линейным? Указание на начало и конец алгоритма. Типы алгоритмов. Виды алгоритмов. Много нужно работать над данной темой.

«Свойства и виды алгоритмов» - Циклическая алгоритмическая конструкция, в которой условие поставлено в начале цикла. Начало, конец алгоритма. Виды алгоритмов. Графический способ описания алгоритма (блок-схема). Выполняемое действие. Последовательность выполнения действий. Линейный алгоритм. Неполная форма разветвленного алгоритма.

«Алгоритмы действий» - Как необходимо описать алгоритм? Чтобы выполнить некоторое дело, вы сначала продумываете по­следовательность действий. При переводе на латынь имя автора писали так: Algorithmi [алгоритми]. Зажечь газ. Алгоритмы в нашей жизни. Любой алгоритм можно изобразить графически или описать словами. Откуда произошло слово «алгоритм».

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

«Алгоритм и его формальное исполнение» - Запись алгоритма в виде блок-схемы. В качестве объекта возьмем текст. Развитие языков программирования. Кодирование. Алгоритмы состоят из отдельных команд. Алгоритм должен быть понятен. Основы алгоритмизации. Публикация или передача заказчику результата работы. Запись алгоритма. Проектирование «сверху вниз».

Всего в теме 31 презентация

При после­дов-й детализации сначала строится осн-й алгоритм, а за­тем в него вносятся обращения к вспом-м алгоритмам первого уровня. После этого сост-ся вспомог-е алгоритмы первого уровня, в кот-х могут присутствовать обращения к вспомога-м алгоритмам второго уровня, и т.д. Вспомог-е алго­ритмы самого нижнего уровня состоят только из простых команд. Метод последов-й детализации прим-ся в любом кон­струировании сложных объектов. Это естественная логическая послед-ть мышления констр-ра: постеп-е углубление в детали. Методика послед-й детализации позволяет организовать работу коллектива программ-в над сложным проектом. Сначала анализируется исход­ная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач.

Затем сост-ся алгоритмы (или программы), начиная с ос­н-го алгоритма (основной программы), далее - вспомогатель­ные алгоритмы (подпр-мы) с послед-м углублением Уровня, пока не получим алгоритмы, состоящие из простых команд. Задача. Условие: дана исходная символьная строка, имеющая следующий вид: a Å b = На месте а и b стоят десятичные цифры; значком Å обозначен один из знаков операций:*,-, *. Нужно, чтобы машина вычис­лила это выражение и после знака = вывела рез-т. Операнды а и b могут быть многозначными целыми положи­тельными числами в пределах Maxlnt. Между элементами строки, а также в начале и в конце мои стоять пробелы. Прог-ма осуществляет синтаксический контроль текста. Ограничимся простейшим вариантом контроля: строка должна состоять только из цифр, знаков операций, знака = и пробела. Проводится семантический контроль: строка должна быть построена по схеме a Å b = . Ошибка, если какой-то элемент отсутствует или нарушен их порядок. Осуществляется контроль диапазона значений операндов и результата (не должны выходить за пределы Maxint). Уже из перечня требований становится ясно, что программа будет непростой. Составлять ее мы будем, используя метод после­д-й детализации. Начнем с того, что представим в самом общем виде алгоритм как линейную послед-ть этапов решения задачи: Ввод строки. Синтаксический контроль (нет ли недопустимых символов?). Семантический контроль (правильно ли построено выраже­ние?). Выделение операндов. Проверка операндов на допустимый диапазон зн-й. Перевод в целые числа. Вып-е операции. Проверка рез-та на допустимый диапазон. Вывод рез-та. Этапы 2, 3, 4, 5 будем рассматривать как подзадачи первого уровня, назвав их (и будущие подпрограммы) соответственно Sintax, Semantika, Operand, Calc. В свою очередь, для их реализации потребуется реш-е следующих подзадач: пропуск лиш­них пробелов (propusk), преобраз-е симв-й цифры в целое число (cifra). Кроме того, при выделении операндов понадобится распознавать операнд, превышающий максимально допустимое значение (Error). Первый шаг детализации. Сначала наметим все необходимые подрог-мы, указав лишь их заголовки (спецификации). На месте тела подпрограмм запишем поясняющие комментарии. Напишем осн-ю часть прогр-ы. А потом вернемся к детальному программ-ю процедур и ф-й. Второй шаг детализации. Сост-е подрог-м. Окончательно объединив тексты подпрограмм с основной прогр-й, получаем рабочий вариант программы Interpolator.

Основные алгоритмические структуры: следование, ветвление, цикл; изображение на блок-схемах. Разбиение задачи на подзадачи. Вспомогательные алгоритмы.

Основные виды алгоритмов (алгоритмических структур):

1. Линейный алгоритм (еще называют следование);

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

3. Разветвляющийся алгоритм;

4. Вспомогательный алгоритм.

Линейный алгоритм

Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке в котором они следуют.

Блок-схема линейного алгоритма:

Циклический алгоритм

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

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

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

Перечень повторяющихся действий называют телом цикла .

Циклические алгоритмы бывают двух типов:

  • Циклы со счетчиком , в которых какие-то действия выполняются определенное число раз;
  • Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.

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



В общем случае схема циклического алгоритма со счетчиком будет выглядеть так:

Для счетчика от нач. значения до кон. значения выполнить действие .

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

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

В общем случае схема циклического алгоритма с условием будет выглядеть так:

Пока условие повторять действие .

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

Разветвляющийся алгоритм

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

Если пошел дождь, то надо открыть зонт.

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

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

Эти предложения начинаются с проверки какого-либо условия: пошел дождь, прозвенел будильник, встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо действие, либо не выполняем его (или выполняем какое-то другое действие).

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

В общем случае схема разветвляющегося алгоритма будет выглядеть так: «если условие , то действие 1 , иначе действие 2 » (Если встречу Сашу, то скажу ему …, иначе зайду к нему сам. ). Так же можно использовать неполную форму: «если условие , то действие » (Если встречу Сашу, то скажу ему … ). В этом случае не предусматривается действий на случай невыполнения условия.

Условие – это высказывание которое может быть либо истинно, либо ложно.

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

Вспомогательный алгоритм

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

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

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

Рассмотрим пример с графическим исполнителем ГРИС. Пусть требуется составить алгоритм рисования четырехзначного числа 1919.

Можно составить один длинный алгоритм, по которому исполнитель шаг за шагом нарисует эти цифры. Но ведь цифры 1 и 9 повторяются по два раза. Алгоритм можно сократить используя вспомогательный алгоритм.

Получится более короткий и понятный алгоритм:

Алгоритм Число «1919»
начало
сделай ЕДИНИЦА
прыжок
сделай ДЕВЯТЬ
прыжок
сделай ЕДИНИЦА
прыжок
сделай ДЕВЯТЬ
конец

Где ЕДИНИЦА и ДЕВЯТЬ вспомогательные алгоритмы:

Метод последовательной детализации

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

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

Сборочный метод

Возможен и другой подход к построению сложных программ: первоначально составляется множество подпрограмм, которые могут понадобиться при решении задачи, а затем пишется основная программа, содержащая обращения к ним. Подпрограммы могут быть объединены в библиотеку подпрограмм и сохранены в долговременной памяти компьютера. Такую библиотеку можно постепенно пополнять новыми подпрограммами.

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

Описанный метод называется сборочным программированием .

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