Rekurzia (riešené príklady)

Algoritmy a programovanie - zbierka úloh

---

Štruktúry

Rekurzia

Dynamická alokácia pamäti

Vyhľadávanie

Triedenie

Lineárny zoznam

Binárny strom

Numerické algoritmy

Najväčší spoločný deliteľ

Zadanie Nájdite rekurzívny vzťah v Euklidovom algoritme pre výpočet najväčšieho spoločného deliteľa a využite ho vo funkcii, ktorá bude počítať najväčší spoločný deliteľ dvoch čísel, uvedených ako jej parametre. Funkciu použite v programe, ktorý načíta dve čísla a napíše hodnotu ich najväčšieho spoločného deliteľa.

Poznámka: V Euklidovom algoritme môžete namiesto klasického odpočítavania využiť zvyšok po delení, čo zníži počet krokov výpočtu a nebude potrebné sa zaoberať problémom „nesprávneho poradia“ čísel pri odpočítavaní.

Vzorové príklady

vstup		výstup
36 48	->	12
576 284	->	4
2553 7215	->	111

Analýza riešenia

Hľadaný rekurzívny vzťah je vidieť v postupe prevodu čísel postupným „modulovaním“ (operáciou modulo) – delenec a je nahradený deliteľom b, deliteľ b zase výsledkom a%b, ukončenie je pri nulovom b:

• NSD(a, b) = NSD(b, a%b) pre b>0,
• NSD(a, 0) = a

Možné riešenie:

 1 #include <iostream.h>
 2 
 3 int NSD(int a, int b)
 4 {
 5    if (b == 0) return a;
 6    return NSD(b, a%b);
 7 }
 8 
 9 int main()
10 {
11    int a, b;
12    cin >> a >> b;
13    cout << NSD(a, b);
14 return 0;
15 }

Fibonacciho postupnosť

Zadanie Pre Fibonacciho postupnosť platí, že hodnota ďalšieho jeho prvku je súčtom dvoch predchádzajúcich. Zostavte program, ktorý bude z klávesnice čítať čísla n, kým nenačíta nulu a pre každé číslo n vypíše n-té Fibonacciho číslo v poradí, za predpokladu, že Fib(0) = 0 a Fib(1) = 1.

Vzorové príklady

vstup		výstup
4	->	3
9	->	34
20	->	6765
40	->	102334155
0	->

Analýza riešenia

Fibonacciho postupnosť je rekurzívne definovaná ako:

• fib(0)=0
• fib(1)=1
• fib(i)=fib(i-1)+fib(i-2), pre i>1

Na tomto príklade je vhodné demonštrovať, čo sa stane, ak zabudneme v rekurzívnej funkcii uviesť podmienku pre ukončenie rekurzie – program havaruje kvôli pretečeniu zásobníka.

Možné riešenie:

 1 #include <iostream.h>
 2 long fib(int n)
 3 {
 4   if (n < 2) return n;
 5   else return fib(n-1) + fib(n-2);
 6 }
 7 int main()
 8 {
 9    int n;
10    cin >> n;
11    while (n)
12    {
13       cout << fib(n) << endl;
14       cin >> n;
15    }
16    return 0;
17 }

Prevod čísel z 10-vej sústavy

Zadanie

Zostavte program, ktorý bude prevádzať prirodzené čísla do ľubovoľných číselných sústav so základom Z<10, využitím rekurzívnej funkcie. Túto funkciu postupne zdokonaľujte:

1. Funkciu vylepšite, aby vedela prevádzať aj do sústav so základom Z<=16.
2. Upravte funkciu tak, aby vedela prevádzať všetky celé čísla (čiže aj záporné a nulu).
3. Pokúste sa funkciu obohatiť o prevod reálnych čísel (čiže aj desatinných).

V programe načítajte 2 vstupné údaje: číslo N v 10-vej sústave a základ novej sústavy z.

Vzorové príklady

vstup	výstup
80 2	1010000
93 16	5D
0 8	0
-74 4	-1022
3.141592654 16	3.243F6A8A48AA
-0.1 2	-0.0001100110011001100

Je vhodné začať jednoduchou funkciou na prevod prirodzeného čísla. Ak máme základ cieľovej sústavy z<10, môžeme problém vyjadriť aj rekurentným vzťahom v matematickom tvare: P(n, z) = P(n/z, z) * 10 + n%z (pre n > 0), a teda by bolo možné vytvoriť funkciu, ktorej návratovou hodnotou by bolo celé číslo.

V prípade, že uvažujeme o vyššom základe, vo výsledku sa objavia aj symboly A, B, C, ... funkcia by už musela výsledok vracať vo forme reťazca. Pre zjednodušenie nám stačí funkcia, ktorá bude výsledok priamo vypisovať. Je treba si uvedomiť, ako sa počíta prevod čísla – číslo vydelíme základom sústavy, tento podiel prevedieme a za ním bude nasledovať zvyšok po pôvodnom delení.

