Индуктивно-рекурзивна конструкција алгоритама

Увод

Индуктивно-рекурзивна конструкција алгоритама је један од основних приступа у конструкцији алгоритама који се ослања на решавање проблема тако што га сведемо на мање инстанце истог проблема. На овом месту треба нагласити да ово звучи као наивна или школска дефиниција рекурзије, али суштина је потпуно другачија. Уместо на рекурзију, при конструкцији алгоритма ми се ослањамо на математичку индукцију, тј. на веру да ако знамо да решимо проблем димензије $n$ онда га можемо решити и за случај димензије $n+1$.

Концептуално, приликом дизајнирања алгоритма овом техником ми се ослањамо на индуктивни начин размишљања, док рекурзија представља најчешће техничко решење којим имплементирамо алгоритам. Формално:

• Математичка индукција - Доказујемо да тврђење важи за $n$ користећи претпоставку да важи за $n-1$.
• Рекурзивна конструкција - Градимо решење, тј. описујемо неопходну трансформацију којом од познатог решења за случај $n-1$ добијамо решење проблема величине $n$.

Практично правило: Никада се покушавамо да решимо проблем одједном, већ се увек фокусирамо само на то како да повежемо последњи корак са оним што је већ урађено.

У пракси, имамо три кључна корака у конструкцији алгоритма:

1. Базни случај - Дефинишемо решење за најмању могућу величину улаза. Најчешће се ради о тривијалном случају који је неопходан да би се спречило бесконачно извршавање алгоритма.
2. Индуктивна хипотеза - Претпостављамо да наш алгоритам већ савршено ради за све проблеме величине мање од $n$. Овде је кључно не доводити у питање како је решен проблем мање димензије, већ само прихватити да некако магично јесте.
3. Индуктивни корак - Индуктивни корак је срж конструкције алгоритма. У индуктивном кораку треба дефинисати како ћемо искористити постојеће решење за проблем димензије $n-1$ да бисмо добили решење проблема димензије $n$. Неколико уобичајених приступа је:
   • Додавање новог елемента на крај,
   • Разматрање или обрада последњег елемента,
   • Убацивање последњег елемента на неко конкретно место у већ обрађеном префиксу,
   • Комбиновање више мањих решења у решење целог проблема.

Илустроваћемо рекурзивну конструкцију алгоритама на примеру сортирања уметањем (енгл. insertion sort). Формално, потребно је да спроведемо следеће кораке:

1. Базни случај: - Празан низ је сортиран.
2. Индуктивна хипотеза - Низ од $n-1$ елемената је сортиран.
3. Индуктивни корак (конструкција алгоритма) - Дат нам је низ од $n$ елемената. Применом индуктивне хипотезе можемо да сортирамо префикс низа дужине $n-1$. Након сортирања, остаје нам само да у сортирани префикс на право место убацимо последњи елемент низа.

Имплементација која прати описани поступак је у наставку.

static void insertion_sort(int[] niz, int n) {
    // провера базног случаја
    if (n == 0)
        return;
    // примена индуктивне хипотезе
    insertion_sort(niz, n - 1);
    // конструкција алгоритма (индуктивни корак)
    int poslednji = niz[n-1]
    int j = n - 2;
    while (j >= 0 && niz[j] > poslednji) {
        niz[j+1] = niz[j];
        j--;
    }
    niz[j+1] = poslednji;
}

Индуктивно-рекурзивна конструкција алгоритама има неколико предности и мана:

• Предности: кратки и елегантни кодови, висока читљивост и лако разумевање алгоритама, блиско математичком формализму.
• Мане: меморијска ефикасност (сваки рекурзивни позив повлачи отварање новог стек оквира), потенцијално преклапање подпроблема које води ка експоненцијалној временској сложености.

У пракси је индуктивно-рекурзивна конструкција алгоритама прва идеја којом се тешки проблеми решавају. Касније се та решења пребацују у итеративни облик да би се смањила меморијска сложеност алгоритма и уколико постоји потреба даље се унапређују неким другим техникама за конструкцију алгоритама. Индуктивно-рекурзивну конструкцију алгоритама можемо грубо да поделимо према три уобичајена приступа у конструкцији алгоритама:

• Смањи за један - Ако је дат проблем димензије $n$, на пример низ са $n$ елемената, издвојићемо последњи елемент низа и решићемо проблем димензије $n-1$, након чега ћемо додати последњи елемент и конструисати решење проблема димензије $n$. Ово је најчешћи приступ у општем случају.
• Смањи за фактор - Полазни проблем поделимо на пола (или на трећине, четвртине итд). Решимо подпроблеме и затим та решења објединимо у решење полазног проблема. Чест приступ код подели-па-владај алгоритама.
• Променљива величина - Проблем се смањује на непредвидљив начин у зависности од улаза. Карактеристичан проблем је Еуклидов алгоритам за одређивање НЗД-а.

Репна рекурзија

Репна рекурзија је посебан облик рекурзије у којој је рекурзивни позив последња ствар коју функција ради пре него што врати вредности. Предност репне рекурзије у односу на обичну рекурзију огледа се у томе што нема преосталих операција након рекурзивног позива, тј. рекурзивни позив је уједно и коначан резултат функције.

Да бисмо илустровали разлику размотрићемо рекурзивно израчунавање факторијела датог природног броја $n$. Израчунавање факторијела можемо описaти следећом рекурентном релацијом:

$$\begin{aligned} f(n) = \begin{cases} 1, \quad & \text{za} \quad n = 1 \\ n \cdot f(n-1), \quad & \text{za} \quad n > 1 \end{cases} \end{aligned}$$

Имплементација директно следи:

static int faktorijel(int n) {
    if (n == 1)
        return 1;
    return n * faktorijel(n-1);
}

На пример, да бисмо израчунали $f(5)$ потребно је да извршимо следећи низ функционалних позива:

