Определяне на възел на дървото по неговия номер

Идеята на този подход е да се заменят рекурсивните извиквания с прост цикъл, който ще се изпълнява толкова пъти, колкото възли има в дървото, образувано от рекурсивните процедури. Какво точно ще се прави на всяка стъпка трябва да се определи от номера на стъпката. Сравняването на номера на стъпката и необходимите действия не е тривиална задача и във всеки случай ще трябва да се решава отделно.

Например, да кажем, че трябва да изпълнимkвложени цикъла сnстъпки всяка:

за i1 := 0 до n-1 направете за i2 := 0 до n-1 направете за i3 := 0 до n-1 направете …

Акоkне е известно предварително, тогава е невъзможно да ги напишете изрично, както е показано по-горе. Използвайки техниката, демонстрирана в раздел 6.5, можете да получите необходимия брой вложени цикли, като използвате рекурсивна процедура:

процедура NestedCycles(Индекси: масив от цели числа; n, k, дълбочина: цяло число); var i: цяло число; започва, ако дълбочина k . След като сортираме номерата им в десетичната бройна система и преведем всеки от тях в система с основаn, получаваме стойностите на индекса:

M := кръгъл (IntPower(n, k)); за i := 0 до M-1 do begin Number := i; за p := 0 до k-1 do begin Indexes[k - p] := Number mod n; Число := Число div n; край; Направи нещо (индекси); край;

Още веднъж отбелязваме, че методът не е универсален и за всяка задача ще трябва да измислите нещо свое.

Друг страхотен пример е изчислението чрез броя на стъпките на смените в проблема с кулите на Ханой, вижте тук: http://algolist.manual.ru/maths/combinat/hanoi.php

Тестови въпроси

1. Определете какво ще правят следните рекурсивни процедури и функции.

(a) Какво ще отпечата следната процедура, когато се извика Rec(4)?

процедураRec(a: цяло число); започнете writeln(a); ако a>0 тогава Rec(a-1); writeln(a); край;

(b) Каква ще бъде стойността на функцията Nod(78, 26)?

функция Nod(a, b: цяло число): цяло число; започва, ако a > b тогава кимване := кимване(a – b, b) иначе ако b>gt; a then Nod := Nod(a, b – a) else Nod := a; край;

процедура A(n: цяло число); процедура B(n: цяло число); процедура A(n: цяло число); започнете writeln(n); B(n-1); край; процедура B(n: цяло число); започнете writeln(n); ако

а) броят на отварящите и затварящите скоби е равен. (b) във всяка двойка отварящи и съответстващи затварящи скоби, скобите са поставени правилно.

Примери за неправилно разположение: )(, ())(, ())(() и др.

3. Редът може да съдържа скоби, както кръгли, така и квадратни. Всяка отваряща скоба съответства на затваряща скоба от същия тип (кръгла - кръгла, квадратна - квадратна). Напишете рекурсивна функция, за да проверите дали скобите са правилни в този случай.

Пример за неправилно разположение: ( [ ) ].

4. Броят на валидните скоби с дължина 6 е 5: ()()(), (())(), ()(()), ((())), (()()). Напишете рекурсивна програма за генериране на всички валидни скоби с дължина 2n.

Съвет: Коригирайте структурата на скобите с минимална дължина „()“. Структури с по-голяма дължина се получават от структури с по-малка дължина по два начина:

(a) ако по-малката структура е поставена в скоби, (b) ако две по-малки структури са написани последователно.

5. Създайте процедура, която отпечатва всички възможни пермутации за цели числа от 1 до N.

6. Създайте процедура, която отпечатва всички подмножества на набора.

7. Създайте процедура, която отпечатва всички възможни представяния на естествено число N като сбор от други естествени числа.

8. Създайте функция, която изчислява сумата на елементите на масива по следния алгоритъм: масивът се разделя наполовина, сумите на елементите във всяка половина се изчисляват и събират. Сумата от елементите в половината от масива се изчислява по същия алгоритъм, тоест отново чрез разделяне на половина. Деленията се извършват, докато получените части от масив съдържат по един елемент и съответно изчисляването на сумата стане тривиално.

Забележка: Този алгоритъм е алтернатива на метода за натрупване на суми. В случай на масиви с реални стойности, това обикновено ви позволява да получите по-малки грешки при закръгляване.

9. Програмирайте методите за бързо сортиране на масиви, описани в раздел 6.4.

10. Създайте процедура, която чертае кривата на Кох (фиг. 12).

11. Възпроизвеждане на фиг. 16. На фигурата при всяка следваща итерация кръгът е 2,5 пъти по-малък (този коефициент може да се направи параметър).