Теоретический материал
Подпрограммы - процедуры и функции, в языке Delphi служат для выполнения специализированных операций.
Процедура Delphi выполняет требуемые операции, но никаких результатов своих действий не возвращает. Результат - в тех изменениях, которые произошли в программе в процессе выполнения этой процедуры. В частности, процедура может поменять значения переменных, записать новые значения в ячейки компонентов, сделать запись в файл и т.д.
Если процедура относится к объекту (т.е. является его методом), то нужно написать в объявлении имя объекта, а после точки - имя процедуры. Если процедура не относится к объекту, она должна быть описана до начала использования.
Чтобы процедуры можно было использовать до ее реализации, нужно в разделе interface описать её, например:
Если процедура относится к объекту (является её методом), то не имеет значения, где она написана и где вызывается, т.к. классы имеют область описания и она доступна компилятору:
По этому описанию компилятор узнаёт о существовании процедур.
Функция Delphi также позволяет выполнить всё перечисленное, но дополнительно возвращает результат в присвоенном ей самой значении. То есть вызов функции может присутствовать в выражении справа от оператора присваивания. Таким образом, функция - более универсальный объект.
Результат выполнения функции можно записывать в Result или присваивать самому имени функции. Result работает как простая переменная, хотя она нигде не описанаю Она всегда существует в функциях и имеет тип возвращаемого функцией значения.
Рекурсия это возможность подпрограммы в процессе работы обращаться к самой себе. При этом в подпрограмме обязательно должно быть условие, при выполнении которого дальнейшая рекурсия прекращается, иначе подпрограмма зациклится.
Рекурсивные процедуры (recursive procedure) - это процедуры, которые вызывают сами себя.
При работе с рекурсивными алгоритмами следует избегать трех основных опасностей:
бесконечная рекурсия (алгоритм должен иметь надежное условие остановки);
глубокая рекурсия (Если алгоритм вызывает слишком глубокую рекурсию, он исчерпает всю память стека. Сократите использование стека, уменьшив количество переменных, которые размещает процедура, или описывая переменные глобально. Если процедура все еще исчерпывает память стека, перепишите алгоритм без рекурсии с помощью устранения хвостовой рекурсии);
неуместная рекурсия (Обычно это происходит, когда алгоритм, подобный рекурсивному алгоритму подсчета чисел Фибоначчи, много раз вычисляет одни и те же промежуточные значения. Если в вашей программе возникают проблемы подобного рода, попытайтесь переписать алгоритм методом снизу вверх. Если алгоритм нельзя преобразовать с помощью восходящего способа, создайте таблицу соответствия промежуточных значений).
Вычисление факториала - классическая в программировании задача на использование рекурсии.
N! = 1*2* ... *(N-1)*N = N*(N-1)!
Порядок выполнения работы
Изучите теоретический материал.
Разработайте программное приложение для вычисления факториала с применением рекурсии. Для этого используйте компоненты Edit и UpDown. Компонент UpDown имеет полезное свойство Associate. Стоит в Инспекторе объектов присвоить ему (из выпадающего списка) один из находящихся на Форме компонентов Edit, как компонент UpDown пристроится к нему, примет его размеры, и изменение его свойства Position будет отображаться компонентом Edit без всякого программирования
Натуральное число М называется совершенным, если оно равно сумме всех своих делителей, включая 1, но исключая себя. Напечатать все совершенные числа, меньшие заданного числа N. Код с применением циклов переделать на рекурсию
Задача поиска пути между двумя городами
Если несколько городов соединены дорогами, то очевидно, что попасть из одного города в другой можно различными маршрутами. Задача состоит в нахождении всех возможных маршрутов.
Карта дорог между городами может быть изображена в виде графа — набора вершин, означающих города, и ребер, обозначающих дороги
Процесс поиска может быть представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в которую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала, то делаем из этой точки еще шаг. Так как текущая точка может быть соединена с несколькими другими, то нужен какой-то формальный критерий выбора. В простейшем случае можно выбрать точку с наименьшим номером.
Пусть, например, надо найти все возможные пути из точки 1 в точку 5. Согласно принятому правилу, сначала выбираем точку 2. На следующем шаге выясняем, что точка 2 тупиковая, поэтому возвращаемся в точку 1 и делаем шаг в точку 3. Из точки 3 — в точку 4, из 4 — в 6 и из точки 6 — в точку 5. Один маршрут найден. После этого возвращаемся в точку 6 и проверяем, возможен ли шаг в точку, отличную от 5. Так как это возможно, то делаем шаг в точку 7, и затем — в 5. Найден еше один путь. Таким образом, процесс поиска состоит из шагов вперед и возвратов назад. Поиск завершается, если из узла начала движения уже некуда идти.
Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, и так продолжаем до тех пор, пока не достигнем цели.
Таким образом, задача поиска маршрута может рассматриваться как задача выбора очередной точки (города) и поиска оставшейся части маршрута, т. е. имеет место рекурсия.
Граф можно представить двумерным массивом, который назовем тар (карта). Значение элемента массива map[i, j ] — это расстояние между городами i и j, если города соединены дорогой, или ноль, если города не соединены прямой дорогой. Для приведенного графа массив тар можно изобразить в виде таблицы
Содержимое ячейки таблицы на пересечении строки i и столбца j соответствует значению map[i,j].
Помимо массива тар нам потребуются массив road (дорога) и массив incl (от include — включать). В road мы будем записывать номера пройденных городов. В момент достижения конечной точки он будет содержать номера всех пройденных точек, т. е. описание маршрута.
В incl будем записывать true, если точка с номером i включена в маршрут. Делается это для того, чтобы не включать в маршрут уже пройденную точку (не ходить по кругу).
Так как мы используем рекурсивную процедуру, то надо обратить особое внимание на условие завершения рекурсивного процесса. Процедура должна прекратить вызывать сама себя, если текущая точка совпала с заданной конечной точкой.
На рис. 12.11 приведена блок-схема алгоритма процедуры выбора очередной точки формируемого маршрута, а диалоговое окно — на рис. 12.12.
Для ввода массива, представляющего описание карты, используется компонент stringGridl (значения его свойств приведены в таблице 12.1), для вывода результата (найденного маршрута) — поле метки Label1. Начальная и конечная точки маршрута задаются вводом значений в поля редактирования Edit1и Edit2. Процедура поиска запускается щелчком кнопки Поиск (Button1). Поля меток Label2, Label3 и Label4 используются для вывода поясняющего текста.
Блок-схема процедуры выбора точки маршрута
При запуске программы в момент активизации формы приложения происходит событие OnActivate, процедура обработки которого заполняет массив StringGrid1.cells значениями, представляющими описание карты. Эта же процедура нумерует строки и столбцы таблицы, заполняя зафиксированные ячейки первого столбца и первой строки StringGrid1. Поиск маршрута инициирует процедура TFormi.Buttoniciick, которая запускается щелчком на кнопке Поиск. Данная процедура для поиска точки, соединенной с исходной точкой, вызывает процедуру step, которая после выбора первой точки, соединенной с начальной, и включения ее в маршрут вызывает сама себя. При этом в качестве начальной точки задается уже не исходная, а текущая, только что включенная в маршрут.
Ответьте на контрольные вопросы.
Форма отчёта: Отчет выполняется в тетрадях по практическим работам в письменном виде. Программа отлаживается в IDE Delphi и в виде файлов копируется на сетевой диск.
Содержание отчета:
Тема работы.
Цель работы.
По каждому из заданий:
Условие задачи.
Постановка задачи.
Текст программного кода на языке OBJECT PASCAL.
Результаты расчетов (входные и выходные данные).
Система оценки: двухбалльная.