Материал: Информатика. Неформальное программирование и основы алгоритмизации вычислительных процессов. Кононов А.Д., Кононов А.А

Контрольные вопросы и упражнения

1.Какие способы описания схем алгоритмов вы знаете?

2.Что такое переменная, ввод, присваивание?

3.Укажите отличие операций ввода и присваивания.

4.Поясните отличие равенства и присваивания.

5.Укажите достоинства и недостатки словесного и формульнословесного описания алгоритмов.

6.В чем достоинства графического метода описания алгоритмов?

7.Дать определение блок-схемы.

8.Перечислите известные блоки и укажите их назначение.

9.Перечислите правила построения алгоритмов на языке блоксхем.

Управляющие структуры

В предыдущем описании алгоритма Евклида мы увидели ряд операций различного характера и назначения. Основными являются:

1)последовательное исполнение – исполнение инструкций алгоритма в том порядке, как они представлены в тексте программы (естественный порядок). Линейный алгоритм – это алгоритм, в котором действия выполняются только один раз и строго в том порядке, в котором они записаны;

2)переход – записывается в виде инструкции «перейти к m», где m – метка, указывающая место в программе, куда необходимо передать управление ходом вычислительного процесса;

3)условное исполнение или разветвление – исполнение одной группы действий при выполнении некоторого условия и другой группы действий при его нарушении. Разветвляющийся алгоритм – это алгоритм, в котором то или иное действие выполняется после анализа условия, который на блок-схеме показывают с помощью логического блока (ромб). Логический блок имеет один вход и два выхода (ветвь «да» и ветвь «нет»). Существуют две формы условного исполнения:

а) полное условное предложение «если А, то В, иначе С». Здесь А – условие, В и С – разные группы действий (рис. 2, а); б) укороченное условное предложение «если А, то В» (рис. 2, б)

15

Рис. 3. Блок-схемы циклов с условием

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

Цикл с параметром. Конструкция цикла выглядит следующим образом.

Для I от M до N шаг H повторяй B,

где I – параметр или индекс цикла, он выполняет роль счетчика, то есть следит за количеством повторений в цикле; M и N – соответственно нижняя и верхняя границы изменения параметра цикла; Н – шаг изменения параметра цикла; В – некоторая группа действий.

В процессе работы параметр I принимает последовательные значения M, M+H, M+2H, …, соответствующие членам арифметической прогрессии.

Контрольные вопросы и упражнения

1.Перечислите и охарактеризуйте основные управляющие структуры.

2.В чем отличие полного условного предложения и укороченного условного предложения?

3.Почему цикл с параметром можно называть циклом типа арифметической прогрессии?

4.Дайте определение линейного вычислительного процесса.

5.Какой процесс называется разветвляющимся?

17

6.Чем определяется выбор ветви вычислений?

7.Какие типы циклов вы знаете?

8.В чем отличие циклов с предусловием и с постусловием?

9.Какие величины задаются в случае цикла с заданным числом повторений?

Типовые задачи программирования

Рассмотрим ряд примеров использования управляющих структур. 1. Тривиальный. Найти наибольшее из двух чисел – max{A,B}. На неформальном уровне алгоритм решения прост

1.Ввод (А,В)

2.Если A≥B, то MAX:=A, иначе MAX:=B

3.Вывод (MAX)

Решение достигается использованием одного полного условного предложения.

2.Усложняем. Найти наибольшее из трех чисел – max{A,B,C}. По методу парных сравнений получим следующий алгоритм

1.Ввод (A,B,C)

2.Если A≥B, то {если A≥C, то MAX :=A, иначе MAX:= C}, иначе {если B≥C, то MAX:=B, иначе MAX:=C}

3.Вывод (M)

Здесь решение получается с использованием трех полных условных предложений, два из которых внутренние и одно внешнее. Графическая иллюстрация решения приведена на рис. 4.

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

18

начало

Нет

A≥C

MAX:=C

Да

MAX:=A

MAX

конец

Рис. 4. Блок-схема нахождения наибольшего из трех чисел

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

1)Ввод (A,B,C)

2)MAX:=A

3)Если MAX<B, то MAX:=B

4)Если MAX<C, то MAX:=C

5)Вывод (MAX)

В пунктах 3,4 применяются укороченные условные предложения. Теперь после второго этапа ячейка MAX «помнит» наибольшее из одного числа, то есть само это число, после третьего шага – наибольшее из двух чисел, после четвертого – наибольшее из трех чисел и т.д.

4.Обобщаем. Пользуясь последней методикой, найдем наибольшее из n чисел – max {ai, i=1,2,…, n}, приведя решение задачи к циклической процедуре с известным числом повторений

1)Ввод (N,A)

2)MAX:=A(1)

19