Рекурсія1. ПРИЗНАЧЕННЯ ПРОГРАМИ Рекурсія є одним з фундаментальних методів програмування. Не дивлячись на те, що рекурсивні алгоритми згадуються в підручнику інформатики, для більшості учнів рекурсія залишається незрозумілою. Прикладів в підручнику явно недостатньо, та й ті допускають очевидне рішення за допомогою звичайного циклу. В той же час є декілька класичних завдань, що чудово ілюструють можливості рекурсії. Це завдання про перестановки, розміщення ферзів на шахівниці, пошуку шляху в лабіринті, гра |Ханойські башти| і т.д. Ефективність рекурсивних алгоритмів в поєднанні з їх ідейним багатством і логікою побудови служать основою для включення в олімпіади з інформатики завдань, в основу рішення яких покладені рекурсії. Зрозуміло, що для розв»язання подібних завдань учасники олімпіади повинні, окрім розуміння суті рекурсивних алгоритмів, мати також і певний досвід їх розробки. Для детальнішого знайомства з рекурсивними алгоритмами і підготовки до олімпіад і призначена дана робота. 2. ТЕОРІЯ РЕКУРСІЇ 2.1. Основні визначення. Приклади При розробці програми часто необхідно звести початкові завдання до простіших. Серед цих завдань може опинитися і первинна, але в більш спрощеній формі. Рекурсивним називається об.єкт, який містить сам себе або визначений за допомогою самого себе. або Алгоритм, який містить звернення до себе, називається рекурсивним… або Спосіб зведення завдання до нього ж самого, але із зміненими початковими даними, називається рекурсією. Пояснимо на прикладах. ПРИКЛАД 1. Обчислення факторіалу п!=1*2*3...п зводиться до обчислення добутку цілих чисел від 1 до п 0! = 1 1! = 1 4! = 1*2*3*4 = 24 Такий добуток можна легко обчислити за допомогою интеретивных (циклічних) конструкцій, наприклад, оператора циклу for program Factorial. var Fact: Longint. n,i : Integer. begin Write (. Введіть число n:.). Realdn (n). Fact: = 1. for i: = 1 to n do Fact:= Fact*i. WriteLn (факторіал n! = ., Fact). end. Проте, n! рівне n, помноженому на добуток від 1 до (n-1), тобто на (1-n)! n! = (n-1)!*n 0! =1 за означенням 4! = 3!*4 6! = 5!*6 В цьому випадку означуване поняття n! описується через саме себе (n) і через простіше поняття (n-1)!. Щоб знайти n!, треба застосувати функцію факторіа до числа (п-1), потім до (п-2) і т.д. аж до 1. Це і означає, що таке означення факторіалу рекурсивне. Будь-яке рекурсивне означення визначається за допомогою рекурентной формули, яка завжди містить два елементи: умова завершення і спосіб вираження одного кроку рішення за допомогою іншого простішого кроку. Кожна рекурентная формула складається з двох частин. Одна частина визначає поняття через нього ж, інша частина через інші поняття. Для функції п! рекурентная формула має вигляд: (1) 0! = 1 (2) для п 0 п! = п*(п-1)! Рекурсивний виклик може бути непрямим. В цьому випадку підпрограма звертається до себе опосередковано, шляхом виклику іншої підпрограми, в якій міститься звернення до першої, створюється рекурсивний ланцюжок. Наприклад: Procedure A (i:byte). begin ... B (i). ... end. Procedure B (j:Byte). ... begin ... A (j). ... end. Обов.язковим елементом в описі всякого рекурсивного процесу є якесь твердження, що визначає умову завершення рекурсії. Це - опорна умова, або |якір| рекурсії, тобто фіксоване значення, що свідомо досягається в ході рекурсивних обчислень і дозволяє організувати своєчасну зупинку процесу. Стосовно обчислення n! опорною умовою (|якорем|) буде рівність i = 1. Використання рекурсії дозволяє легко (майже дослівно) запрограмувати обчислення за рекурентними формулах. Наприклад, програма, використовуються рекурсивну функцію для обчислення факторіалу n! має вигляд program Factorial. var n: Integer. function Fact (i:integer): Longint. begin if (i=1) or (i=0) then Fact: =1 else Fact: =i*Fact(i-1). end. begin Write (.Введіть число n:.). Readln (n) Writeln (Факторіал n!=.,Fact(n)). end. Зміст і потужність рекурсивного визначення, а також його головне призначення полягає в тому, що воно дозволяє за допомогою кінцевого виразу визначити нескінчену множину об.єктів. За допомогою кінцевого рекурсивного алгоритму можна визначити нескінчене обчислення, причому алгоритм не міститиме повторень фрагментів тексту. Для створення рекурентних алгоритмів необхідно і досить наявність поняття процедури або функції, оскільки їх наявність дозволяє дати будь-якій послідовності дій (операторів) ім.я, за допомогою якого цю процедуру (функцію) викликати. Програми, в яких використовують рекурсивні процедури відрізняються простотою, наочністю і комплектністю тексту, оскільки рекурсивна процедура указує що потрібно робити, а нерекурсивна більше акцентує увагу на тому, як потрібно робити. Проте за цю простоту доводиться розплачуватися неекономним використанням оперативної пам.яті, оскільки при кожному рекурсивному виклику для локальних змінних, а також для параметрів процедури, які передаються за значенням, виділяються нові комірки. Як правило, програми, що використовують пам.яті интеративні (циклічні)процеси виходять більш швидкодіючими, ніж рекурсивні. Але ці недоліки врівноважуються, коли в постановці завдання явно присутня рекурсивність - в описі структур даних або самого алгоритму (чим того й іншого разом), - тоді саме рекурсивні методи програмування виявляються найбільш доречними, витонченими і ефективними. Необхідно пам.ятати, що будь-якій локальній змінній А на різних рівнях рекурсії відповідатимуть різні елементи пам.яті, які можуть мати різні значення. Тому, скористатися значенням змінної А i-го рівня рекурсії можна знаходячись тільки на цьому i-том рівні. Глибина рекурсії - це максимальне число рекурсивних викликів процедури без повернень, яке відбувається під час виконання програми. Поточний рівень рекурсії - число рекурсивних викликів в кожен конкретний момент часу. Стек - це послідовність рекурсивних викликів (принцип |першим увійшов - останнім вийшов). Пояснимо сказане на прикладі 2 Числа Фібоначчі. Числа Фібоначчі можна визначити таким чином: перше і друге рівне 1, кожне подальше (починаючи з третього) є сума двох попередніх. 1, 1, 2, 3, 5, 8, 13, 21 ... їх можна обчислити за допомогою формули F(n)= ------------------------------ або за допомогою рекурсивного означення (1) F(1)= 1 (2) F(2)= 1 (3) для n 2 F(n)= F(n-1)+F(n-2) Зрозуміло, що організувати обчислення за рекурентною формулою можна і без допомоги рекурсії, але для наочності розв»яжемо її в рекурсивним способом. Припустимо, нам потрібна підпрограма - функція, яка отримує цілочислений параметр n і що повертає n-е число Фібоначчі. Назвемо її fib. Як і у всякому рекурсивному процесі, ми повинні сформувати умову виходу з нього (спеціально обумовивши випадки, коли n=1 або n=2), а також вказати спосіб переходу від одного етапу рішення до іншого, простішого. function fib (n: integer): integer { Рекурсивна функція що обчислює n-й член числа Фібоначчі: 1, 1, 2, 3, 5, 8 ...} begin if(n=0) or (n=1) or (n=2) then Fib: = 1 else fib:=fib(n-1) + fib (n-20 end. Обчислимо 6-е число Фібоначчі (fib 6). Прослідкуємо, наскільки довгий ланцюжок дій породжує такий виклик. При першому вході у функцію fib (n=6) значення fib визначається як fib(5)+ fib(4). Але щоб одержати fib(5), нам треба обчислити fib(4)+ fib(3). обчислення fib(4) |розгортається| в fib(3)+ fib(2), а fib(3)= 6fib(2)+ fib(1). Нарешті, обчислюється що fib(2) і fib(1) фіксоване значення 1 згідно умови припинення рекурсії if(n-1)= (n-2) then fib:=1. Ми протрасували першу частину процесу обчислення fib(5) - фазу так званого рекурсивного занурення від fib(5) до fib(1), за якою слідує фаза |спливання|, що супроводжується новими |зануреннями| і що поступово формує чисельні результати: fib(3)= 1+1 = 2, fib(4)= 2+fib(2)= 2+1=3 fib(5)= 3+fib(3)= 3+ fib(2)+ fib(1)=3+1+fib(1)=4+1= 5 Потрібно пройти ще аналогічний рекурсивний шлях для обчислення fib(4) з тим, щоб його результат додати до значення fib(5), підрахувавши тим самим остаточне значення fib(6). Воно рівне 8, це і є 6-е число Фібоначчі. На цьому прикладі ми бачимо, що дана рекурсивна функція займає дуже великий об.єм оперативної пам.яті, але прекрасно демонструє основні принципи рекурсії. Числа Фібоначчі можна обчислювати за ітеративною схемою, при якій використання допоміжних змінних x=fibi і y=fibi-1 дозволяє уникнути повторного обчислення одних і тих же значень: обчислення x = fibn для n 0 i: = 1. x: = 1. у: 0. while i<=n do begin z: = x. i: = i = 1. x:= x+y. у: = z. end Примітка: Три присвоєння x, у і z можна виразити всього лише двома присвоєннями без використання допоміжної змінної z: x: = x + у. у: = x - у. Таким чином: Слід уникати рекурсії, якщо є очевидном интеративное рішення поставленої задачі. 2.2. Форми рекурсивних процедур. Складання рекурсивних алгоритмів У загальному випадку будь-яка рекурсивна процедура включає деяку безліч операторів S і один або декілька операторів рекурсивного виклику P. Оскільки для кожної копи рекурсивної процедури, як ми переконалися вище, необхідно виділяти додаткову область пам.яті, а нескінченної пам.яті не існує, то: головна вимога до рекурсивних процедур полягає в тому, що виклик рекурсивної процедури повинен виконуватися при умові, яка на якомусь рівні рекурсії стане помилковою. Якщо умова істинна, рекурсивний спуск продовжується. Коли вона стає помилковою, то спуск закінчується і починається почергове рекурсивне повернення зі всіх викликаних на даний момент копій рекурсивної процедури. Перш ніж скласти рекурсивний алгоритм необхідно побудувати рекурсивний опис початкового завдання, тобто його постановку. Оскільки виконання рекурсивних алгоритмів здійснюється послідовним |зануренням-виходом|, то рекурсивна постановка завдання повинна бути розгалуженою схемою, що містить принаймні два варіанти дій: дія при виході з рекурсії дія при зануренні в рекурсію і умову вибору необхідних дій. Саме, правильна рекурсивна постановка завдання є визначальною і найбільш складною проблемою у використанні рекурсії при розв»язанні задач. Структура рекурсивної процедури може приймати три різні форми. 1. Форма з виконанням дій до рекурсивного виклику ( з виконанням дій на рекурсивному спуску). procedure Rec. begin S. if умова then Rec. end Приклад приведений в завданні |Швидке сортування| п.2.3 2. Форма з виконанням дій після рекурсивного виклику ( з виконанням дій на рекурсивному поверненні). procedure Rec. begin if умова then Rec. S. end 3. Форма з виконанням дій як до так і після рекурсивного виклику ( з виконанням дій як на рекурсивному спуску, так і на поверненні). procedure Rec. begin S1. if умова then Rec. S2. end. або procedure Rec. begin if умова then begin S1. Rec. S2. end. end. Всі форми рекурсивних процедур знаходять застосування на практиці. Багато завдань, зокрема обчислення факторіалу, байдужі до того, яка використовується форма рекурсивної процедури. Проте є класи завдань (деревовидні структури), де потрібно свідомо управляти ходом рекурсії, оскільки одні завдання можна зробити тільки на спуску, а інші - тільки на поверненні. Приклад - п.3.4. Завдання про вісім ферзів. 2.2.1. Виконання дій на рекурсивному спуску. Для реалізації універсального алгоритму обчислення факторіалу, що працює на спуску, в рекурсивну функцію потрібно додатково ввести 2 параметри: Mult - для виконання до рекурсивного виклику (тобто на спуску) операції множення накопичуваного значення факторіалу на черговий множник. m - для забезпечення незалежності рекурсивної функції від імені конкретної глобальної змінної, тобто для підвищення універсальності функції. Програма Factorial Down, яка використовує рекурсивну функцію Fact Dn, що виконує обчислення на спуску, має вигляд: program Factorial. var n: Integer. function Fact_n (Mult: Longint.i,m: Integer):Longint. begin Mult:=Mult*i.{ Накопичення факторіалу стоїть до оператора рекурсивного виклику. Отже обчислення виконується на спуску.} if i = m then Fact_Dn:= Mult else Fact_Dn:=Fact_Dn(Mult i+1, m) end. begin Write (.Введіть число n: .). Readln (n). Writeln (.Факторіал n! =., Fact_Dn(1, 1, n)). end. Заповнимо таблицю трасування значень її параметрів за рівнями рекурсії для випадку n=5. ---------T---------------------------------------T-----------------¬ |Поточний| Рекурсивний спуск | Рекурсивне | | рівень | | повернення | |рекурсії| | | +--------+---------------------------------------+-----------------+ | | | | | 0 | Введення (n=5) Fact_Dn(1,1,5).|Виведення:n!=120 | +--------+---------------------------------------+-----------------+ | | | | | 1 | Mult:1*1(1). i=1. Fact_Dn(1,2,5).|Fact_Dn:=120. | +--------+---------------------------------------+-----------------+ | | | | | 2 | Mult:=1*2(2). i=2. Fact_Dn(2,3,5).|Fact_Dn:=120. | +--------+---------------------------------------+-----------------+ | | | | | 3 | Mult:=2*3(6). i=3. Fact_Dn(6,4,5).|Fact_Dn:=120. | +--------+---------------------------------------+-----------------+ | | | | | 4 | Mult:=6*4(24). i=4. Fact_Dn(24,5,5).|Fact_Dn:=120. | +--------+---------------------------------------+-----------------+ | | | | | 5 | Mult=24*5(120).i=5. Fact_Dn:=120. | Fact_Dn:=120. | L--------+---------------------------------------+-----------------+ Приведемо таблицю трасування по рівнях рекурсії для n=5 ---------T--------------------------------------T-------------- ---¬ |поточний| Рекурсивний спуск | Рекурсивне | | рівень | | повернення | |рекурсії| | | +--------+--------------------------------------+------------------+ | | | | | 0 | Введення (n=5) Fact_Up(5) |Виведення:n!=120 | +--------+--------------------------------------+------------------+ | | | | | 1 | i=5. Mult:Fact_Up(4).|Fact_Up:24*5(120).| +--------+--------------------------------------+------------------+ | | | | | 2 | i=4. Mult:Fact_Up(3).|Fact_Up:6*4(24). | +--------+--------------------------------------+------------------+ | | | | | 3 | i=3. Mult:Fact_Up(2).|Fact_Up:2*3(6). | +--------+--------------------------------------+------------------+ | | | | | 4 | i=2. Mult:Fact_Up(1).|Fact_Up:1*2(2). | +--------+--------------------------------------+------------------+ | | | | | 5 | i=1 Mult:=1. |Fact_Up:=1*1(1). | L--------+--------------------------------------+------------------- 2.2.3. Виконання дій як на рекурсивному спукску, так і на поверненні. Пояснимо на прикладі наступного завдання Завдання. Вивести на друк символи введеного рядка |HELLO| у зворотному напрямі. Рішення приведене у вигляді програми Reverse_String, що використовує рекурсивну процедуру Reverse. Нагадаємо, що функція eoln повертає значення рівне False, якщо рядок ще не закінчився, і значення, рівне True, коли прочитується останній символ рядка. program Reverse_String. procedure Reverse. var Ch:Char. begin if not eoln then begin Read (Ch). Reverse. Write (Ch). end end. begin Reverse. end. Якщо після запуску програми на виконання як вхідний рядок ввести слово |Hello|, то таблиця трасування (стек) по рівнях рекурсії матиме вигляд: ---------T---------------------------------------T-----------------¬ |Поточний| Рекурсивний спуск |Рекурсивне | | рівень | | повернення | |рекурсії| | | +--------+---------------------------------------+-----------------+ | | | | | 0 | Reverse. | | +--------+---------------------------------------+-----------------+ | 1 | eoln=False. Введення:.H..Reverse. | Висновок:.H.. | +--------+---------------------------------------+-----------------+ | 2 | eoln=False. Введення:.E..Reverse. | Висновок:.E.. | +- ------+---------------------------------------+-----------------+ | 3 | eoln=False. Введення:.L..Reverse. | Висновок:.L.. | |--------+---------------------------------------+-----------------+ | 4 | eoln=False. Введення:.L..Reverse. | Висновок:.L.. | +--------+---------------------------------------+-----------------+ | 5 | eoln=False. Введення:.O..Reverse. | Висновок:.O.. | +--------+---------------------------------------+-----------------+ | | eoln=True. | | L--------+---------------------------------------+------------------ Задачі 3. Завдання. Приклади розв»язання 3.1. Завдання про Ханойські башти. Дані три стовпчики - А, В, С. На стовпчику А один на одному знаходяться чотири диски різного діаметру, пронумеровані зверху вниз. Причому, вони розташовуються так, що кожен менший диск знаходиться над більшим. Потрібно перемістити ці чотири диски на стовпчик З, зберігши їх взаєморозташування. Стовпчик В дозволяється використовувати як допоміжний. При розв»язанні за один крок допускається переміщати лише один з верхніх дисків будь-якого стовпчика. Крім того, більший диск ніколи не дозволяється класти на диск меншого діаметру. Для визначення підходу до розв»язання поставленої задачі, розглянемо більш загальний випадок з n дисками. Якщо ми зможемо сформулювати розв»язання для n дисків в термінах розв»язання для n-1 диска, то поставлена проблема була б розв»язана, оскільки завдання для n-1 диска можна буде,в свою чергу, розв»язати в термінах n-2 дисків і т.д. до тривіального випадку одного диска. А для випадку одного диска (n=1) розв»язання виходить елементарним. Потрібн просто перемістити один єдиний диск із стовпчика А на стовпчик В. Таким чином, якщо сформулювати рзв»язання для n дисків в термінах n-1 диска, то ми фактично одержимо алгоритм рекурсивної процедури, за допомогою якої можна легко досягти мети поставленого завдання. Розглянемо словесний опис такого алгоритму ------------------------------------------------------------------¬ | if n=1 | | | | (then) | | | | 1.Перемістити цей єдиний диск із стовпчика А на стовбчик | | С і зупинитися. | | | | (else) | | 1.Перемістити верхні n-1 диск із стовпчика А на стовпчик В | | використовуючи стовпчик С як допоміжний. | | 2.Перемістити нижній диск, що залишився, із стовпчика А на | | стовпчик С. | | 3.Перемістити n-1 диск із стовпчика В на стовпчик С, | | використовуючи стовпчик А як допоміжний | | | L------------------------------------------------------------------ Можна з упевненістю сказати, що така послідовність дій дасть конкретне розв»язання поставленої задачі для будь-якого n. Це випливає з наступного. Якщо n=1, то коректність очевидна. Якщо n=2, то ми знаємо, що вже маємо розв»язання для (n-1)-го диска, яке рівне 1. Аналогічно, якщо n=3, ми знову маємо розв»язання для (n-1)-го диска б яке рівне 2. Так само можна сказати, що це розв»язання працює для n=1,2,3,4,5.. і якого-небудь іншого n. Приведемо програму Hanoi_Towers, яка вирішує поставлену задачу за допомогою рекурсивної процедури Move_Disks: Program Hanoi_Towers. var n: integer. procedure Move_Disks(n: byte. Sourse,Dest,Tmp: Char). {n - число дисків на стовпчику Sourse Sourse - Початковий стовпчик Dest - Стовпчик, на який на який потрібно переставити диск Tmp - Допоміжний стовпчик} begin if n=1 then WriteLn(.переставити диск номер 1 із стовпчика. sourse,. на стовпчик .,Dest) else begin { Переставляємо n-1 верхніх дисків з початкового стовпчика на допоміжний, використовуючи цільовий стовпчик як проміжний} Move_Disks(n-1,Sourse,Tmp,Dest). WriteLn(.Переставити диск номер .,n,. із стовпчика. Sourse,. на стовпчик .,Dest). { Переставляємо все n-1 диск з допоміжного стовпчика на цільовий, використовуючи початковий стовпчик як проміжний} Move_Disks(n-1,Tmp,Dest,Sourse). end. end. begin Write(.Введіть число дисків: .). ReadLn(n). WriteLn. WriteLn(.Послідовність інструкцій для розв»язання завдання:.). WriteLn. Move_Disks(n,.A.,.B.,.C.). end. Результат роботи програми Hanoi_Towers для числа початкових дисків, рівного 4, буде таким: Введіть число дисков:4 Послідовність інструкцій для розв»язання завдання: переставити диск номер 1 із стовпчика A на стовпчик B переставити диск номер 2 із стовпчика A на стовпчик C переставити диск номер 1 із стовпчика B на стовпчик C переставити диск номер 3 із стовпчика A на стовпчик B переставити диск номер 1 із стовпчика C на стовпчик A переставити диск номер 2 із стовпчика C на стовпчик B переставити диск номер 1 із стовпчика A на стовпчик B переставити диск номер 4 із стовпчика A на стовпчик C переставити диск номер 1 із стовпчика B на стовпчик C переставити диск номер 2 із стовпчика B на стовпчик A переставити диск номер 1 із стовпчика C на стовпчик A переставити диск номер 3 із стовпчика B на стовпчик C переставити диск номер 1 із стовпчика A на стовпчик B переставити диск номер 2 із стовпчика A на стовпчик C переставити диск номер 1 із стовпчика B на стовпчик C Підводячи підсумки розглянутих нами завдань, слід зазначити аналогію між методом математичної індукції і рекурсивним методом програмування. Дійсно, спочатку було сформульоване розв»язання для одного диска. Потім було припущення існування розв»язання для(n-1)-го диска, і на основі цього припущення побудована процедура переміщення n дисків в рекурсивній формі. 3.2 Швидке сортування. Реалізація методу швидкого сортування масиву є прекрасним прикладом використання рекурсії. Цей метод був розроблений в 1962 році професором Оксфордського університету До. Хоором. Ідеєю створення методу було припущення про те, що через низьку ефективність |бульбашкового| сортування цей метод потребує істотного доопрацювання. Саме через високу швидкіст виконання програм, написаних із застосуванням вдосконаленого |бульбашкового| сортування, цей метод стали називати |швидким| сортуванням. Принцип методу: 1. Вибираємо центральний елемент масиву A і записуємо його в змінну t. Потім переглядаємо по черзі зліва-направо і справа-наліво. При русі зліва направо шукаємо елемент А[i], який буде більше або рівний t, а також запам.ятовуємо його позицію.При русі справа наліво шукаємо елемент А[j], який буде менший або рівний t, і також запам.ятовуємо його позицію. Знайдені елементи міняємо місцями і продовжуємо зустрічний пошук по вказаних напрямах. Знайдені елементи міняємо місцями і так далі, поки при черговій ітерації пошуку зустрічні індекси i і j не перетнуться. Після цього перший етап вважається закінченим, після чого елементи початкового масиву виявляться розділеними на дві частини щодо значення t - всі елементи, які менше або рівні t, розташовуватимуться зліва від межі перетину індексів i і j, а всі елементи, які більше або рівні t, розташовуватимуться праворуч від межі. Таким чином, щодо значення t масив виходить відсортованим, але ліва і права його частині ще не впорядковані. 2. На другому етапі повторюються дії першого етапу для лівої і правої частин масиву окремо. В результаті масив виявиться розбитим вже на чотири непересічні по сортуванню частини, які можна упорядкувати окремо. На третьому етапі повторюються дії першого етапу окремо для кожної з чотирьох частин і так далі, поки довжина сортованих частин не стане рівною одному елементу і, отже, всі елементи масиву будуть вже впорядковані. Оскільки на кожному етапі повторюється одна і та ж послідовність дій, але в різних рамках масиву, то цю послідовність дій можна запрограмувати у вигляді рекурсивної процедури, що самовикликається, яка використовується в наступній програмі: program QuickSort. const n = 20. var A: array[1..n] of integer. i: word. procedure QSort(L,R: word). var B,Tmp: integer. i,j : word. begin B := A[(L+R) div 2]. i := L. j := R. while i<=j do begin while A[i] while A[j]>B do j := j-1. if i<=j then begin Tmp := A[i]. A[i]:= A[j]. A[j]:= Tmp. i := i+1. j := j-1. end. end. if L if i end. begin WriteLn(.Введіть розмір масиву: .). ReadLn(n). WriteLn(.Введіть елементи масиву:.). for i := 1 to n do Read(A[i]). ReadLn. {-----------------------------------------} QSort(1,n). {-----------------------------------------} WriteLn(.Відсортований масив:.). for i := 1 to n do Write(A[i]:8). WriteLn. end. 3.3. Лабіринт План лабіринту заданий прямокутною таблицею А[1:N,1:M], елементи якої рівні 0 або 1. 0 означає, що клітка належить коридору 1- стіні. Початкове положення подорожнього - клітка (Ўн,Jн). Виходом з лабіринту вважається будь-яка нульова клітка на межі плану лабіринту. Скласти алгоритм пошуку ритму виходу з лабіринту. Розв»язання. Це завдання легко піддається рекурсивному опису. Одним з варіантів рекурсивної процедури пошуку виходу з лабіринту може бути наступний алгоритм : АЛГ ЛАБІРИНТ ( ЦІЛИЙ N,M,i,j,F,L, Довжинана_шляху, ЦІЛИЙ ТАБ А[1:N,1:M] P[1:2,1:N*M]) АРГ N,M, i,j,F,L,A РЕЗ Довжина_шляху,Р ПОЧ ЦІЛИЙ к,x,y, ЦІЛИЙ ТАБ DX[1:4],DY[1:4] DX[1]:=1. DX[2]:=-1. DX[3]:=0. DX[4]:=0. |Значення приростів DY[1]:=1. DY[2]:=0. DY[3]:=1. DY[4]:=-1. ЯКЩО F=0 | Пошук шляху потрібно ТО ЯКЩО (i=N) АБО (i=1) АБО (j=M) АБО (j=1) продовжувати ТО F=1. Довжина_шляху:= L ІНАКШЕ k:=1 ПОКИ (k<=4) І (F=0) |Не потрібно перебирати інші НЦ варіанти виходу, якщо шлях x:=i+DX[k]. y:=j+DY[k] вже знайдений, тобто F=1 ЯКЩО І (x>0) І (y0) ТО ЯКЩО А[x,y]=0 ТО A[x,y]:=2 |Відмічаємо клітку шляху, щоб уникнути зациклення кільцевих коридорах. L:=L+1.P[1,L]:=x. P[2,L]:=y Запам.ятовуємо шлях ЛАБІРИНТ (N,M,x,y,F,L,Довжина_шляху,A,P) A[x,y]:=0 Відновлюємо стан таблиць А і Р (ЎЎЎ) . L:=L-1 ВСЕ ВСЕ k:=k+1 КЦ ВСЕ ВСЕ КОН У головному алгоритмі необхідно привласнити початкові значення аргументам рекурсивної процедури. АЛГ ЛАБ_ОСН(ЦІЛИЙ N,M,Iн,Jн,Довжина_шляху,ЦІЛ ТАБ А [1:N,1:M] P[1:2,1:N*M],ЛИТ Z). АРГ N,M,F,Iн,Jн РЕЗ Z,P,Довжина_шляху ПОЧ ЦІЛИЙ F,L F:=0. P[1,11]:=Iн. P[2,1]:=Jн. L:1. ЛАБІРИНТ (N,M,Iн,Jн,F,l,Довжина_шляху,A,P) ЯКЩО F = 0 ТО Z:=.Немає розв»язання!. ІНАКШЕ Z:=.Є розв»язання!. ВСЕ КІН Розглянутий нами варіант пошуку будь-якого виходу з лабіринту може бути перетворений в пошук найкоротшого шляху. Для цього необхідно прибрати |прапорець| F і забезпечити повний перебір всіх напрямів руху з поточної клітинки (i,j). 3.4. Перестановки Програма отримання перестановок з безлічі чисел [1...N ] const N=5 type IntSet=set of N...N. var A:array [1...N] of integer.{ перестановка} Procedure Print. var i:integer begin for i:=1 to N do Write (A[i]). Writeln. end. Procedure Perest (S:Int Set. k:integer) var i:integer. begin for i:=1 to N do its= [] then Print else if i in s then begin A[k]:= i. Present (s-[i],k+1). end {if} end. begin Perest ([1..N],1). end. 3.5. Різні завдання. 3.5.1. Type ім.я = (Алла, ..., Юрій, Ні). Припускаючи вже описаними функції БАТЬКО(x) і МАТИ(x), значеннями яких є імена відповідно батька і матері людини по імені X або ідентифікатор НЕМАЄ, якщо відсутні відомості про відповідного батька описати логічну функцію НАЩАДОК(а,b), перевіряючу, чи є людина з ім.ям B нащадком (дитиною, онуком, правнуком, і т.д.) людини з ім.ям A Рішення. Function НАЩАДОК (а,b : ім.я) : boolean. var f,m : ім.я. Begin if (а = b) or (а = Ні) or (b = Ні) then НАЩАДОК := false else begin f := БАТЬКО (b). m := МАТИ (b). if (а = f) or (а = m) then НАЩАДОК := true else { Дитина нащадка - також нащадок} if НАЩАДОК (а,f) then НАЩАДОК := true else НАЩАДОК := НАЩАДОК(а,m). end End. 3.5.2. Const n = 40. Type Вектор = array [1..n] of real. Описати функцію MIN(x) для визначення мінімального елементу вектора X, ввівши допоміжну рекурсивну процедуру MIN1(k), що знаходить мінімум серед останніх елементів вектора X, починаючи з K-того. Рішення. Function MIN (Var x : вектор) : real. Function MIN1 (до : integer) : real. { min x[до..n]} Var m : real. begin if до = n then minl := x[n] { min x[n..n]= x[n]} else begin { min x[до..n]= min (x[k], min x[k+1..n]} m := MIN1 (k+1). if x[k]< m then MIN1 := x[k] else MIN1 := m. end end. { of min1 } Begin Min := MIN1 (1) End. 3.5.3. У вхідному файлі задана ненульова послідовність додатних цілих чисел, за якою слідує від»ємне число. Описати рекурсивну функцію SUM без параметрів для знаходження суми цих додатніх чисел. Розв»язання. Function Sum : real. Var x : real. Begin read (x). if x<0 then Sum := 0 else Sum := X + Sum. end. 3.5.4. Програма. У вхідному файлі записана (без помилок) формула наступного вигляду : < Формула > ::= < Цифра > | < Формула >< Знак >< Формула > < Знак > ::= + | - | * < Цифра > ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Ввести цю формулу і обчислити її значення ( Наприклад 5 -> 5((2-4)*6) -> 12 ) Розв»язання. Program Formula (input,output). Function F : integer. { F Читає з початку вхідного файлу літери, створюючі закінчену формулу, і обчислює її значення як ціле } Var C,Op : char. x,y : integer. Begin Read (c). if (c>=.0.) and (c<=.9.) then { Цифра є формула } F := ord(c) - ord(.0.) else { Почалася формула вигляду (X op Y) } Begin X := F. Read (op). у := F. Case Op of .+. : F := x+y. .-. : F := x-y. .*. : F := x*y. End. Read(c). { Пробіл .). } end. end. { of F } Begin Writeln (F). end.