Na vypísanie zvyšku pre vyššie sústavy by sme mohli pre zvyšky väčšie ako 9 použiť aj inkrementáciu znakového typu:

cout << char (‘A’ + n%z – 10);

Keďže základ sústavy sa počas celého prevodu samozrejme nemení, nemá význam v každom volaní funkcie vytvárať jeho kópiu v podobe vstupnej premennej, ale stačí nám referencia (ušetrí sa pár bajtíkov pri každom vnorení).

Ak chceme, aby funkcia dokázala prevádzať aj nulu a záporné čísla, musíme si pridať akúsi „úvodnú“ funkciu, ktorá ošetrí problematické situácie a až potom zavolá hlavnú rekurzívnu funkciu prevodu.

Možné riešenie:

#include <iostream.h>

const char znaky[] = "0123456789ABCDEF";
void PrevodCele(int n, int &zaklad)
{
   if (n == 0) return;
   PrevodCele(n/zaklad, zaklad); // prevedie celu cast podielu
   cout << znaky[n%zaklad]; // za tym napise zvysok
}

void PrevodReal(double r, int &zaklad, int presnost)
{
   if (r == 0) return;
   r *= zaklad; // posunie o jeden rad vlavo
   cout << znaky[int(r)]; // celu cast vypise
   PrevodReal(r - int(r), zaklad, presnost - 1); // zvysok prevedie
}

// uvodna funkcia na specialne pripady
void Prevod(double r, int zaklad, int presnost)
{
   // ak je zaporne
   if (r < 0)
   {
      r = -r; cout << '-';
   }
   // cela cast
   int n = int(r);
   if (n) 
      PrevodCele(n, zaklad);
   else 
      cout << 0; // ak je nula, vypise ju

   // desatinna cast (ak je)
   if (r -= n)
   {
      cout << '.';
      PrevodReal(r, zaklad, presnost);
   }
}

int main()
{
   double r;
   int sustava;
   cout << "cislo v 10-kovej sustave: "; cin >> r;
   cout << "cielova sustava: "; cin >> sustava;
   cout << "prevedene: ";
   Prevod(r, sustava, 6);
  return 0;
}

Prvočísla

Zadanie:

Pomocou rekurzívneho riešenia vytvorte funkciu, ktorá otestuje, či je dané číslo prvočíslo.

Prvé riešenie - neoptimalizované

Analýza riešenia:

Testujeme číslo n na prvočíselnosť. Číslo n budeme postupne deliť číslami od 2 až po (n-1) aby sme zistili zvyšok po delení. Pri prvom zvyšku, ktorý je rovný 0 (teda číslo z delí číslo n bezo zvyšku) funkciu ukončíme a vrátime hodnotu 0 (n nie je prvočíslo). Ak je z<(n-1) tak funkciu is_prime1 voláme rekurzívne a v tomto volaní zvýšime parameter z o 1. (riadok č. 8). V prípade, že neplatí rovnosť z<(n-1) a ani jedno číslo z intervalu <2,n-1> nedelí číslo n bezo zvyšku, vrátime hodnotu 1 (n je prvočíslo).

Možné riešenie:

 1 int is_prime1(int n, int z=2)
 2 {  
 3    if((n%z)==0)
 4       return 0;
 5    else
 6    {
 7       if(z<(n-1))
 8          return is_prime1(n,z+1);
 9       else
10          return 1;
11    }
12 }

Druhé riešenie - čiastočne optimalizované

Optimalizácia v tomto prípade znamená eliminovať počet delení modulo. Myšlienka nájdenia hornej hranice hodnoty premennej z z predchádzajúceho príkladu:

• Číslo n delíme modulo hodnotou 2. (výsledok je rôzny od 0)
  • nemá zmysel deliť číslom z väčším ako je n/2, pretože už nám nemôže vyjsť celočíselný podiel. Výsledok takéhoto delenia bude v intervale (0,1)
• Číslo n delíme modulo hodnotou 3. (výsledok je rôzny od 0)
  • nemá zmysel deliť číslom z väčším ako je n/3, pretože už nám nemôže vyjsť celočíselný podiel. Výsledok takéhoto delenia bude v intervale [math](1,2) \cup (2,3)[/math]. Podiel nebude mať hodnotu 2, pretože v tom prípade by bolo číslo n delitelné číslom 3 bezo zvyšku.
• Delitel n budeme zväčšovať až pokiaľ platí [math]\frac {n}{d}\gt d[/math]

Horná hranica hodnoty d sa dá určiť nasledovne: [math]d=\sqrt{n}[/math]

