Начало » Экзамен по информатике » 2007 год » Ответы на билеты 9 класса 2007 год » Билет № 7
Билет № 7
1.
Основные алгоритмические структуры: следование, ветвление, цикл;
изображение на блок-схемах. Разбиение задачи на подзадачи.
Вспомогательные алгоритмы.
Основные виды алгоритмов
(алгоритмических структур):
1. Линейный алгоритм (еще
называют следование);
2. Циклический алгоритм;
3. Разветвляющийся алгоритм;
4. Вспомогательный алгоритм.
Линейный
алгоритм
Линейный алгоритм –
описание действий, которые выполняются однократно в заданном
порядке. Исполнитель выполняет действия последовательно, одно за
другим в том порядке в котором они следуют.
Блок-схема линейного алгоритма:
Циклический
алгоритм
Лучшее качества компьютеров
проявляются не тогда, когда они рассчитывают значения сложных
выражений, а когда многократно, с незначительными изменениями,
повторяют сравнительно простые операции. Даже очень простые расчеты
могут поставить человека в тупик, если их надо повторить тысячи раз,
а повторять операции миллионы раз человек совершенно не способен.
С необходимостью повторяющихся
вычислений программисты сталкиваются постоянно. Например, если надо
подсчитать, сколько раз буква "о" встречается в тексте
необходимо перебрать все буквы. При всей простоте этой программы
исполнить ее человеку очень трудно, а для компьютера это задача на
несколько секунд.
Циклический алгоритм –
описание действий, которые должны повторяться указанное число раз или
пока не выполнено заданное условие.
Перечень повторяющихся действий
называют телом цикла.
Циклические алгоритмы бывают
двух типов:
Циклы со счетчиком, в
которых какие-то действия выполняются определенное число раз;
Циклы с условием, в
которых тело цикла выполняется, в зависимости от какого-либо
условия. Различают циклы с предусловием и постусловием.
Циклы со счетчиком используют
когда заранее известно какое число повторений тела цикла необходимо
выполнить. Например, на уроке физкультуры вы должны пробежать
некоторое количество кругов вокруг стадиона.
В общем случае схема
циклического алгоритма со счетчиком будет выглядеть так:
Для счетчика от нач.
значения до кон. значения выполнить действие.
Часто бывает так, что
необходимо повторить тело цикла, но заранее не известно, какое
количество раз это надо сделать. В таких случаях количество
повторений зависит от некоторого условия. Такие циклы называются
циклы с условием. Циклы в которых сначала проверяется условие, а
затем, возможно, выполняется тело цикла называют циклы с
предусловием. Если условие проверяется после первого выполнения тела
цикла, то циклы называются циклы с постусловием.
Например,
в субботу вечером вы смотрите телевизор. Время от времени
поглядываете на часы и если время меньше полуночи, то продолжаете
смотреть телевизор, если это не так, то вы прекращаете просмотр
телепередач.
В общем случае схема
циклического алгоритма с условием будет выглядеть так:
Пока условие
повторять действие.
При составлении циклических
алгоритмов важно думать о том, чтобы цикл был конечным. Ситуация, при
которой выполнение цикла никогда не заканчивается, называется
зацикливанием.
Разветвляющийся
алгоритм
Во многих случаях требуется,
чтобы при одних условиях выполнялась одна последовательность
действий, а при других – другая.
Если
пошел дождь, то надо открыть зонт.
Если
прозвенел будильник, то надо вставать.
Если
встречу Сашу, то скажу ему …
Если
встречу Сашу, то скажу ему …, иначе зайду к нему сам.
Разветвляющийся алгоритм
- алгоритм, в котором в зависимости от условия выполняется либо одна,
либо другая последовательность действий.
Эти предложения начинаются с
проверки какого-либо условия: пошел дождь, прозвенел будильник,
встретил Сашу… Далее в зависимости мы либо вылиняем какое-либо
действие, либо не выполняем его (или выполняем какое-то другое
действие).
Компьютер тоже в зависимости от
какого-либо условия может выполнять или не выполнять те или иные
действия. Алгоритм, в котором используется условие, получил название
разветвляющегося, так как в зависимости от значения условия
выбираются те или иные действия.
В общем случае схема
разветвляющегося алгоритма будет выглядеть так: «если
условие, то действие 1, иначе действие
2» (Если встречу Сашу, то скажу ему …, иначе
зайду к нему сам.). Так же можно использовать неполную форму:
«если условие, то действие»
(Если встречу Сашу, то скажу ему …). В этом случае не
предусматривается действий на случай невыполнения условия.
Условие – это
высказывание которое может быть либо истинно, либо ложно.
Еще раз обратим внимание, что
существует две формы ветвления – неполная (когда присутствует
только одна ветвь, т.е. в зависимости от истинности условия либо
выполняется, либо не выполняется действие) и полная (когда
присутствуют две ветви, т.е. в зависимости от истинности условия
выполняется либо одно, либо другое действие).
Вспомогательный
алгоритм
Вспомогательный алгоритм
– алгоритм, который можно использовать в других алгоритмах,
указав только его имя.
Вспомогательный алгоритм,
записанный на языке программирования, называется подпрограммой. При
создании средних по размеру программ используется структурное
программирование, идея которого заключается в том, что структура
программы должна отражать структуру решаемой задачи, чтобы алгоритм
решения был ясно виден из исходного текста. Программа разбивается на
множество подпрограмм, каждая из которых выполняет какое-то действие,
предусмотренное исходным заданием.
Комбинируя подпрограммы,
удается сформировать итоговый алгоритм используя блоки кода
(подпрограммы), имеющих определенную смысловую нагрузку. Обращаться к
этим подпрограммам можно по их имени. Очень важная характеристика
подпрограмм - это возможность их повторного использования.
Рассмотрим пример с графическим
исполнителем ГРИС. Пусть требуется составить алгоритм рисования
четырехзначного числа 1919.
Можно составить один длинный
алгоритм, по которому исполнитель шаг за шагом нарисует эти цифры. Но
ведь цифры 1 и 9 повторяются по два раза. Алгоритм можно сократить
используя вспомогательный алгоритм.
Получится
более короткий и понятный алгоритм:
Алгоритм Число «1919»
начало
сделай ЕДИНИЦА
прыжок
сделай ДЕВЯТЬ
прыжок
сделай ЕДИНИЦА
прыжок
сделай ДЕВЯТЬ
конец
Где ЕДИНИЦА и ДЕВЯТЬ
вспомогательные алгоритмы:
Алгоритм ЕДИНИЦА
начало
поворот
шаг
шаг
шаг
шаг
поворот
поворот
прыжок
прыжок
прыжок
прыжок
поворот
конец |
Алгоритм ДЕВЯТЬ
начало
шаг
поворот
шаг
шаг
шаг
шаг
поворот
шаг
поворот
шаг
шаг
поворот
шаг
поворот
поворот
поворот
прыжок
прыжок
поворот
конец |
Метод
последовательной детализации
Использованный нами подход
облегчает программирование сложных задач. Задача разбивается на более
простые подзадачи. Решение каждой оформляется в виде вспомогательного
алгоритма, а основной алгоритм организует связку между ними.
Метод программирования, при
котором сначала пишется основная программа, в ней записываются
обращения к пока еще не составленным подпрограммам, а потом
описываются эти подпрограммы, называется методом последовательной
(пошаговой) детализации. Причем количество шагов детализации
может быть гораздо большим, чем в нашем примере, поскольку сами
подпрограммы могут содержать внутри себя обращения к другим
подпрограммам.
Сборочный
метод
Возможен и другой подход к
построению сложных программ: первоначально составляется множество
подпрограмм, которые могут понадобиться при решении задачи, а затем
пишется основная программа, содержащая обращения к ним. Подпрограммы
могут быть объединены в библиотеку подпрограмм и сохранены в
долговременной памяти компьютера. Такую библиотеку можно постепенно
пополнять новыми подпрограммами.
Например, если для управления
графическим исполнителем создать библиотеку процедур рисования всех
букв и цифр, то программа получения любого текста будет состоять из
команд обращения к библиотечным процедурам.
Описанный метод называется
сборочным программированием.
Часто в литературе по
программированию используется такая терминология: метод
последовательной детализации называют программированием сверху
вниз, а сборочный метод — программированием снизу вверх.
список билетов
|