Учебное пособие 80053

ФГБОУ ВО «Воронежский государственный технический университет»

Кафедра систем информационной безопасности

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

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

10.05.01«Компьютерная безопасность», 10.05.02 «Информационная безопасность телекоммуникационных систем»

очной формы обучения

Воронеж 2017

один и тот же результат, т.е. результат однозначно определяется исходными данными (на это свойство указывается в определении 3);

3)результативность. Свойство результативности означает, что алгоритм должен выдавать результат за конечное число шагов. О том, что число шагов должно быть конечным говорится в определениях 3 и 4;

4)массовость. В определениях 1, 2, 3 говорится о некоторых классах задач (входных экземплярах задачи, варьируемых начальных данных) на которых алгоритм должен работать алгоритм. Это означает, что набор исходных данных, на которых алгоритм должен выдавать верное решение, заранее ограничен;

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

Задание 1

Изучите ГОСТ 19.701-90 ЕСПД. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения.

Задание 2

Разработайте схему алгоритма следующей задачи об автомате и лабиринте.

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

Автомат, который не видит перед собой, может осуществить следующие элементарные действия:

•продвинуться на шаг вперед;

•повернуться на 900 (налево или направо);

2

• узнать, не натолкнется ли он при следующем шаге на стену;

• проверить, вышел ли он из лабиринта (уловив поток свежего воздуха).

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

Задача

а) Какие правила должен применять автомат, чтобы пройти от входа лабиринта до выхода из него?

б) Эти правила необходимо записать кратко, но так, чтобы они допускали только одну интерпретацию.

Решение

а) Среди возможных решений следующий вариант является одним из самых простых:

состояние 1 Автомат продвигается на ОДИН шаг (в первый - раз этот шаг необходим, чтобы войти в лабиринт) и переходит в состояние 2.

состояние 2 Автомат осуществляет проверку: вышел ли он из лабиринта?

• если да то задача закончена и автомат останавливается,

• если нет, то он переходит в состояние 3. состояние 3 Автомат делает поворот направо и пере-

ходит в состояние 4.

состояние 4 Автомат осуществляет проверку: не стена ли перед ним?

•если нет, то он переходит в состояние 1,

•если да, то он переходит в состояние 5. состояние 5 Автомат делает поворот налево, затем пе-

реходит в состояние 4.

Начиная с рис. 1.1 проследим, как автомат выйдет из лабиринта.

3

Он входит в лабиринт, делает поворот направо (состояние 3), обнаруживает перед собой стену (состояние 4), делает поворот налево (состояние 5), продвигается на один шаг (состояние 1) и т. д. до тех пор, пока не найдет проход, позволяющий ему войти в коридор В. Там он поворачивает направо (состояние 3) и продолжает свой путь по коридору В, пока не натолкнется на стену (рис. 1.2).

Оказавшись вблизи В, автомат обнаруживает стену справа (состояния 3, 4, 5); затем находит ее перед собой (состояние 4), поворачивается снова налево (состояние 5), вновь обнаруживает стену (состояние 4), совершает еще один поворот налево, и теперь может снова продвигаться (ему приходится возвращаться). Наконец, он находит проход, который ведет в коридор С, и процесс продолжается.

Этот метод представляется вполне удовлетворитель-

ным.

б) Теперь остается сформулировать этот метод в лаконичной форме – составить схему алгоритма.

Рис. 1.1. Пример лабиринта без кольцевых коридоров

4

5.Как на схемах изображаются вложенные циклы?

6.Как на схемах изображаются комментарии?

7.Как схему алгоритма (программы) размещают на нескольких листах?

8.Как в схемах алгоритмов (программ) используют линии и линии со стрелками?

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 2 РАЗРАБОТКА РЕКУРСИВНЫХ ПРОГРАММ

Цель практического занятия Изучить механизм выполнения рекурсивных подпро-

грамм, освоить их разработку, в том числе особенности их отладки в среде разработки.

Теоретические сведения

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

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

Рекурсию целесообразно использовать в следующих случаях:

1)когда вычисления являются рекурсивными в силу своей природы;

2)когда обрабатываются данные с рекурсивной структурой. Примером рекурсивно определяемых структур являются деревья. Деревья используются как для упрощения

6

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

3) когда рекурсия позволяет строить компактные программы (иногда их легче писать и понимать).

Недостаток рекурсивных программ – они медленнее выполняются и сложнее в отладке, чем нерекурсивные.

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

N! = N* (N- 1)!, для N > 1, причем 0! = 1.

Рекурсивная программа вычисления факториала представлена ниже.

int fact_r(int n){

if (n <= 1)

return 1;

else

return n * fact_r(n - 1);

}

Здесь вычисления в конце концов завершатся, поскольку после серии рекурсивных вызовов при n = 1 выполнится основная ветвь условного оператора. Такое условие называют условием выхода из рекурсии.

Правила построения рекурсивных подпрограмм:

1)рекурсивная подпрограмма должна иметь хотя бы одну терминальную ветвь, переход на которую должен осуществляться в зависимости от некоторого условия (условия выхода);

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

7

Задание 1

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

int gcd(int m, int n)

{

Int l, lr;

if (n == 0) return m;

l = m % n;

lr = gcd(n, m % n) ;

return lr;

}

Подберите пару чисел (например, 63 и 90), чтобы рекурсивный вызов сработал несколько раз. В среде отладки установите контрольную точку и посмотрите как изменяются значения переменных, параметры и возвращаемое значение функции gcd. Просмотрите стек вызовов функции в сответствующем окне среды разработки.

Задание 2

Напишите и отладьте рекурсивную программу суммирования массива чисел.

Контрольные вопросы

1. В каких случаях целесообразно использовать рекур-

сию?

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

3.Назовите достоинства и недостатки рекурсивных про-

грамм.

8