$$\begin{aligned} f(5) \rightarrow 5 \cdot & f(4) & & & & \downarrow\\ \rightarrow & 4 \cdot & f(3) & & & \downarrow\\ &\rightarrow & 3 \cdot & f(2) & & \downarrow\\ & & \rightarrow & 2 \cdot & f(1) & \downarrow\\ & & & \rightarrow & 1 & \end{aligned}$$

Тек у последњем функционалном позиву, тј. тек када низом свођење на проблеме мање димензије стигнемо до базног случаја, сазнајемо неку конкретну вредност. Сада се ходом уназад, тј. одмотавањем рекурзивних позива, обједињавају решења мањих проблема у решења већих:

$$\begin{aligned} f(5) \rightarrow 5 \cdot 24 & & & & = 120 & \\ \rightarrow & 4 \cdot 6 & & & = 24 & \uparrow\\ &\rightarrow & 3 \cdot 2 & & = 6 & \uparrow \\ & & \rightarrow & 2 \cdot 1 & = 2 & \uparrow\\ & & & \rightarrow & 1 & \uparrow \end{aligned}$$

Иако синтаксно елегантан, наш код није претерано ефикасан ни у временском ни у просторном смислу. Сваки рекурзивни позив отвара нови стек оквир, па је укупна просторна сложеност $O(n)$. Када је временска сложеност у питању треба приметити да извршњавање нашег програма има две одвојене фазе. Прва фаза је свођење проблеме до соновног случаја, што је шематски обележено стрелицама на доле, а друга фаза је одмотавање рекурзије, тј. конструкција решења, што је шематски обележено стрелицама на горе. Одавде се лако закључује да је временска сложеност решења $O(2n)$.

Временска сложеност се може снизити тако што бисмо рачунање могли да изменимо. Уместо да рачунамо у фази одмотавања, можемо да сваком следећем рекурзивном позиву проследимо до сада израчунати фрагмент решења. Тиме ћемо добити комплетно решење проблема када стигнемо до базног случаја. Да бисмо то постигли, треба да уведемо помоћну променљиву (акумулатор) коју ћемо прослеђивати рекурзивном позиву. Решење сада постаје:

static int faktorijel_2(int n, int acc = 1) {
    if (n == 1)
        return acc;
    return faktorijel_2(n-1, n * acc);
}

Приметимо да у овом решењу нема никакве потребе за одмотавањем рекурзије. Заједно са последњим стек оквиром смо добили коначно решење, тј. резултат. За функцију faktorijel_2 се каже да је репно рекурзивна. Шематски, извршавање репно рекурзивне функције можемо приказати на следећи начин:

$$\begin{aligned} f_2(5) \rightarrow & f_2(4, 5 \cdot 1) & & & & & \downarrow\\ & \rightarrow & f_2(3, 4 \cdot 5) & & & & \downarrow\\ & & \rightarrow & f_2(2, 3 \cdot 20) & & & \downarrow\\ & & & \rightarrow & f_2(1, 2 \cdot 60) & & \downarrow\\ & & & & \rightarrow & 120 & \end{aligned}$$

