Конец
Каждый блок может содержать в себе как простую команду, так и сложную структуру, но обязательно должен иметь один вход и один выход.
Ветвление - алгоритмическая альтернатива. С помощью этой команды, которую еще называют развилкой, осуществляется выбор одного из двух возможных действий в зависимости от условия. После завершения команды происходит выход на общее продолжение:
На псевдокоде эта команда в общем виде записывается так:
если <условие>
то <действие 1>
иначе <действие 2>
Действия, указанные после служебных слов то ииначе , могут быть простыми или составными командами. При исполнении команды ветвления выполняется только одно из действий: если условие соблюдено, то выполняется действие1, в противном случае – действие2.
Команда ветвления может использоваться в сокращенной форме (коррекция)
, когда в случае несоблюдения условия никакое действие не выполняется. На псевдокоде коррекция записывается так:
если <условие>
то <действие >
Команда повторения (цикл). Большинство алгоритмов содержат серии многократно повторяемых команд. Если такие команды записывать в виде составной команды следования, то каждую повторяемую команду пришлось бы выписывать ровно столько раз, сколько раз она повторяется. Но это очень неэкономный способ записи. Поэтому для обозначения многократно повторяемых действий используют специальную конструкцию, называемую циклом.
Составная команда цикла, называемая также командой повторения, содержит условие, которое используется для определения количества повторений. Рассмотрим три типа команды повторения.
Команда повторения с предусловием записывается на псевдокоде следующим образом:
пока <условие >
повторять <действие>
Под действием, как и прежде, понимается простая или составная команда. Исполнение такой команды повторения состоит в том, что сначала проверяется условие (отсюда и название – цикл с предусловием), и если оно соблюдено, то выполняется команда, записанная после служебного слова повторять. После этого снова проверяется условие. Выполнение цикла завершается, когда условие перестает соблюдаться. Для этого необходимо, чтобы команда, выполняемая в цикле, влияла на условие.
Запись команды повторения с предусловием на языке блок-схем выглядит так:
 |
