Формирование задержки с помощью таймера

Методические указания к практическому занятию № 33

Тема: «Рекурсия»

Количество часов: 2.

Цели:

- обучающая: изучить рекурсивные методы, написать программу с использованием рекурсии; научить анализировать, выделять главное, существенное при решении задачи, самостоятельно работать;

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

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

Задания:

1. Общие понятия.

2. Формирование задержки с помощью таймера.

3. Практическое задание.

Выводы: выполнение практической работы способствует формированию практических навыков по созданию прикладных приложений, содержащих рекурсию.

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ:

Общие понятия

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

Из курса математики известно, что 0! = 1! = 1, n! = 1*2*3...*n. С другой стороны n! = (n - 1)!* n. Таким образом, известны два частных случая параметра n, а именно n = 0 и n = 1, при которых мы без каких-либо дополнительных вычислений можем определить значение факториала. Во всех остальных случаях, то есть для n > 1, значение факториала может быть вычислено через значение факториала для параметра n - 1. Таким образом, рекурсивный метод будет иметь вид:

Рассмотрим работу описанного выше рекурсивного метода для n = 3.

Первый вызов метода осуществляется из основной программы, в нашем случае командой f = F(3). Этап вхождения в рекурсию обозначим стрелками с подписью «шаг». Он продолжается до тех пор, пока значение переменной n не становится равным 1. После этого начинается выход из рекурсии (стрелки с подписью «возврат»). В результате вычислений получается, что F(3) = 3 * 2 * 1 (рис.1).

Рисунок 1 - Структура рекурсивных вызовов

 

Рассмотренный вид рекурсии называют прямой. Метод с прямой рекурсией обычно содержит следующую структуру:

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

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

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

Рассмотрим пример кода для создания набора самоподобных структур. В нашем случае это будет набор увеличивающихся квадратов (рис. 2).

Рисунок 2 – Набор квадратов

 

При проектировании данной программы были созданы два метода:

Координаты левого верхнего угла всех прямоугольников неизменны и находятся в точке (0, 0). Поэтому в параметрах метода MyDraw достаточно передавать x и y для правого нижнего угла. Также в параметрах передается N, значение которой определяет текущую вложенность рекурсии (сколько вызовов рекурсии еще будет).

 

Формирование задержки с помощью таймера

Графические конструкции иногда требуется рассматривать динамически в процессе их построения. Поэтому зачастую используется такая схема вывода графики:

1. Вывод графического элемента.

2. Задержка на n миллисекунд.

3. Повторение 1 и 2 этапа до вывода всех графических элементов.

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

Идея данного подхода заключается в организации бесконечного цикла, который будет проверять значение некого флага. Однако значение флага может измениться при наступлении события Tick таймера, то есть через заданный в таймере промежуток времени. Однако бесконечный цикл, описанный выше, останется бесконечным, и программа просто зависнет. В чем же дело? Дело в том, что при такой организации цикла программа не может опросить очередь сообщений, в которое и будет поступать, в том числе, и событие Tick от таймера. Тем самым мы не попадем никогда в обработчик события timer1_Tick_1. Чтобы решить данную проблему, надо в теле цикла написать Application.DoEvents(), что фактически будет заставлять приложение опрашивать очередь сообщений и в свою очередь приведет к срабатыванию обработчика события timer1_Tick_1.

Практическое задание

Задание 1. Разработайте приложение, строящее ряд увеличивающихся квадратов (рис. 2).