Репна рекурзија може да донесе значајно снижавање просторне сложености, јер одређени компајлери могу да уоче својство репне рекурзије и да уместо отварања нових стек оквира за сваки рекурзивни позив, користе постојећи. Тиме просторна сложеност постаје константна, а временска постаје $O(n)$, јер неће бити потребе за одмотавањем рекурзије. Овакво понашање компајлера је карактеристично за функционалне програмске језике (F#, Haskell, Scala) и није толико често када се ради о програмском језику C#.

Суштинске разлике измећу обичних и репно рекурзивних функција су следеће:

• Задња операција код репно рекурзивних функција мора бити искључиво рекурзивни позив. Код обичних рекурзивних функција може бити произвољни аритметички израз.
• Просторна сложеност код репно рекурзивних функција расте пропорционално величини улазног проблема. Просторна сложеност репно рекурзивних функција је често константна, ако компајлери могу аутоматски да изврше оптимизацију отварања стек оквира.
• Текуће стање резултата се имплицитно чува на системском стеку када се ради о обичним рекурзивним функцијама. Код репно рекурзивних функција се текуће стање резултата преноси уз помоћ аргумената функције кроз рекурзивне позиве.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу. Формално, треба да

Задатак 1

Ако су дати цели бројеви $a$ и $b$, написати рекурзивну функцију која исписује редом све целе бројеве у задатом интервалу $[a,b]$ у:

• растућем поретку;
• опадајућем поретку.

Улаз: У првој линији стандардног улаза налази се цео број $a$, а у другој је цео број $b$ $(-1000 \leq a \leq 1000, -1000 \leq b \leq 1000)$.

Излаз: На стандардном излазу исписују се редом сви цели бројеви из интервала, у свакој линији по један број, у траженом редоследу.

Решење

Да бисмо решили задатак полазни проблем можемо да поделимо на последњи број и на префикс. тј. смањићемо величину проблема за један. Да бисмо одштампали вредности у сегменту растуће, то значи следеће:

1. Базни случај - лева граница интервала је већа од десне границе интервала, тј. не треба ништа да штампамо.
2. Индуктивна претпоставка - умемо да одштампамо префикс димензије $n-1$ у растућем поретку.
3. Индуктивни корак (конструкција) - након што рекурзивно одштампамо префикс у растућем поретку, потребно је да одштампамо последњи елемент, чиме смо решили проблем димензије $n$.

Код који прати описану конструкцију је у наставку:

static void zad1_rastuci(int a, int b)
{
    // провера основног случаја
    if (a > b)
        return;
    // прво штампамо све бројеве пре текућег броја
    zad1_rastuci(a, b - 1);
    // затим штампамо текући број
    Console.WriteLine(b);
}

Да бисмо одштампали вредности у сегменту опадајуће, то значи следеће:

1. Базни случај - лева граница интервала је већа од десне границе интервала, тј. не треба ништа да штампамо.
2. Индуктивна претпоставка - умемо да одштампамо префикс димензије $n-1$ у опадајућем поретку.
3. Индуктивни корак (конструкција) - потребно је да одштампамо последњи елемент и затим да рекурзивно одштампамо префикс у опадајућем поретку, чиме смо решили проблем димензије $n$.

Код који прати описану конструкцију је у наставку:

static void zad1_opadajuci(int a, int b)
{
    // провера основног случаја
    if (a > b)
        return;
    // прво штампамо текући број
    Console.WriteLine(b);
    // затим штампамо све бројеве пре текућег броја
    zad1_opadajuci(a, b - 1);
}

Посебно обратите пажњу на редослед извршњавања рекурзивног позива и текуће операције. Ако је рекурзивни позив пре текуће операције, то је еквивалентно обрађивању података унапред. Ако је рекурзивни позив након текуће операције, то је еквивалентно обрађивању података уназад.

Задатак 2

Написати рекурзивну функцију која израчунава $n$-ти степен реалног број $x$. Рекурзивна функција треба да одреди тражени степен:

• Узастопним множењем.
• Степеновањем квадрирањем.

Улаз: У првој линији стандардног улаза уноси се реалан број $x$. У следећој линији стандардног улаза уноси се природан број $n$.

Излаз: На стандардни излаз исписати тражени степен $x^n$.

Решење

Задатак можемо врло лако да решимо смањивањем величине проблема за један. Тиме ћемо добити следећу рекурентну релацију која описује степеновање:

$$\begin{aligned} f(x, n) = \begin{cases} 1, \quad & \text{за} \quad n = 0 \\ x \cdot f(x, n - 1), \quad & \text{за} \quad n > 0 \end{cases} \end{aligned}$$

Рекурзивна имплементација директно прати рекурентну релацију.

static double zad2(double x, int n)
{
    // базни случај
    if (n == 0)
        return 1;
    // конструкција решења
    return x * zad2(x, n - 1);
}

Знајући за повећану меморијску сложеност и повећану временску сложеност као последице рекурзивне имплементације решења, можемо да имплементирамо репно-рекурзивну верзију функције. Уместо да вредности међурезултата чувамо имплицитно на системском стеку, можемо их експлицитно прослеђивати функционалним позивима кроз аргументе функције. Репно-рекурзивна имплементација је у наставку:

static double zad2_repna_rek(double x, int n, double s = 1)
{
    // базни случај
    if (n == 0)
        return s;
    // конструкција решења
    return zad2_repna_rek(x, n - 1, s * x);
}

Временска и просторна сложеност приказаних решења су $O(n)$.

Задатак можемо да решимо и другачијом поделом проблема на подпроблеме, тј. можемо добити решење које је логаритамске сложености. Покушаћемо да уочимо правилност која постоји приликом израчунавања $x^16$. Досадашња идеја би рачунала овај резултат као:

$$x^16 = x \cdot x^15 = x \cdot x \cdot x^14 = \underbrace{x \cdot x \cdot \ldots \cdot x}_{16 \quad пута}.$$

Број множења у израчунавању степена се може значајно смањити. На пример, можемо приметити следеће

$$x^16 = x^8 \cdot x^8$$

Дакле, ако бисмо знали $x^8$, тада бисмо $x^16$ добили у само једном множењу. На сличан начин, могли бисмо да применимо низ свођења:

$$\begin{aligned} x^8 & = x^4 \cdot x^4 \\ x^4 & = x^2 \cdot x^2 \\ x^2 & = x \cdot x \end{aligned}$$

Имајући ово у виду, алгоритам можемо да конструишемо на следећи начин:

$$\begin{aligned} f(x, n) = \begin{cases} 1, \quad & \text{за} \quad n = 0 \\ x \cdot f(x, \left\lfloor \frac{n}{2} \right\rfloor) \cdot f(x, \left\lfloor \frac{n}{2} \right\rfloor) , \quad & \text{за} \quad n > 0 \land n \text{ непарно} \\ f(x, \left\lfloor \frac{n}{2} \right\rfloor) \cdot f(x, \left\lfloor \frac{n}{2} \right\rfloor) , \quad & \text{за} \quad n > 0 \land n \text{ парно} \end{cases} \end{aligned}$$

Имплементација директно следи из рекурентне релације:

static double zad2_efikasno(double x, int n)
{
    // вазни случај
    if (n == 0)
        return 1;
    // конструкција решења
    double x2 = zad2_efikasno(x, n/2);
    double rez = x2*x2;
    // провера парности експонента
    return (n % 2 == 0) ? rez : (x*rez);
}

Приметите да у имплементацији само једном рекурзивно рачунамо $x^{\left\lfloor \frac{n}{2} \right\rfloor}$ и затим користимо ту вредност приликом рачунања $x^n$. Временска и просторна сложеност решења су $O(\log n)$.

Задатак 3

Корисник уноси један природан број $n$. Написати рекурзивну функцију која одређује:

• збир цифара датог броја,
• број цифара у запису датог броја,
• максималну цифру у запису броја,
• минималну цифру у запису број,
• број различитих цифара у запису броја.

Улаз: Са стандардног улаза се уноси природан број $n$ ($1 \le n \le 10^9$).

Излаз: На стандардни излаз исписати тражене вредности.

Решење

Да бисмо одредили збир цифара, можемо да применимо исти поступак као и до сада. Смањићемо величину полазног проблема за један, тј. претпоставићемо да знамо да израчунамо збир префикса и решење ћемо добити сабирањем тог резултата са цифром најмање тежине у броју. Описани поступак можемо да опишемо рекурентном релацијом:

$$\begin{aligned} f(x) = \begin{cases} 0, \quad & \text{за} \quad x = 0 \\ x \% 10 + f(x/10), \quad & \text{за} \quad x > 0 \end{cases} \end{aligned}$$

Имплементација директно следи из рекурентне релације:

static int zbir_cifara(int n)
{
    // базни случај
    if (n == 0)
        return 0;
    // рекурзивно одређујемо збир цифара
    return n%10 + zbir_cifara(n/10);
}

Да бисмо одредили број цифара, можемо да применимо сличан поступак као за рачунање збира цифара. Смањићемо величину полазног проблема за један, тј. претпоставићемо да знамо да израчунамо број цифара у префиксу и решење ћемо добити сабирањем тог резултата са јединицом. Описани поступак можемо да опишемо рекурентном релацијом:

$$\begin{aligned} f(x) = \begin{cases} 0, \quad & \text{за} \quad x = 0 \\ 1 + f(x/10), \quad & \text{за} \quad x > 0 \end{cases} \end{aligned}$$

Имплементација директно следи из рекурентне релације:

static int broj_cifara(int n)
{
    // базни случај
    if (n == 0)
        return 0;
    // рекурзивно одређујемо број цифара
    return 1 + broj_cifara(n/10);
}

Да бисмо одредили максималну цифру броја, смањићемо величину полазног проблема за један, тј. претпоставићемо да знамо да израчунамо максимум у префиксу и решење ћемо добити упоређивањем тог резултата са цифром најмање тежине. Решење проблема ће бити већи од та два броја. Треба само водити рачуна да је базни случај једноцифрени број. Описани поступак можемо да опишемо рекурентном релацијом:

$$\begin{aligned} f(x) = \begin{cases} x, \quad & \text{за} \quad 0 \le x \le 9 \\ \max ( x \% 10, f(x/10)), \quad & \text{за} \quad x > 9 \end{cases} \end{aligned}$$

Имплементација директно следи из рекурентне релације:

static int max_cifra(int n)
{
    // базни случај
    if (0 <= n && n < 10)
        return n;
    // рекурзивно рачунамо решење префикса
    int max = max_cifra(n / 10);
    int c = n % 10;
    // упоређујемо текућу цифру са резултатом префикса
    return c > max ? c : max;
}

Аналогно одређујемо минималну цифру.

$$\begin{aligned} f(x) = \begin{cases} x, \quad & \text{за} \quad 0 \le x \le 9 \\ \min ( x \% 10, f(x/10)), \quad & \text{за} \quad x > 9 \end{cases} \end{aligned}$$

static int min_cifra(int n)
{
    // базни случај
    if (0 <= n && n < 10)
        return n;
    // рекурзивно рачунамо решење префикса
    int min = min_cifra(n / 10);
    int c = n % 10;
    // упоређујемо текућу цифру са резултатом префикса
    return c < min ? c : max;
}

Да бисмо одредили колико различитих цифара има у запису броја, треба нам елегантан начин да одржавамо информацију колико смо до сада нашли различитих цифара. Најефикаснија структура података за тако нешто је HashSet(), јер омогућава додавање и проверу да ли је елемент у скупу у константном времену.

С обзриом да решење конструишемо од цифре најмање тежине ка цифри највеће тежине, природно је да текући резултат пропагирамо кроз аргументе функције, па ће имплементација бити репно-рекурзивна.

static int broj_razlicitih_cifara(int n)
{
    // помоћна структура у којој чувамо цифре на које смо наишли    
    HashSet<int> cifre = new HashSet<int>();
    // позив помоћне функције која рачуна број различитих цифара
    return broj_razlicitih_cifara(n, cifre, 0);
}
static int broj_razlicitih_cifara(int n, HashSet<int> cifre, int s)
{
    // када искористимо све цифре, резултат је у аргументу s
    if (n == 0)
        return s;
    // издвајамо цифру и проверавамо да ли је у скупу
    int c = n / 10;
    if (cifre.Contains(c) == false)
    {
        // ако није, додајемо је у скуп и увећавамо бројач
        cifre.Add(c);
        s = s + 1;
    }
    // рекурзивно одређујемо број различитих цифара у префиксу
    return broj_razlicitih_cifara(n/10, cifre, s);
}

Временска и просторна сложеност свих приказаних решења су линеарне.

Задатак 4

Перици недостаје само сличица са бројем $x$ да би попунио читав албум. Перица је у својој колекцији поседовао један изузетно редак дупликат и договорио се са колегом скупљачем сличица да ће му дати свој вредан дупликат ако му колега преда све своје дупликате у замену. Колега је пристао на такву замену и Перица је добио гомилу сличица. Замолио нас је да напишемо програм који треба да утврди да ли се у добијеном скупу сличица налази тражена сличица $x$.

Улаз: У првој линији стандардног улаза налази учитава се природан број $x$, у следећој линији се учитава природан број $n$ ($1 \le n \le 50000$) који представља укупан број сличица које је Перица добио у замени, а затим се у свакој од наредних $n$ линија стандардног улаза учитава по један природан број.

Излаз: У једној линији стандарног излаза исписати Da ако је Перица добио тражену сличицу, иначе исписати Ne.

Решење

Из текста задатка је јасно да се ради о обичној линеарној претрази. Проблем можемо решити свођењем на проблем који је истог типа, али за један мањи. Упоређујемо последњи елемент низа са траженом вредности. Ако смо нашли тражену вредност, прекидамо даљу претрагу. Ако нисмо нашли, претрагу рекурзивно настављамо у префиксу низа и враћамо резултат претраге. Базни случај је празан низ.

Рекурзивна имплементација линеарне претраге је у наставку:

static int linearna_pretraga(int[] niz, int n, int x)
{
    // базни случај, празан низ
    if (n == 0)
        return -1;
    // ако смо нашли елемент, прекидамо претрагу
    if (niz[n-1] == x)
        return n - 1;
    // ако нисмо, резултат ће бити исход претраге у префиксу
    return linearna_pretraga(niz, n-1, x);
}

Временска и просторна сложеност су линеарне.

Задатак 5

Перица је у продавници купио $n$ артикала. Написати програм који ће одредити укупан износ рачуна, као и цену најскупљег артикла који је Перица купио.

Улаз: Са стандардног улаза се учитава број $n$ ($1 \le n \le 10^6$), а затим се у наредних $n$ линија учитавају реални бројеви који представљају цене артикала које је Перица купио.

Излаз: На стандардни излаз исписати два реална броја раздвојена једним размаком, укупан рачун и цену најскупљег артикла редом.

Решење

Очигледан и исправан приступ јесте да напишемо две рекурзивне функције. Једну за израчунавање износа рачуна, тј. збира целог низа и другу за одређивање најскупљег артикла. Поступак којим то радимо је идентичан поступку којим смо рачунали збир цифара и максималну цифру броја. Разлика је само у томе, што као аргумент функције морамо да проследимо текућу дужину префикса за који треба да израчунамо тражене статистике. Решење је у наставку:

static double max(double[] niz, int n)
{
    // базни случај
    if (n == 1)
        return niz[0];
    // конструкција решења
    int m = max(niz, n - 1);
    return niz[n-1] > m ? niz[n-1] : m;
}
static double zbir(double[] niz, int n)
{
    // базни случај
    if (n == 0)
        return 0;
    // констукција решења
    return niz[n-1] + zbir(niz, n - 1);
}

С обзиром да смо упознати са концептом репно-рекурзивних функција можемо да напишемо једну репно-рекурзивну функцију која ће у једном пролазу одредити обе статистике. Као и да сада, у случају репно-рекурзивних функција, међурезултате ћемо прослеђивати као аргументе функционалним позивима. Решење је у прилогу:

static Tuple<double, double> zbir_max(double[] niz, int n, 
                                        double zbir = 0, double max = double.MinValue)
{
    // базни сллучај у којем враћамо комплетно решење
    if (n == 0)
        return Tuple.Create(zbir, max);
    // смањивање проблема за један и пропагација међурезултата
    int m = niz[n-1] > max ? niz[n-1] : max;
    return zbir_max(niz, ni-1, zbir + niz[n-1], m);
}

Напомена: Иако репно-рекурзивно решење на први поглед делује елегантније, оно није исправно, јер не прати правила лепог кодирања. Функције које пишемо треба да решавају искључиво један проблем, а не да буду “франкенштајни” који решавају више проблема истовремено. Иако примамљива, франкенштајн решења су тешка за дебаговање и одржавање.

Задатак 6

У школи малих жутих мрава наставник је прегледао контролни задатак. Прво је прегледао ђаке који су радили групу $A$, а затим оне који су радили групу $B$, средио је резултате за сваку групу и мраве поређао на основу броја поена који су освојили. Напиши програм који му помаже да од уређеног списка ученика који су радили задатке из групе $A$ и од уређеног списка ученика који су радили задатке из групе $B$ добије јединствен уређен списак свих ученика.

Улаз: Са стандардног улаза се уноси број ђака $m$ који су радили групу $A$ ($5 \le m \le 25000$), а затим неопадајуће сортиран низ поена тих ђака (елементи су у једној линији, раздвојени са по једним размаком). Након тога се уноси број $n$ ђака који су радили групу $B$ ($5 \le n \le 25000$), a затим неопадајуће сортиран низ поена тих ђака (елементи су у једној линији, раздвојени са по једним размаком).

Излаз: На стандардни излаз исписати неопадајуће сортирани низ поена свих ђака заједно, раздвојених са по једним размаком.

Решење

Итеративна имплементација алгоритма за обједињавање сортираних низова нам је позната од раније, јер смо овај проблем већ решили уз помоћ два показивача. Вежбе ради, решићемо исти проблем индуктивно-рекурзивном конструкцијом алгоритама.

Нека је са $m$ обележена дужина низа $А$ и нека је са $n$ обележена дужина низа $B$, тада ће укупна дужина низа $C$ бити $m+n$, што је заправо величина нашег проблема. Конструкција решења може бити следећа:

1. Базни случај - Празан низ је исправно обједињен.
2. Индуктивна хипотеза - Умемо правилно да објединимо два низа укупне дужине $n+m-1$.
3. Индуктивни корак (конструкција решења) - Полазнни низ $c$ је димензије $n+m$ и можемо да применимо следећу тактику: На место $c_0$ поставићемо мањи од бројева $a_0$ и $b_0$, чиме ћемо проблем свести на обједињавање суфикса дужине $n+m-1$, што је проблем димензије $n+m-1$ који према индуктивној хипотези умемо да решимо. Дакле, имаћемо следеће случајеве:
   • $a_0 < b_0$ - У овом случају, након уписивања елемента $a_0$ на позицију $c_0$ остаје на да објединомо низове $a_{1, \ldots, m-1}$ и $b_{0, \ldots , n - 1}$.
   • $a_0 \ge b_0$ - У овом случају, након уписивања елемента $b_0$ на позицију $c_0$ остаје на да објединомо низове $a_{0, \ldots, m-1}$ и $b_{1, \ldots , n - 1}$.

Да бисмо имплементирали алгоритам, потребна су нам три бројача:

• $i$ - одређује текућу позицију у низу $A$, $0 \le i < m$
• $j$ - одређује текућу позицију у низу $B$, $0 \le j < n$
• $k$ - одређује текућу позицију у низу $C$, $0 \le k < m+n$

У сваком рекурзивном позиву увећаваћемо $k$ за један и тачно један од бројача $i$ и $j$. Рекурзивно решење је у наставку:

static void objedini(int[] a, int[] b, int[] c, int i = 0, int j = 0, int k = 0) 
{
    if (i < a.Length && j < b.Length) 
    {
        if (a[i] < b[j]) {
            c[k] = a[i];
            objedini(a, b, c, i + 1, j, k + 1);
        }
        else {
            c[k] = b[j];
            objedini(a, b, c, i, j + 1, k + 1);
        }
    }
    else if (i < a.Length) 
    {
        c[k] = a[i];
        objedini(a, b, c, i + 1, j, k + 1);
    }
    else if (j < b.Length) 
    {
        c[k] = b[j];
        objedini(a, b, c, i, j + 1, k + 1);
    }
}

Треба приметити да у рекурзивној верзији решења, имплицитно користимо системски стек да бисмо симулирали извршавање петље. У пракси, наравно ово никада не бисмо радили. Рекуривно решење је овде наведено само као илустрација размишљања.

Задатак 7

Уносе се масе предмета, одредити разлику суме маса предмета до првог појављивања предмета највеће масе и суме маса предмета после првог појављивања предмета највеће масе (предмет највеће масе није укуључен ни у једну суму).

Улаз: У првој линији стандардног улаза налази се број предмета $n$ $(1 \le n \le 50000)$. Свака од наредних $n$ линија садржи по један природан број из интервала $[1, 50000]$, ти бројеви представљају масе сваког од $n$ предмета.

Излаз: У првој линији стандарног излаза приказати тражену разлику маса.

Решење

Као и до сада, задатак можемо решити свођењем на проблем чија је димензија за један мања од полазног проблема. Потребно је да приликом тог свођења одржавамо текући максимум и збирове пре и после максимума. Дакле, кроз низ ћемо пролазити уназад и резултате елемената које смо до сада прошли ћемо одржавати кроз аргументе функције. Задатак можемо врло елегантно решити репно-рекурзивном функцијом.

Приликом разматрања текућег елемента на позицији $i$ у низу, имамо следеће познате информације:

• максимум суфикса, јер смо га већ обрадили
• збир пре максимума у суфиксу
• збир након максимума у суфиксу

Конструкција је следећа:

• ако је текући елемент мањи или једнак од максимума, увећавамо збир пре максимума и рекурзивно обрађујемо префикс.
• ако је текући елемент већи од максимума, тада он постаје нови максимум, збир после максимума увећавамо за текући елемент и стари збир пре максимума и на крају збир пре максимума постаје 0.
• ако је низ празан, тада смо конструисали решење и враћамо вредности збира пре и збира после максимума.

Репно-рекурзивно решење је у наставку:

static Tuple<int,int> zbirPrePosleMax(int[] niz, int n, int max, int zbirPre, int zbirPosle) 
{
    // ако смо прошли кроз све елементе, решили смо проблем и враћамо резултат
    if (n == 0)
        return Tuple.Create(zbirPre, zbirPosle);
    // упоређујемо последњи елемент и максимум суфикса.
    // ако је текући елемент мањи или једнак
    if (niz[n-1] <= max)
        // ажурирамо вредност променљивих и рекурзивно обрађујемо префикс низа
        return zbirPrePosleMax(niz, n - 1, max, zbirPre + niz[n-1], zbirPosle);
    else 
        // ако је текуђи елемент већи од максимума суфикса, ажурирамо максимум,
        // ажурирамо вредности збирова и рекурзивно обрађујемо префикс низа
        return zbirPrePosleMax(niz, n-1, niz[n-1], 0, zbirPre + niz[n-1] + zbirPosle)ч
}
static Tuple<int,int> zbirPrePosleMax(int[] niz, int n) 
{
    // на почетку, максимум је једнак последњем елементу низа и збирови су 0
    return zbirPrePosleMax(niz, n-1, niz[n-1], 0, 0);
}

Задатак 8

Дате су просечне оцене $n$ ученикa једног одељења. Написати програм којим се одређује просек просечних оцена свих одличних ученика тог одељења.

Улаз: Прва линија стандарног улаза садржи природан број $n$ $(1 \le n \le 100)$ који представља број ученика. У наредних $n$ линија налази се по један реалан број из интервала $[2, 5]$. Ти бројеви представљају просеке ученика.

Излаз: У првој линији стандарног излаза приказати просек просечних оцена одличних ученика одељења заокружен nа две децимале. Ако одличних ученика нема приказати -.

Решење

Примењујемо стандардну конструкцију смањи за један. Уколико последњи елемент низа представља одличан просек, додајемо га на текући збир и рекурзивно обрађујемо префикс. Ако последњи елемент није одличан просек, задржавамо стари збир и прелазимо на обрађивање префикса. Како смо прошли кроз цео низ, добијени збир треба да поделимо бројем одличних.

С обзиром да низ обрађујемо уназад и да све време ажурирамо текуђе резултате, репно-рекурзивна функција је решење.

static double prosek_odlicnih(double[] niz, int n, double zbir = 0, int brojOdlicnih = 0) 
{
    // када прођемо кроз цео низ, рачунамо просек. 
    if (n == 0)
        return n != 0 ? (zbir/brojOdlicnih) : 0;
    // ако је последњи елемент одличан
    if (niz[n-1] >= 4.5)
        // увећавамо збир и број одличних и рекурзивно обрађујемо префикс
        return prosek_odlicnih(niz, n - 1, zbir + niz[n-1], brojOdlicnih + 1);
    else 
        // ако није, не мењамо старе вредност и рекурзивно обрађујемо префикс
        return prosek_odlicnih(niz, n - 1, zbir, brojOdlicnih);
}

Задатак 9

Становници једне дугачке улице желе да одреде положај на којем ће бити направљена антена за мобилну телефонију. Пошто желе да локацију одреде на најправеднији могући начин, договорили су се да антену саграде на месту на ком ће збир растојања свих оних који се налазе лево од антене до ње, бити једнак збиру растојања свих оних који се налазе десно од антене до ње. Ако су познате координате свих кућа у улици (можемо замислити да су то координате тачака на једној правој), написати програм који одређује положај антене.

Улаз: Са стандардног улаза у првој линији се уноси природан број $n$ $(1 \le n \le 100)$ који представља број станара, а у наредних $n$ линија реални бројеви (од $−1000$ до $1000$) који представљају координате станара ($x$ координате тачака на оси).

Излаз: На стандардни излаз исписати један реалан број који представља тражени положај антене (допуштена је толеранција грешке $10^{-5}$).

Решење

Једно могуће решење је уз помоћ бинарне претраге оптималне вредности. Треба да поставимо антену тако да разлика растојања са леве и растојања са десне стране буде што је могуће мања. Прво треба да одредимо интервал у којем вршимо претрагу. Лева граница интервала биће најмања координате куће, а десна граница интервала ће бити максимална координата куће.

Након одређивања граница, потребно је да проблем прво преведемо у проблем одлучивања. Дакле, за дати положај антене треба да одредимо да ли је то решење исправно или не. Проблем који постоји овде јесте на који начин усмерити претрагу. Можемо да користимо разлику збира растојања лево од антене и збира растојања десно од антене. Ако је та разлика позитивна, тада антену треба да померимо у лево, ако је разлика негативна, тада антену треба да померимо у десно. Овим добијамо поделу простора претраге која има следећи облик:

$$----------------++++++++++++++++++$$

И наше решење ће заправо бити преломна тачка. Решење проблема које користи бинарну претрагу је у наставку:

static double max_niza(double[] niz, int n) 
{
    if (n == 1)
        return niz[0];
    double max = max_niza(niz, n-1);
    return max > niz[n-1] > max ? niz[n-1];
}
static double min_niza(double[] niz, int n) 
{
    if (n == 1)
        return niz[0];
    double min = min_niza(niz, n-1);
    return min <> niz[n-1] > min ? niz[n-1];
}
static double razlike_rastojanja(double[] niz, int n, double m, double zbirLevo, double zbirDesno) 
{
    // ако смо прошли кроз цео низ, враћамо разлику збирова
    if (n == 0)
        return zbirLevo - zbirDesno;
    // у зависности од положаја антене и куће, увећавамо одговарајући збир
    if (niz[n-1] < m)
        return razlike_rastojanja(niz, n - 1, zbirLevo + (m - niz[n-1]), zbirDesno);
    else 
        return razlike_rastojanja(niz, n-1, zbirLevo, zbirDesno + (niz[n-1] - m));
}
static double polozaj_antene(double[] niz, double l, double d) 
{
    // ако су лева и десна граница довољно близу, одредили смо решење
    if (Math.Abs(l - d) < 10e-6)
        return (l + d)/2;
    // одређујемо средину интервала 
    double m = l + (d-l)/2;
    // рачунамо разлику растојања за дати положај антене
    double razlika = razlike_rastojanja(niz, niz.Length, m, 0, 0);
    // ако је разлика довољно мала, одредили смо решење
    if (Math.Abs(razlika) < 10e-6)
        return m;
    // ако је разлика негативна, претрагу настављамо у десној половини
    else if (razlika < 0)
        return polozaj_antene(niz, m, d);
    // ако је разлика позитивна, претрагу настављамо у левој половини. 
    else
        return polozaj_antene(niz, l, m);
}
static double polozaj_antene(double[] niz) 
{
    // одређујемо границе интервала претраге
    double min = min_niza(niz, n);
    deouble max = max_niza(niz, n);
    // решавамо проблем
    return polozaj_antene(niz, min, max);
}

Све функције у претходном решењу су написане рекурзивно ради вежбе. Укупна временска сложеност приказаног решења је $O(n \log n)$, а просторна је $O(n)$. Итеративно решење је просторно ефикасније, док временска сложеност остаје непромењена.

Задатак можемо да решимо и значајно једноставније, ако се мало детаљније позабавимо анализом проблема. Ако са $m$ обележимо тренутни положај антене, наш задатак је да одредимо $m$ такво да разлика растојања лево и десно буде 0, тј.

$$\sum_{i, a_i < m} (m - a_i) = \sum_{j, a_j \ge m} (a_j - m)$$

Збирови су коначни, па можемо сва појављивања $m$ да пребацимо на једну страну и сва појављивања $a_i$ да пребацимо на другу страну. Ако број сабирака са леве стране обележимо са $k$ и број сабирака са десне стране обележимо са $l$, добићемо:

$$(k+l)m = \sum_{j, a_j \ge m} a_j + \sum_{i, a_i < m} a_i.$$

Јасно је да важи $(k+l)=n$ и да са десне стране имамо збир свих елемената низа, тј.

$$nm = \sum_{i = 0}^{n - 1} a_i.$$

Прецизније, $m$ које је решење проблема је заправо просек координата:

$$m = \frac{1}{n} \sum_{i = 0}^{n - 1} a_i$$

Репно-рекурзивна функција која одређује просек је дата у наставку:

static double polozaj_antene(int[] niz, int n, double zbir = 0) {

    if (n == 0)
        return zbir / niz.Length;

    return polozaj_antene(niz, n - 1, zbir + niz[n-1]);
}

Временска и просторна сложеност упрошћеног решења су линеарне.

Задатак 10

Грејов кôд реда $n$ подразумева ређање свих $n$-тоцифрених бинарних записа тако да се свака два суседна записа разликују тачно у једном биту (при чему ово важи и за први и последњи запис, тако да се може сматрати да су сви записи поређани у круг). Грејов кôд дужине $0$ садржи само један елемент и то празну ниску. Грејов кôд дужине $n+1$ се може добити од кода дужине $n$ тако што се испред сваког броја у коду дужине $n$ допише цифра $0$, затим се редослед елемената у коду дужине $n$ обрне и на сваком броју се на почетак допише цифра $1$ и два тако добијена низа бројева се споје. Нпр. Грејов кôд реда $2$ је:

$$\begin{aligned} 00 \\ 01 \\ 11 \\ 10 \\ \end{aligned}$$

На основу претходног поступка добијамо Грејов кôд реда $3$.

$$\begin{aligned} \quad & \quad & k \quad \quad \quad\\ 000 \quad & \ \ | \quad & 0: \quad 000\\ 001 \quad & \ \ | \quad & 1: \quad 001\\ 011 \quad & \ \ | \quad & 2: \quad 011\\ 010 \quad & \downarrow \quad & 3: \quad 010\\ 110 \quad & \uparrow \quad & 4: \quad 110\\ 111 \quad & \ \ | \quad & 5: \quad 111\\ 101 \quad & \ \ | \quad & 6: \quad 101\\ 100 \quad & \ \ | \quad & 7: \quad 100 \end{aligned}$$

Написати програм који за дату дужину кода $n$ и дату позицију $k$ $(0 \le k \le 2n )$ одређује бинарни број који се налази на позицији $k$ у коду дужине $n$.

Улаз: Са стандардног улаза се учитава дужина кода $n$ $(1 \leq n \leq 32)$ и позиција $k$ $(0 \leq k \leq 2^{n})$.

Излаз: На стандардни излаз исписати тражени бинарни број.

Решење

За унето $n$, Грејов код ће бити дужине $2^n$, па мора важити $0 \le k < 2^n$. Функцију која одређује $k$-ти елемент Грејовог кода можемо лако дефинисати рекурзивно:

1. Ако је $n = 0$, тада је ниска која представља Грејов код празна.
2. У супротном, претпотавићемо да већ умемо да израчунамо Грејов код дужине $n-1$ и да само треба да га проширимо водећом $0$ или $1$. Из уводног примера се лако види да треба да разликујемо елементе у горњој и доњој половини листе кодова. С обзиром да укупно имамо $2^n$ кодова, кодови у горњој половини ће бити они са редним бројевима $0 \le k < 2^{n-1}$, док ће кодови у доњој половини бити на позицијама $2^{n-1} \le k < 2^n$. У рекурзивном кораку разликујемо два случаја:
   • Када је $0 \le k < 2^{n-1}$, тада се враћа Грејов код дужине $n-1$ на позицији $к$ допуњен почетном $0$.
   • Када се $2^{n-1} \le k < 2^n$ , тада се враћа Грејовв код дужине $n-1$ на позицији $k - 2^{n-1}$ допуњен почетном $1$. Изразом $k - 2^{n-1}$ враћамо редни број позиције на интервал $[0, 2^{n-1})$ и уједно обрћемо редослед већ генерисаних елемената. Може се показати да је вредност $k - 2^{n-1}$ идентична као $2^n - 1 - k$, што ћемо користити у имплементацији.

Ради једноставности, израчунавање степена двојке ћемо радити битовским операцијама и резултате ћемо представљати као стрингове. Стрингови са којима радимо су кратки, па надовезивање можемо посматрати као константне операције. Рекурзивно решење је у наставку:

static string grejov_kod(int n, uint k) 
{
    if (n == 0)
        return "";
    if (k < (1u << (n-1)))
        return "0" + grejov_kod(n-1, k);
    else 
        return "1" + grejov_kod(n-1, (uint)((1u << n) - 1 - k));
}

Задатак 11

Од три дата штапа, на једном је $n$ дискова различитих величина, а остала два су празна. Дискови на првом штапу су поређани по величини, то јест тако да је диск величине $n$ на дну, на њему је диск величине $n − 1$ итд. све до диска величине $1$, који је на врху. Потребно је дискове преместити са првог на трећи штап користећи што мање премештања. При томе треба премештати дискове један по један и стављати само мањи диск на већи, а никако обрнуто (није дозвољено стављати већи диск преко мањег). На пример, ако је $n = 3$, редослед премештања треба да буде:

• диск величине $1$ са штапа $1$ на штап $3$
• диск величине $2$ са штапа $1$ на штап $2$
• диск величине $1$ са штапа $3$ на штап $2$
• диск величине $3$ са штапа $1$ на штап $3$
• диск величине $1$ са штапа $2$ на штап $1$
• диск величине $2$ са штапа $2$ на штап $3$
• диск величине $1$ са штапа $1$ на штап $3$.

Написати програм који за дати број дискова $n$ исписује редослед премештања.

Улаз: Са стандардног улаза се учитава број штапова $n$ $(1 \le n \le 10)$.

Излаз: На стандардни излаз за свако премештање једног диска исписати по један ред, у коме се наводи редни број штапа са чијег врха се диск премешта и редни број штапа на чији врх се диск премешта, раздвојене једним размаком.

Решење

Као и до сада, задатак можемо да решимо рекурзивно техником смањивањa за један. Претпоставићемо да знамо да решимо задатака за мање од $n$ дискова. С обзиром да су нам дата три штапа, на једном од њих морају бити поређани дискови, на други треба да пребацимо дискове и трећи штап ћемо користити као помоћни.

Нека су дискови на штапу 1 и нека је задатак да их пребацимо на штап 3 користећи штап 2 као помоћни. Ослонићемо се на индуктивну претпоставку која каже да умемо да пребацимо $n-1$ дискова и применићемо следећи поступак:

1. Познатим поступком преместимо $n-1$ дискова са штапа 1 на штап 2 користећи штап 3 као помоћни.
2. Пребацимо највећи диск са штапа 1 на штап 3.
3. Познатим поступком преместимо $n-1$ дискова са штапа 2 на штап 3 користећи штап 1 као помоћни.

Функција мора имати 4 аргумента: број дискова, редни број штапа са којег пребацујемо дискове, редни број штапа на који пребацујемо штапове, редни број штапа који користимо као помоћни.

Рекурзивна функција која решава проблем је у наставку:

static void hanojske_kule(int n, int sa, int pom, int na) 
{
    if (n > 0) 
    {
        hanojske_kule(n - 1, sa, na, pom);
        Console.WriteLine("{0} {1}", sa, na);
        hanojske_kule(n-1, pom, sa, na);
    }
}

Временска сложеност приказаног алгоритма је експоненцијална.