2015-05-10
429
Лабораторна робота № 9.
| Тема: | Розробка і відладка програм із використанням рекурсії. |
| Мета: | Здобути практичні навички розробки рекурсивних функцій і програм які їх використовують. |
| Програмне забезпечення | ОС Windows, C++Builder 10 |
| Завдання: | Розробити і протестувати програми для вирішення наступних задач:
|
| Зміст звіту: | 1. Порядок виконання роботи. 2. Опис алгоритмів вирішення задач. 3. Вихідний код програм з коментарями. 4. Результати тестування програм. Висновки |
Короткі теоретичні відомості
|
|
|
Рекурсія — виклик функції з неї самої (звичайно з іншими значеннями вхідних параметрів), чи безпосередньо через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.
Міць рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою рекурсивної програми ж можливо описати нескінченне обчислення, причому без явних повторень частин програми.
Існує спеціальний тип рекурсії, називаний «хвостовою рекурсією». Інтерпретатори і компілятори функціональных мов програмування, що підтримують оптимізацію коду (вихідного і/чи що виконується), виконують хвостову рекурсію в обмеженому обсязі пам'яті за допомогою ітерацій.
Варто уникати надлишкової глибини рекурсії, тому що це може викликати переповнення стека викликів.
Факторіал
Найпростішим прикладом рекурсивного рішення служить завдання про обчислення факторіала. Звичайно, факторіал можна обчислити і без рекурсії, але рекурсивне рішення виглядає витонченіше. Тут потрібно визначити деяку функцію F(n), яка буде обчислювати значення n! через саму себе. В даному випадку скористаємося формулою: F(n) = F(n-1) * n. Врахуємо і умову виходу: якщо n менше 2, то відповідь дорівнює 1. Таким чином, в тих випадках, коли n менше 2х, функція не буде себе викликати, що буде гарантувати вихід з рекурсії.
|
|
|
/ / Обчислення факторіала
int F(int n){
if n<2 then return 1;
else return F(n-1)*n;
}
Задача про Ханойські вежі
Завдання:
Є три стержня, на один з яких нанизані N кілець, причому кільця відрізняються розміром і лежать менше на більшому. Потрібно перенести піраміду з N кілець з одного стрижня на інший за найменше число ходів. За один раз дозволяється переносити тільки одне кільце, причому не можна класти більше кільце на менше.
Припустимо, що ми хочемо отримати в результаті програму, яка за заданим значенням N буде нам виводити послідовність дій, які вирішують задачу, тобто алгоритм перенесення всіх кілець із стержня А на стержень B. Дія перенесення одного кільця буде мати вигляд: А -> В, що означає перенесення одного верхнього кільця зі стержня з ім'ям А, на стержень з ім'ям B. Розглянемо, як повинні виглядати рішення для малих N:
N=1: A -> B
N=2: A -> C, A -> B, C -> B
N=3: A -> B, A -> C, B -> C, A -> B, C -> A, C -> B, A -> B
Рішення: Розглянемо, як вміючи перекладати N-1 кільце можливо перекласти N кілець. Для цього необхідно виконати наступні дії:
1) перекласти N-1 кільце з вихідного на тимчасовий стержень
2) перекласти 1 кільце з вихідного на кінцевий стержень
3) перекласти N-1 кільце з тимчасового на кінцевий стержень
Зауважимо, що 0 і 1 кільце ми вміємо перекладати. Для кращого розуміння слід сказати, що N-1 кільце буде перекладатися через 2 дії з N-2 кільцями, N-2 кільця через 2 дії з N-3 кільцями і т.д. поки не опустимося до нуля. Відзначимо також, що при перекладенні N-1 кільця, N-е (і кільця ще більшого діаметра), ніяк не заважають.
// n - число кілець, from - ім'я стержня-джерела, to - ім'я стержня-приймача
// temp - ім'я тимчасового стержня
void Hanoi(int n, char from, char to, char temp)
{
if(n>0){
Hanoi(n-1, from, temp, to);
writeln(from, '->', to);
Hanoi(n-1, temp, to, from);
}
}
Тепер для того, щоб отримати рішення задачі для N = 8 досить викликати вищеописану функцію, наприклад, наступним чином:
Hanoi(n-1, temp, to, from);