Možné riešenie:

 1 int is_prime2(int n, int z=2)
 2 {  
 3    if((n%z)==0)
 4       return 0;
 5    else
 6    {
 7       if(z<sqrt(n))
 8          return is_prime2(n,z+1);
 9       else
10          return 1;
11    }
12 }

Tretie riešenie - viac optimalizované

V predchádzajúcom príklade sme delili číslo n hodnotami premennej d. Premenná d mala prvú hodnotu 2 a potom sa k nej vždy pripočítala hodnota 1. Teda, číslo n sme postupne delili hodnotami

2, 3, 4, 5, 6, 7, 8, ... [math]d=\sqrt{n}[/math].

Všimnime si, že niektoré delenia sú opäť zbytočné:

• ak delíme číslom 2, potom nemá zmysel deliť žiadnym jeho násobkom
• vo všeobecnosti platí: ak delíme číslom j, potom nemá zmysel deliť žiadnym násobkom čísla j.

Inak povedané, netreba deliť žiadnom zloženým číslom. Stačí deliť prvočíslami. A tu sa dostávame k rekurzívnej definícii prvočísel:

Rekurzívna definícia prvočísla:

• Číslo 2 je najmenšie prvočíslo.
• Prvočíslo je každé celé kladné číslo, ktoré nie je deliteľné žiadnym iným menším prvočíslom ako je toto číslo samotné.

Pri takto stanovenej podmienke je komplikovanejšie vytvoriť podmienku, ktoré by toto spĺňala. Preto skúsme napísať program, ktorý by zbytočne nedelil násobkami čísel 2 a 3. Ak nechceme deliť násobkami čísla 2, tak potom budeme postupne deliť premennú n hodnotami 3,5,7,9,11,...

Ak nechceme deliť násobkami čísla 3, tak potom budeme postupne deliť premennú n hodnotami 4,5,7,8,10,11,13,14,...

Prienikom týchto dvoch podmienok je, že nám zostava deliť číslami 5,7,11,13,17,19,23, ...

V tejto postupnosti je jednoduché pravidlo: striedavé pripočítavanie hodnoty 2 a 4. Vyjadrené aritmetickou postupnosťou:

• [math]d_0=2[/math]
• [math]d_1=3[/math]
• [math]d_2=5[/math]
• [math]d_n=d_{n-1} + 3-(-1)^{i+1}[/math]

Možné riešenie:

 1 int is_prime3(int n, int z,int krok)
 2 { 
 3    int d=z+3+krok;
 4    if((n%d)==0)
 5       return 0;
 6    else
 7    {
 8       if(d<sqrt(n))
 9          return is_prime3(n,d,-krok);
10       else
11          return 1;
12    }
13 }
14 
15 int is_prime(int n)
16 {
17    if((n%2)==0) return 0;
18    if((n%3)==0) return 0;
19    if((n%5)==0) return 0;
20    return is_prime3(n,5,-1);
21 }

Rozbor zdrojového kódu:

Pre hľadanie prvočísel použijeme funkciu is_prime, ktorá otestuje číslo n na deliteľnosť číslami 2, 3 a 5. Potom zavoláme pomocnú rekurzívnu funkciu is_prime3(int n, int z,int krok) ktorá bude testovať deliteľnosť čísla n prvkami postupnosti [math]\big\{d_n\big\}[/math]. Aby sme sa vyhli zbytočným podmienkam, ktoré môžu celý algoritmus spomaliť, definujeme tretí parameter funkcie is_prime3 krok. Parameter krok je v našej postupnosti výraz [math] 3-(-1)^{i+1}[/math], avšak tu nepočítame hodnotu mocniny [math](-1)^{i+1}[/math] ale využívame skutočnosť že tento výraz nadobúda hodnoty -1,1,-1,1, ... .

V premennej d je vypočítaná hodnota aktuálneho deliteľa podľa vzťahu: [math]d_n=d_{n-1} + 3-(-1)^{i+1}[/math].

Riešenie s globálnym poľom

Pre zjednodušenie tvorby programu si vytvorme globálne pole do ktorého uložíme prvých n prvočísel. Potom najväčšie číslo, ktoré môžeme testovať na prvočíselnosť je [math]N=n^2[/math].

Analýza riešenia:

Testujeme číslo n na prvočíselnosť. Ako prvé vypočítame zvyšok po delení prvým prvočíslom v poli pcisla (delíme číslom pcisla[0]=2). V prípade, ak je výsledok 0, tak výpočet ukončíme a vrátime hodnotu (0 - nie je prvočíslo). V opačnom prípade rekurzívne zavoláme funkciu jePrvocislo, kde druhý parameter (má význam indexu v poli pcisla) zvýšime o 1. Teda v ďalšom volaní funkcie jePrvocislo už budeme deliť číslom pcisla[1]=3. Musíme však zabezpečiť, aby hodnota pcisla[i] v riadku č. 5 existovala. To zabezpečíme tak, že rekurzívne volanie dovolíme len ak je hodnota indexu i menšia ako počet hodnôt v pole pcisla.

