завдання 3
- У програмі вкажіть рекурсивні функції. Поясніть роботу рекурсивних функцій.
- Перевірте роботу програми при зміні порядку оголошень функцій.
- Перевірте роботу програми без використання прототипів функцій.
- Для випадку, коли
, Передбачте висновок результату в рядок, а не в стовпець. - У програму додайте програмний код для підрахунку рекурсивних викликів, кожної з рекурсивних функцій.
- остройте залежність числа комбінацій заповнення і звільнення клітин від введеного числа n.
Приклад 4. "Ханойська вежа". Напишіть програму по вирішення наступного завдання. Є піраміда з n кілець, що лежать на підставі А (на стрижні, на стовпі) одне на одному в порядку убування розмірів. Кільця повинні бути переміщені на підставу В в тому ж порядку, в якому вони були на підставі А, при використанні "проміжного" підстави С. Єдиними дозволеними переміщеннями є такі, при яких кільце, взяте з вершини однієї з пірамід, поміщається на більше кільце, або на порожній підставу. Здійснити видачу на друк (на консоль, в текстовий файл) послідовності переміщень кілець.
"Ханойська вежа" - відома задача. Алгоритм рішення цієї задачі досить докладно описаний в [ 18.10 ].
Рішення завдання "Ханойська вежа"
Для рекурсивного вирішення цього завдання слід пройти три етапи.
1-й етап - параметризація. У цьому завданні природним параметром є n - число кілець. У число параметрів можна включити також і три підстави: А (вихідне), В (кінцеве), С (проміжне).
2-й етап - пошук тривіальних випадків. Тут тривіальним випадком буде такою, при якому n = 0; в цьому випадку просто нічого робити.
3-й етап - редукція загального випадку до більш простому. Тут треба зазначити, що n кілець можуть бути переміщені з А на В наступним шляхом:
- перенесення (рекурсивно) n - 1 кілець з вершини А (вихідне підставу) на С ( "проміжне" підстава) з урахуванням правил: підстава В (кінцева мета) використовується як проміжне підставу;
- переміщення на В кільця (найбільшого діаметра), що залишився на А;
- перенесення (рекурсивно) n - 1 інших кілець з З на В при дотриманні правил з А в якості проміжного підстави.
Алгоритм розв'язання задачі запишемо в наступному вигляді:
hanoi (n-1, A, C, B); перемістити (A, B); hanoi (n-1, C, B, A);де hanoi () - ім'я рекурсивної функції [ 18.10 ].
Приклад проміжного становища Ханойська вежі при n = 4 показаний на Мал. 18.4 .
Мал. 18.4. Проміжне становище Ханойська вежі при n = 4
Число елементарних переміщень одно 2n - 1, де n - кількість вихідних дисків [ 18.10 ]. Зі збільшенням n число переміщень швидко наростає.
на Мал. 18.5 показана залежність елементарних переміщень від числа дисків.
Мал. 18.5. Залежність елементарних переміщень від числа дисків
З урахуванням того, що переміщення диска - це є рекурсивний виклик функції, то на кожен виклик потрібен певний час. Практично з будь-яким кінцевим малим часом обробки рекурсивного виклику загальний час роботи рекурсивної функції для великої кількості дисків n стає надскладним на існуючих сучасних комп'ютерах. Відповідно до легенди кінець світу настане при переміщенні 64 дисків [ 18.10 ].
У зв'язку зі статечним зростанням числа рекурсивних викликів в програмі обмежимося величиною n = 15.
Програмний код рішення прикладу:
#include <stdio.h> #include <conio.h> #include <math.h> // Пртотіп рекурсивної функції void hanoi (int n, char a, char b, char c); int main (void) {char a = 'A'; // вихідне підставу char b = 'B'; // кінцеве підставу char c = 'C'; // проміжне підставу double n; // число дисків char str [81] = "15"; // ініціалізація рядки puts ( "\ n Hanoi Tower; A - starting; B - end; C - intermediate"); while (0.01) {// 0.01 - як справжнє значення printf ( "\ n Enter the number of disks:"); scanf_s ( "% s", str, 80); n = atof (str); if (n <= 0 || ceil (n)! = n) {printf ( "\ n Error input. Press any key:"); _getch (); continue; } Else if (n> 15.0) {printf ( "\ n Very large number. Press any key:"); _getch (); continue; } Else break; } Puts ( "\ n Elementary transferences:"); hanoi ((int) n, a, b, c); printf ( "\ n \ n Press any key:"); _getch (); return 0; } // Визначення рекурсивної функції void hanoi (int num, char a, char b, char c) {if (num> 0) {hanoi (num-1, a, c, b); printf ( "\ t% c ->% c \ n", a, b); hanoi (num-1, c, b, a); }}Результат виконання програми при n = 5 показаний на Мал. 18.6 .
Мал. 18.6. Переміщення дисків в Ханойські вежі при n = 5
завдання 4
- Визначте тип рекурсії, використовуваної в програмі.
- Для випадку, коли не всі елементарні переміщення виводяться на екран дисплея, передбачте висновок результату програми в текстовий файл з ім'ям compX.txt, де X - номер комп'ютера, на якому виконується лабораторна робота.
- Програмним шляхом виконайте підрахунок загальної кількості звернень до рекурсивної функції. Зробіть також висновок порядкового номера переміщення на екран дисплея. Порядковий номер розташуйте зліва від елементарного переміщення. Побудувати (в MS Excel або в MATLAB) залежність кількості звернень до рекурсивної функції від заданого числа дисків.
- Змініть аргументи рекурсивної функції: включити змінні типу int для визначення імені (нумерації) підстави.
- Змініть умову задачі "Ханойська вежа". Спочатку вихідним підставою вважати В, кінцевим С, проміжним А. Потім прийняти за вихідне підставу С, проміжним В, кінцевим А.
Приклад 5. "Завдання про рюкзаку". Є 10 предметів, про які відомі їх ваги та вартості. Потрібно помістити в рюкзак предмети таким чином, щоб вони не перевищили допустимий вага для рюкзака при максимальній вартості обраних предметів. Вихідні параметри моделі - характеристики предметів взяті з [11] і наведені в табл. 18.1 .
Таблиця 18.1. Характеристики предметів № п / п 1 2 3 4 5 6 7 8 9 10 Вага 10 11 12 13 14 15 16 17 18 19 Вартість 18 20 17 19 25 21 27 23 25 24Дане завдання широко відома [ 18.9 - 18.10 - 18.11 ], Вона ще називається завданням про ранці, або варіант з англійської - "knapsack problem". Передбачається, що один і той же предмет не може бути взятий кілька разів.
Для вирішення поставленого завдання використовуємо рекурсивний алгоритм, описаний в [ 18.11 ], Де також наводиться фрагмент програми на мові програмування MODULA - 2.
Програмний код рішення прикладу:
#include <stdio.h> #include <conio.h> #include <locale.h> const int limW = 20; // гранична вага обраних предметів enum {N = 10}; // кількість предметів typedef struct {int weight; //// вага або розмір предметів int value; //// вартість або цінність предметів} object; // Формування структурного типу з параметрами моделі object obj [] = {10,18, 11,20, 12,17, 13,19, 14,25, 15,21, 16,27, 17,23, 18,25, 19,24}; int maxv; // для ініціалізації вартості предметів // Рекурсивна функція int TRY (int i, int tw, int av) {// Спроба включення предмета if (tw + obj [i] .weight <= limW) if (i <N-1) TRY (i + 1, tw + obj [i] .weight, av); else if (av> maxv) maxv = av; // Спроба виключення предмета if (av> maxv + obj [i] .value) if (i <N-1) TRY (i + 1, tw, av - obj [i] .value); else maxv = av - obj [i] .value; return maxv; } // Головна функція програми int main (void) {int i, price; int sumw = 0; int sumv = 0; setlocale (LC_ALL, "rus"); maxv = obj [0] .value; // ініціалізації вартості предметів puts ( "\ n \ t \ t \ tЗАДАЧА Про рюкзак"); puts ( "\ t \ t Характеристика предметів"); for (i = 0; i <(4 * N + 12); i ++) printf ( "% s", "_"); printf ( "\ n \ n% 12s", "Вага:"); for (i = 0; i <N; i ++) {sumw + = obj [i] .weight; printf ( "% 3d", obj [i] .weight); } Printf ( "\ n% 12s", "Вартість:"); for (i = 0; i <N; i ++) {sumv + = obj [i] .value; printf ( "% 3d", obj [i] .value); } Printf ( "\ n"); for (i = 0; i <(4 * N + 12); i ++) printf ( "% s", "_"); printf ( "\ n \ n% 32s:% d \ n", "Загальна вага всіх предметів", sumw); printf ( "% 32s:% d \ n", "Загальна вартість всіх предметів", sumv); printf ( "% 32s:% d \ n", "Допустима вага рюкзака", limW); for (i = 0; i <(4 * N + 12); i ++) printf ( "% s", "_"); // Виклик рекурсивної функції з початковими параметрами price = TRY (0,0, sumv); printf ( "\ n \ n Вартість обраних предметів:% d \ n", price); for (i = 0; i <(4 * N + 12); i ++) printf ( "% s", "_"); printf ( "\ n \ n ... Натисніть будь-яку клавішу:"); _getch (); return 0; }Приклад виконання програми показаний на Мал. 18.7 .
Мал. 18.7. Приклад виконання програми вирішення задачі про рюкзак
Представлена програма заснована на наступному алгоритмі [ 18.11 ]. У рекурсивної функції TRY () визначені дві ситуації для вибору предмета в рюкзак. Якщо мова йде про включення то об'єкт (предмет зі своєю вагою і вартістю) можна включити у вибірку для укладання в рюкзак, якщо він підходить за ваговими обмеженням. Якщо він не підходить, то спроби додати ще один об'єкт в поточну вибірку можна припинити. Коли ж мова йде про виключення, то критерієм прийнятності, т. Е. Можливість продовження побудови поточної вибірки, буде те, що після даного виключення загальна цінність (вартість) буде не менше отриманого до цього моменту оптимуму. У даній програмі реалізована схема з поверненнями, що використовує деякі обмеження для зменшення росту потенційного дерева пошуку, називається алгоритмом гілок і меж [ 18.11 ].