Команда повторения с постусловием выполняется аналогично, только условие проверяется после выполнения команды, а повторение выполнения команды происходит в том случае, когда условие не соблюдено, т.е. повторение производится до соблюдения условия (поэтому этот тип цикла называют также циклом “до"). На псевдокоде и языке блок-схем цикл с постусловием записывается следующим образом:
повторять
действие
до условие
Под действием, как и прежде, понимается простая или составная команда.
Цикл с параметром (известным количеством повторений)
Для
параметр:= N1 до
N2 делать
действие
N1, N2 – выражения, определяющие соответственно начальное и конечное значения параметра цикла, N3 –шаг изменения параметра цикла.
Если N1< N2, то N3 >0.
Если N1> N2, то N3 <0.
Теоретически необходимым и достаточным является лишь первый тип цикла - цикл с предусловием . Любой циклический алгоритм можно построить с его помощью. Это более общий вариант цикла, чем цикл-до и цикл с параметром. Но, в ряде случаев применение цикла-до и цикла с параметром оказывается более удобным.
Структурный подход требует соблюдения стандарта в изображении блок-схем алгоритмов. Чертить их нужно так, как это делалось во всех приведенных примерах. Каждая базовая структура должна иметь один вход и один выход . Нестандартно изображенная блок-схема плохо читается, теряется наглядность и семантика алгоритма.
Чаще всего алгоритм содержит комбинации базовых команд, соединенных между собой. Соединяться эти структуры могут двумя способами: последовательным и вложенным . Эта ситуация аналогична той, которая наблюдается в электротехнике, где любая сколь угодно сложная электрическая цепь может быть разложена на последовательно и параллельно соединенные участки.
Если блок, составляющий тело цикла, сам является циклической структурой, то, значит, имеют место вложенные циклы. В свою очередь, внутренний цикл может иметь внутри себя еще один цикл и т.д. В связи с этим вводится представление о глубине вложенности циклов. Точно так же и ветвления могут быть вложенными друг в друга.
Иногда в литературе структурное программирование называют программированием без goto. Действительно, при таком подходе нет места безусловному переходу.
Неоправданное использование в программах оператора безусловного перехода goto лишает ее структурности, а значит, всех связанных с этим положительных свойств: прозрачности и надежности алгоритма. Хотя во всех процедурных языках программирования этот оператор присутствует, однако, придерживаясь структурного подхода, его употребления следует избегать.
Языки программирования Паскаль и Си называют языками структурного программирования. В них есть все необходимые управляющие конструкции для структурного построения программы. Наглядность такому построению придает структуризация внешнего вида текста программы. Основной используемый для этого прием - сдвиги строк, которые должны подчиняться следующим правилам:
Конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);
Вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.
Структурная методика алгоритмизации - это не только форма описания алгоритма, но это еще и способ мышления программиста. Создавая алгоритм, нужно стремиться составлять его из стандартных структур.
Еще одним важнейшим технологическим приемом структурного программирования является декомпозиция решаемой задачи на подзадачи - разбиение задачи на более простые части исходной задачи с точки зрения программирования.
Алгоритмы решения таких подзадач называются вспомогательными алгоритмами. В связи с этим возможны два пути в построении алгоритма:
"сверху вниз" – сначала строится основной алгоритм, затем вспомогательные алгоритмы;
"снизу вверх" – сначала составляются вспомогательные алгоритмы, а затем основной.
Первый подход еще называют методом последовательной детализации , второй - сборочным методом.
Сборочный метод предполагает накопление и использование библиотек вспомогательных алгоритмов, реализованных в языках программирования в виде подпрограмм, процедур, функций.
При последовательной детализации сначала строится основной алгоритм, а затем в него вносятся обращения к вспомогательным алгоритмам первого уровня. После этого составляются вспомогательные алгоритмы первого уровня, в которых могут присутствовать обращения к вспомогательным алгоритмам второго уровня, и т. д. Вспомогательные алгоритмы самого нижнего уровня состоят только из простых команд.
Метод последовательной детализации применяется в любом конструировании сложных объектов. Это естественная логическая последовательность мышления конструктора: постепенное углубление в детали. Достаточно сложный алгоритм другим способом построить практически невозможно.
Таким образом, методику пошаговой детализации можно представить в виде схемы:
Сначала анализируется исходная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач.
Затем составляются алгоритмы (или программы), начиная с основного алгоритма (основной программы), далее - вспомогательные алгоритмы (подпрограммы) с последовательным углублением уровня, пока не получим алгоритмы, состоящие из простых команд.
Методика последовательной детализации позволяет организовать работу коллектива программистов над сложным проектом. Например, руководитель группы строит основной алгоритм, а разработку вспомогательных алгоритмов и написание соответствующих подпрограмм поручает своим сотрудникам. Участники группы должны лишь договориться об интерфейсе (т. е. взаимосвязи) между разрабатываемыми программными модулями, а внутренняя организация программы - личное дело программиста.
Отладка и тестирование программы. Никогда нельзя быть уверенным, что написанная программа будет верной (хотя такое и возможно, но с усложнением программы становится все менее вероятным). До окончательного рабочего состояния программа доводится в процессе отладки.
Ошибки могут быть "языковые" – синтаксические, и алгоритмические (логические). Первый тип ошибок, как правило, помогает обнаружить компилятор языка программирования. Это ошибки, связанные с нарушением правил языка программирования. Их еще называют ошибками времени компиляции, ибо обнаруживаются они именно во время компиляции. Сам компилятор в той или иной форме сообщает пользователю о характере ошибки и ее месте в тексте программы. Исправив очередную ошибку, пользователь повторяет компиляцию. Так продолжается до тех пор, пока не будут ликвидированы все ошибки этого уровня.
Алгоритмические ошибки приводят к различным последствиям. Во-первых, могут возникнуть невыполнимые действия. Например, деление на ноль, корень квадратный из отрицательного числа, выход индекса за границы массива и т. п. Это ошибки времени исполнения. Они приводят к прерыванию выполнения программы. Как правило, имеются системные программные средства, помогающие в поиске таких ошибок.
Другая ситуация, когда алгоритмические ошибки не приводят к прерыванию выполнения программы. Программа выполняется до конца, получаются какие-то результаты, но они не являются верными. Для окончательной отладки алгоритма и анализа его правильности производится тестирование.
Тест - это такой вариант решения задачи, для которого заранее известны результаты. Как правило, один тестовый вариант не доказывает правильность программы. Программист должен придумать систему тестов, построить план тестирования для исчерпывающего испытания всей программы.
Качественная программа ни в каком варианте не должна завершаться аварийно .
Тесты программы должны продемонстрировать, что при правильном вводе исходных данных будут всегда получаться верные результаты, а при наличии ошибок (синтаксических, семантических, выхода за диапазон) будут получены соответствующие сообщения.
Успешное прохождение всех тестов есть необходимое условие правильности программы. Заметим, что при этом оно необязательно является достаточным. Чем сложнее программа, тем труднее построить исчерпывающий план тестирования. Опыт показывает, что даже в «фирменных» программах в процессе эксплуатации обнаруживаются ошибки. Поэтому проблема тестирования программы - очень важная и одновременно очень сложная проблема.
Урок: Информатика и ИКТ 9 класс
Учитель: Румянцева Татьяна Александровна
Тема урока: Вспомогательные алгоритмы. Метод последовательной детализации и сборочный метод.
Цели:
Знакомство с новыми понятиями: вспомогательный алгоритм, метод последовательной детализации алгоритма, формирование навыка работы со вспомогательными алгоритмами; закрепление навыков по составления линейных алгоритмов,
Задачи:
учебная – изучить понятия: вспомогательный алгоритм детализация алгоритма, формирование навыков составления основных и вспомогательных алгоритмов;
развивающая – развитие алгоритмического мышления, памяти, внимания, логического мышления, познавательного интереса, коммуникативной культуры, учебно-познавательной компетенции;
воспитательная – развитие познавательного интереса, способствовать воспитанию в детях милосердия, ответственности, взаимопонимания, взаимоуважения, взаимопомощи и поддержки.
План урока:
Организационный момент.
Мотивация, целеполагание, постановка проблемы.
Подготовка мини-проекта
Изложение нового материала.
Закрепление, выполнение практического задания.
Итог урока (рефлексия, выполнение домашнего задания).
Ход урока
I. Организационный момент (1 мин)
Приветствие. Проверка присутствующих. Установление психологического и эмоционального контакта с детьми.
I I. Мотивация, целеполагание, постановка проблемы (5 мин)
Многие из вас отдыхали летом на природе. Давайте вспомним это прекрасное время года попробуем представить себе, как мы с вами совершим поход к реке. Нам предстоит переплыть реку на лодке. Необходим алгоритм переправы через реку, учитывая, что в лодку помещаются только два человека. Давайте попробуем его составить.
(Отмечают повторение команд 2-9.)
Очень много времени мы потеряли на запись повторяющихся команд. Как же можно сократить запись данного алгоритма? Ответить мы сможем на данный вопрос после рассмотрения сегодняшней темы урока: «Вспомогательные алгоритмы». Итак, кто сможет сказать, о чем будет идти речь на сегодняшнем уроке?
Сегодня мы узнаем какие алгоритмы называются вспомогательными и как оформляются такие алгоритмические структуры.
I II . Изучение нового материала. (17 мин)
Работать сегодня вы будете самостоятельно. Поэтому давайте продумаем, какие этапы урока нам нужно не упустить.
Изучение материала
Выполнение практического задания
Оценивание работы
Подготовка д/з
Распределимся на группы и каждая группа будет работать над определенным этапом урока.
Над первым пунктом работают 4 человека. 2 человека готовят презентацию к уроку. Материал для презентации можно взять в моих документах в папке 111 или в тексе учебника (§ 29). 2 человека готовят конспект урока в электронном виде для дальнейшего отправления по электронной почте.
Над вторым пунктом работают 2 человека. Ваша задача выполнить практическую работу с использованием вспомогательного алгоритма. На сайте учебный план урок № 40.
2 человека работают над 3 пунктом. Ваша задача составить оценочную таблицу в MS Exel , в которой будет выставлены оценки по 3 параметрам (работа в мини-группах, выполнение практической работы, выполнение дополнительного задания). Табличный процессор должен вывести среднюю оценку – эта оценка и будет выставлена в журнал.
Домашнее задание будет состоять из 3 пунктов. 1) Повторить теоретический материал; 2) разгадать кроссворд; 3) выполнить письменное задание. Поэтому 2 человека готовят кроссворд по теме «Вспомогательные алгоритмы» в среде MS Exel с использованием примечаний, в которых будут отражены вопросы к кроссворду. Остальные выполняют письменную работу из домашнего задания. Именно они и будут ответственными за проверку домашнего задания у остальных ребят из класса.
1 человек будет выполнять роль секретаря по работе с электронной почтой. Его задача набрать в электронном виде все адреса электронной почты одноклассников в среде MS Word для дальнейшей работы с ними. Необходимо собрать в 1 папку теоретический материал и кроссворд, заархивировать и отправить адресатам.
В это время я пущу листочек в котором необходимо зафиксировать адреса. На подготовку проекта 15 минут. Плодотворной вам работы!
После выполнения задания учитель озвучивает оценку за первый этап работы, после чего оценки заносятся в электронную таблицу.
Резервное задание: составление синквейна на тему «Вспомогательные алгоритмы». Учитель выдает карточки с правилами подготовки.
IV . Изложение нового материала. (5 мин) Учащиеся представляют презентацию по теме.
V . Выполнение практического задания (12 мин) Учащиеся выполняют практическое задание: число 1919 в среде исполнителя «Стрелочка». Ребята ответственные за это задание консультируют остальных, проверяют задания и выставляют оценку в электронную таблицу.
VI . Рефлексия. (5 мин) Вернемся к главному вопросу урока (о переправе). Можем ли мы сократить алгоритм решения поставленной задачи.
Давайте повторяющиеся действия выведем в отдельный алгоритм, который назовем – Переправа. Посмотрите, как будет выглядеть наш алгоритм:
Алгоритм, который мы получили будет называться основным , а алгоритм Переправа будет являться вспомогательным.
Ответьте на вопросы:
Ученик, ответственный за оценку знаний оглашает оценки за урок. Выставить оценки в журнал и записать д/з.
Рефлексия: Думаю, что среди вас нет ни одного человека, который бы не был зарегистрирован в социальных сетях и не использовал репосты, лайки. Репост мы обычно ставим, когда полученная информация не только интересна, но и полезна. Лайк – если информация просто интересна. На доске представлена таблица. Отразите ваше отношение к сегодняшнему уроку. Поставьте +1 в соответствующем столбце репост (интересно и полезно), лайк (интересно), прочерк (урок для меня бесполезен).
Резерв (синквейн). Правила оформления:
Синквейн (от фр. cinquains , англ. cinquain ) - это творческая работа, которая имеет короткую форму стихотворения, состоящего из пяти нерифмованных строк.
Синквейн – это не простое стихотворение, а стихотворение, написанное по следующим правилам:
1 строка – одно существительное, выражающее главную тему cинквейна.
2 строка – два прилагательных, выражающих главную мысль.
3 строка – три глагола, описывающие действия в рамках темы.
4 строка – фраза, несущая определенный смысл.
5 строка – заключение в форме существительного (ассоциация с первым словом).
Составлять cинквейн очень просто и интересно. И к тому же, работа над созданием синквейна развивает образное мышление.
Пример синквейна на тему форумов:
Форум (существительное, выражающее главную тему)
Шумный, интересный (два прилагательных, выражающих главную мысль)
Развлекает, развивает, веселит (три глагола, описывающие действия в рамках темы)
Хорошее место для знакомств (фраза, несущая определенный смысл)
Общение (заключение в форме существительного)
Пример синквейна на тему жизни:
Активная, бурная.
Воспитывает, развивает, учит.
Дает возможность реализовать себя.
Основные алгоритмические структуры: следование, ветвление, цикл; изображение на блок-схемах. Разбиение задачи на подзадачи. Вспомогательные алгоритмы.
Основные виды алгоритмов (алгоритмических структур):
1. Линейный алгоритм (еще называют следование);
2. Циклический алгоритм;
3. Разветвляющийся алгоритм;
4. Вспомогательный алгоритм.
Линейный алгоритм
Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке в котором они следуют.
Блок-схема линейного алгоритма:
Циклический алгоритм
Лучшее качества компьютеров проявляются не тогда, когда они рассчитывают значения сложных выражений, а когда многократно, с незначительными изменениями, повторяют сравнительно простые операции. Даже очень простые расчеты могут поставить человека в тупик, если их надо повторить тысячи раз, а повторять операции миллионы раз человек совершенно не способен.
С необходимостью повторяющихся вычислений программисты сталкиваются постоянно. Например, если надо подсчитать, сколько раз буква "о" встречается в тексте необходимо перебрать все буквы. При всей простоте этой программы исполнить ее человеку очень трудно, а для компьютера это задача на несколько секунд.
Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Перечень повторяющихся действий называют телом цикла .
Циклические алгоритмы бывают двух типов:
Циклы со счетчиком используют когда заранее известно какое число повторений тела цикла необходимо выполнить. Например, на уроке физкультуры вы должны пробежать некоторое количество кругов вокруг стадиона.
В общем случае схема циклического алгоритма со счетчиком будет выглядеть так:
Для счетчика от нач. значения до кон. значения выполнить действие .
Часто бывает так, что необходимо повторить тело цикла, но заранее не известно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Такие циклы называются циклы с условием. Циклы в которых сначала проверяется условие, а затем, возможно, выполняется тело цикла называют циклы с предусловием. Если условие проверяется после первого выполнения тела цикла, то циклы называются циклы с постусловием.
Например, в субботу вечером вы смотрите телевизор. Время от времени поглядываете на часы и если время меньше полуночи, то продолжаете смотреть телевизор, если это не так, то вы прекращаете просмотр телепередач.
В общем случае схема циклического алгоритма с условием будет выглядеть так:
Пока условие повторять действие .
При составлении циклических алгоритмов важно думать о том, чтобы цикл был конечным. Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием .
Разветвляющийся алгоритм
Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других – другая.
Если пошел дождь, то надо открыть зонт.
Если прозвенел будильник, то надо вставать.
Разветвляющийся алгоритм - алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Эти предложения начинаются с проверки какого-либо условия: пошел дождь, прозвенел будильник, встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо действие, либо не выполняем его (или выполняем какое-то другое действие).
Компьютер тоже в зависимости от какого-либо условия может выполнять или не выполнять те или иные действия. Алгоритм, в котором используется условие, получил название разветвляющегося, так как в зависимости от значения условия выбираются те или иные действия.
В общем случае схема разветвляющегося алгоритма будет выглядеть так: «если условие , то действие 1 , иначе действие 2 » (Если встречу Сашу, то скажу ему …, иначе зайду к нему сам. ). Так же можно использовать неполную форму: «если условие , то действие » (Если встречу Сашу, то скажу ему … ). В этом случае не предусматривается действий на случай невыполнения условия.
Условие – это высказывание которое может быть либо истинно, либо ложно.
Еще раз обратим внимание, что существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие).
Вспомогательный алгоритм
Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя.
Вспомогательный алгоритм, записанный на языке программирования, называется подпрограммой. При создании средних по размеру программ используется структурное программирование, идея которого заключается в том, что структура программы должна отражать структуру решаемой задачи, чтобы алгоритм решения был ясно виден из исходного текста. Программа разбивается на множество подпрограмм, каждая из которых выполняет какое-то действие, предусмотренное исходным заданием.
Комбинируя подпрограммы, удается сформировать итоговый алгоритм используя блоки кода (подпрограммы), имеющих определенную смысловую нагрузку. Обращаться к этим подпрограммам можно по их имени. Очень важная характеристика подпрограмм - это возможность их повторного использования.
Рассмотрим пример с графическим исполнителем ГРИС. Пусть требуется составить алгоритм рисования четырехзначного числа 1919.
Можно составить один длинный алгоритм, по которому исполнитель шаг за шагом нарисует эти цифры. Но ведь цифры 1 и 9 повторяются по два раза. Алгоритм можно сократить используя вспомогательный алгоритм.
Получится более короткий и понятный алгоритм:
Алгоритм Число «1919»
начало
сделай ЕДИНИЦА
прыжок
сделай ДЕВЯТЬ
прыжок
сделай ЕДИНИЦА
прыжок
сделай ДЕВЯТЬ
конец
Где ЕДИНИЦА и ДЕВЯТЬ вспомогательные алгоритмы:
Метод последовательной детализации
Использованный нами подход облегчает программирование сложных задач. Задача разбивается на более простые подзадачи. Решение каждой оформляется в виде вспомогательного алгоритма, а основной алгоритм организует связку между ними.
Метод программирования, при котором сначала пишется основная программа, в ней записываются обращения к пока еще не составленным подпрограммам, а потом описываются эти подпрограммы, называется методом последовательной (пошаговой) детализации . Причем количество шагов детализации может быть гораздо большим, чем в нашем примере, поскольку сами подпрограммы могут содержать внутри себя обращения к другим подпрограммам.
Сборочный метод
Возможен и другой подход к построению сложных программ: первоначально составляется множество подпрограмм, которые могут понадобиться при решении задачи, а затем пишется основная программа, содержащая обращения к ним. Подпрограммы могут быть объединены в библиотеку подпрограмм и сохранены в долговременной памяти компьютера. Такую библиотеку можно постепенно пополнять новыми подпрограммами.
Например, если для управления графическим исполнителем создать библиотеку процедур рисования всех букв и цифр, то программа получения любого текста будет состоять из команд обращения к библиотечным процедурам.
Описанный метод называется сборочным программированием .
Часто в литературе по программированию используется такая терминология: метод последовательной детализации называют программированием сверху вниз , а сборочный метод - программированием снизу вверх .
При последов-й детализации сначала строится осн-й алгоритм, а затем в него вносятся обращения к вспом-м алгоритмам первого уровня. После этого сост-ся вспомог-е алгоритмы первого уровня, в кот-х могут присутствовать обращения к вспомога-м алгоритмам второго уровня, и т.д. Вспомог-е алгоритмы самого нижнего уровня состоят только из простых команд. Метод последов-й детализации прим-ся в любом конструировании сложных объектов. Это естественная логическая послед-ть мышления констр-ра: постеп-е углубление в детали. Методика послед-й детализации позволяет организовать работу коллектива программ-в над сложным проектом. Сначала анализируется исходная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач.
Затем сост-ся алгоритмы (или программы), начиная с осн-го алгоритма (основной программы), далее - вспомогательные алгоритмы (подпр-мы) с послед-м углублением Уровня, пока не получим алгоритмы, состоящие из простых команд. Задача. Условие: дана исходная символьная строка, имеющая следующий вид: a Å b = На месте а и b стоят десятичные цифры; значком Å обозначен один из знаков операций:*,-, *. Нужно, чтобы машина вычислила это выражение и после знака = вывела рез-т. Операнды а и b могут быть многозначными целыми положительными числами в пределах Maxlnt. Между элементами строки, а также в начале и в конце мои стоять пробелы. Прог-ма осуществляет синтаксический контроль текста. Ограничимся простейшим вариантом контроля: строка должна состоять только из цифр, знаков операций, знака = и пробела. Проводится семантический контроль: строка должна быть построена по схеме a Å b = . Ошибка, если какой-то элемент отсутствует или нарушен их порядок. Осуществляется контроль диапазона значений операндов и результата (не должны выходить за пределы Maxint). Уже из перечня требований становится ясно, что программа будет непростой. Составлять ее мы будем, используя метод послед-й детализации. Начнем с того, что представим в самом общем виде алгоритм как линейную послед-ть этапов решения задачи: Ввод строки. Синтаксический контроль (нет ли недопустимых символов?). Семантический контроль (правильно ли построено выражение?). Выделение операндов. Проверка операндов на допустимый диапазон зн-й. Перевод в целые числа. Вып-е операции. Проверка рез-та на допустимый диапазон. Вывод рез-та. Этапы 2, 3, 4, 5 будем рассматривать как подзадачи первого уровня, назвав их (и будущие подпрограммы) соответственно Sintax, Semantika, Operand, Calc. В свою очередь, для их реализации потребуется реш-е следующих подзадач: пропуск лишних пробелов (propusk), преобраз-е симв-й цифры в целое число (cifra). Кроме того, при выделении операндов понадобится распознавать операнд, превышающий максимально допустимое значение (Error). Первый шаг детализации. Сначала наметим все необходимые подрог-мы, указав лишь их заголовки (спецификации). На месте тела подпрограмм запишем поясняющие комментарии. Напишем осн-ю часть прогр-ы. А потом вернемся к детальному программ-ю процедур и ф-й. Второй шаг детализации. Сост-е подрог-м. Окончательно объединив тексты подпрограмм с основной прогр-й, получаем рабочий вариант программы Interpolator.
Использованный нами подход облегчает программирование сложных задач. Задача разбивается на более простые подзадачи. Решение каждой оформляется в виде вспомогательного алгоритма, а основной алгоритм организует связку между ними.
Метод программирования, при котором сначала пишется основная программа, в ней записываются обращения к пока еще не составленным подпрограммам, а потом описываются эти подпрограммы, называется методом последовательной (пошаговой) детализации . Причем количество шагов детализации может быть гораздо большим, чем в нашем примере, поскольку сами подпрограммы могут содержать внутри себя обращения к другим подпрограммам.
Сборочный метод
Возможен и другой подход к построению сложных программ: первоначально составляется множество подпрограмм, которые могут понадобиться при решении задачи, а затем пишется основная программа, содержащая обращения к ним. Подпрограммы могут быть объединены в библиотеку подпрограмм и сохранены в долговременной памяти компьютера. Такую библиотеку можно постепенно пополнять новыми подпрограммами.
Например, если для управления графическим исполнителем создать библиотеку процедур рисования всех букв и цифр, то программа получения любого текста будет состоять из команд обращения к библиотечным процедурам.
Описанный метод называется сборочным программированием . Часто в литературе по программированию используется такая терминология: метод последовательной детализации называют программированием сверху вниз , а сборочный метод - программированием снизу вверх .
Коротко о главном
Для упрощения программирования сложных задач используются вспомогательные алгоритмы.
Вспомогательный алгоритм - это алгоритм решения некоторой подзадачи исходной (основной) задачи.
Вспомогательный алгоритм, записанный на языке программирования, называется процедурой.
Вспомогательный алгоритм должен быть описан. После этого в основном алгоритме можно использовать команду обращения к этому вспомогательному алгоритму.
Метод программирования, при котором сначала записывается основной алгоритм, а затем описываются использованные в нем вспомогательные алгоритмы, называется методом последовательной детализации, или программированием сверху вниз. Обратный порядок программирования называется программированием снизу вверх.
Вопросы и задания
1. Что такое основной алгоритм; вспомогательный алгоритм?
2. Чем отличается описание вспомогательного алгоритма от обращения к вспомогательному алгоритму?
3. Каковы правила описания вспомогательных алгоритмов (процедур) для исполнителя ГРИС?
4. Как записывается команда обращения к процедуре в языке исполнителя ГРИС?
5. В чем суть метода последовательной детализации?
6. Что такое программирование снизу вверх; сверху вниз?
7. Используя вспомогательные алгоритмы, запрограммируйте рисование следующих фигур.
ЕК ЦОР: часть 2, глава 5, § 29. ЦОР № 6, 9-12, 14, 15.
Циклические алгоритмы
Основные темы параграфа:
■ команда цикла;
■ цикл в процедуре;
■ блок-схемы алгоритмов;
■ цикл с предусловием.
Команда цикла
Обсудим решение следующей задачи.
Задача 3 . Исходное положение: ГРИС - у левого края поля, направление - на восток. Требуется нарисовать горизонтальную линию через весь экран.
Задачу можно решить, написав 15 раз команду шаг (если поперек поля рисунка 15 шагов). Но есть и более короткий вариант программы. Вот он:
пока впереди не край повторять
Здесь использована команда, которая называется циклом. Формат команды цикла следующий:
пока < условие> повторять
<тело цикла>
Служебное слово нц обозначает начало цикла, кц - конец цикла. Это первая команда из СКИ, которая реализует обратную связь между графическим исполнителем и управляющим им компьютером. Она заключается в том, что проверяется, не вышел ли ГРИС на край поля, не грозит ли ему следующий шаг или прыжок в этом направлении аварией. Проверяемые условия звучат так: «впереди край? » или «впереди не край? ». На что машина получает от исполнителя ответ «да » или «нет ».
В приведенном примере проверяется условие «впереди не край?». Если «да», то делается шаг (т. е. выполняется <тело цикла>). Затем происходит возврат на проверку условия, и всё повторяется. Если проверка условия дает отрицательный результат (т. е. впереди край), то выполнение цикла завершается и исполняется следующая после цикла команда программы.
При программировании цикла важно думать о том, чтобы цикл был конечным. Цикл, записанный выше, конечный. Двигаясь в одном направлении, исполнитель обязательно достигнет края, и на этом выполнение цикла закончится.
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием . Пусть ГРИС находится в середине поля. Исполнение следующего цикла:
пока впереди не край повторять
Поворот
никогда не закончится. ГРИС будет бесконечно рисовать квадратик, так как проверка условия «впереди не край?» всегда будет давать положительный ответ.
Цикл в процедуре
Задача 4. Теперь составим программу, по которой графический исполнитель нарисует прямоугольную рамку по краю поля (рис. 1.6). Исходное положение: ГРИС находится в левом верхнем углу, смотрит на юг.
Рамка состоит из четырех линий, поэтому разумно воспользоваться процедурой, проводящей линию от края до края поля. Опять будем действовать методом последовательной детализации. Напишем сначала основную программу.
Программа проведения линии нами уже рассматривалась. Осталось оформить ее в виде процедуры.
процедура ЛИНИЯ
пока впереди не край повторять
При составлении этой программы использовалась одношаговая детализация в такой последовательности:
Блок-схемы алгоритмов
Начиная с 50-х годов прошлого века, т. е. еще с эпохи ЭВМ первого поколения, программисты стали использовать графические схемы, изображающие алгоритмы, которые получили название блок- схем.
Блок-схема состоит из фигур (блоков), обозначающих действия исполнителя, и стрелок, соединяющих эти блоки и указывающих на последовательность их выполнения. Внутри каждого блока записывается выполняемое действие. Форма блока подсказывает характер действия, которое он обозначает. Для придания наглядности и единообразия схемам алгоритмов все графические элементы стандартизированы.
Посмотрите на рис. 1.7, где показана блок-схема алгоритма рисования рамки. Она состоит из двух частей: блок-схемы основного алгоритма и блок-схемы вспомогательного алгоритма ЛИНИЯ.
Из этих схем понятно назначение блоков различной формы (рис. 1.8).
Цикл с предусловием
Команда цикла изображается не отдельным блоком, а целой структурой, показанной на рис. 1.8. Такую структуру называют циклом с предусловием (так как условие предшествует телу цикла). Есть и другой вариант названия: цикл-пока (пока условие истинно, повторяется выполнение тела цикла).
При решении следующей задачи снова будем использовать метод
последовательной детализации.
Задача 5. Требуется расчертить поле горизонтальными линиями (рис. 1.9). Исходное состояние исполнителя: верхний левый угол, направление - на юг.
В программе для решения этой задачи используется та же процедура ЛИНИЯ. Другая процедура - ВОЗВРАТ - возвращает ГРИС к левому краю поля для рисования следующей линии.
 |