Možné riešenie:

 1 int prvocisla[]={2,3,5,7,11,13,17,19,23,29,31,37};
 2 
 3 int is_prime4(int n, int i=0)
 4 { 
 5   if(n%prvocisla[i]==0)
 6      return 0;
 7   if(i<223 && n>pow(prvocisla[i],2))
 8      return is_prime4(n,i+1);
 9   else 
10      return 1;   
11 }

Vzorové riešenie

Uvádzame postupnosť volaní funkcie is_prime4(31)

Vnorenie	Volaná funkcia	prvocisla[i]	n%prvocisla[i]	rekurzívne volanie
0	is_prime(31,0)	2	31%2=1	is_prime(31,1)
1	is_prime(31,1)	3	31%3=1	is_prime(31,2)
2	is_prime(31,2)	5	31%5=1	is_prime(31,3)
3	is_prime(31,3)	7	31%7=3	is_prime(31,4)
4	is_prime(31,4)	11	n.a.	neplatí podmienka n>prvocisla[i]^2 n=31, i=4, prvocisla[i]=11 funkcia vracia hodnotu 1
3	návrat na is_prime(31,3)	7	n.a.	spätný rekurzívny chod
2	návrat na is_prime(31,2)	5	n.a.	spätný rekurzívny chod
1	návrat na is_prime(31,1)	3	n.a.	spätný rekurzívny chod
0	návrat na is_prime(31,0)	2	n.a.	spätný rekurzívny chod

Porovnanie efektivity navrhovaných algoritmov

Skôr ako budeme porovnávať ukázané algoritmy, poznamenajme, že tento spôsob zisťovania prvočíselnosti je pre veľké čísla veľmi neefektívny. Pri 8-cifernom čísle trvá výpočet funkcie is_prime približne 230 s. Pre zisťovanie prvočíselnosti existujú špeciálne algoritmy, napr. ASK test, Test Solovay-Strassena, Test Millera-Rabina a iné. V nasledujúcej tabuľke a na obrázku sú výsledky porovnania efektívnosti týchto algoritmov pri hľadaní prvočísel na intervale (100,n) kde n sme menili od 50 000 do 2 000 000. V tabuľke ani v grafe nie je zahrnutá funkcia is_prime1, pretože pri n=100 000 pri rekurzívnom volaní funkcia neočakávane skončila. Aby sme mohli porovnávať aj funkciu is_prime4, musíme do poľa prvocisla pridať všetky prvočísla, ktoré sú menšie ako [math]\sqrt{n_{max}}[/math], kde n_max je v našom prípade 2 000 000. Pole prvocisla obsahuje prvých 233 prvočísel:

int prvocisla[]={
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,
191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,
397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,
617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,
1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,
1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423};

Naprogramované funkcie sme testovali nasledovne:

#include <iostream.h>
#include <time.h>

int main()
{
   clock_t start, end;
   double elapsed;
   int n;
   n=50000; //100000, 200000, ... 2000000
   start = clock();
   for(int i=100;i<n;i++)
      is_prime(i);   
   end = clock();
   elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
   cout<<elapsed<<endl;
}

Tabuľka nameraných časov behu funkcií

n [tisíc]	is_prime_2 t[s]	is_prime t[s]	is_prime4 t[s]
50	0,16	0,086	0,061
100	0,398	0,134	0,126
200	1,034	0,345	0,304
500	1,245	1,237	0,958
1000	3,275	3,264	2,349
1500	17,203	5,831	3,9
2000	26	8,6	5,82

<pLines ymin=0 ymax=27 colors=FF0000,00FF00,0000FF size=600x250 plots legend> ,is_prime2, is_prime, is_prime4 50 tis, 0.16, 0.08, 0.061 100 tis, 0.398, 0.134, 0.126 200 tis, 1.034, 0.345, 0.304 500 tis, 1.245, 1.237, 0.958 1 mil, 3.275, 3.264, 2.349 1.5 mil, 17.203, 5.831, 3.9 2 mil, 26, 8.6, 5.82 </pLines>

Podobné časy pri nižších hodnotách n sú dané tým, že vzdialenosť susedných prvočísel je väčšia pri vyšších prvočíslach. Z grafu taktiež vidieť účinok optimalizácie algoritmu.

Odkazy

• http://sk.wikipedia.org/wiki/Zoznam_prvo%C4%8D%C3%ADsiel
• http://www.prime-numbers.org/