Блок-схемы основного и вспомогательного алгоритмов представлены на рис. 1.10.
Коротко о главном
Для программирования повторяющихся действий применяется команда цикла, которая имеет следующую структуру:
пока <условие> повторять
<тело цикла>
Команда цикла реализует обратную связь между объектом управления и управляющей системой. Проверка условия дает информацию управляющей системе о состоянии объекта управления.
В цикле с предусловием, если проверяемое условие выполняется (истинно), то выполняются команды, составляющие тело цикла. Если условие ложно, то происходит выход из цикла.
При программировании цикла необходимо следить за тем, чтобы не допускалось зацикливание.
Блок-схема - это графический способ описания алгоритма. Блоки обозначают действия исполнителя, а соединяющие их стрелки указывают на последовательность выполнения действий.
Вопросы и задания
1. Что такое цикл? Как записывается команда цикла?
2. Что такое условие цикла? Что такое тело цикла?
3. В каком случае происходит зацикливание алгоритма?
4. Что такое блок-схема?
5. Из каких блоков составляются блок-схемы (как они изображаются и что обозначают)?
6. Что обозначают стрелки на блок-схемах?
7. Составьте программу, переводящую ГРИС в угол поля из любого исходного состояния.
8. Составьте программу рисования прямоугольной рамки вдоль края поля при любом начальном состоянии исполнителя.
ЕК ЦОР: часть 2, глава 5, § 30. ЦОР № 5, 10-13, 16-18.
