Rekurzia (riešené príklady)

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>
#include <conio.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)
{
   if (r == 0) return;
   r *= zaklad; // posunie o jeden rad vlavo
   cout << znaky[int(r)]; // celu cast vypise
   PrevodReal(r - int(r), zaklad); // zvysok prevedie
}

// uvodna funkcia na specialne pripady
void Prevod(double r, int zaklad)
{
   // 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);
   }
}

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

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_prime 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_prime(int n, int z)
 2 {  
 3    if((n%z)==0)
 4       return 0;
 5    else
 6    {
 7       if(z<(n-1))
 8          return is_prime(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_prime(int n, int z)
 2 {  
 3    if((n%z)==0)
 4       return 0;
 5    else
 6    {
 7       if(z<sqrt(n))
 8          return is_prime(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,10,13,17,19, ...

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_prime2(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_prime2(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_prime2(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_prime2(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 zbyto4n7m podmienkam, ktoré môžu celý algoritmus spomaliť, definujeme tretí parameter funkcie is_prime2 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 pcisla[]={2,3,5,7,11,13,17,19,23,29,31,37};
 2 
 3 int jePrvocislo(int n, int i)
 4 { 
 5   if(n%pcisla[i]==0)
 6      return 0;
 7   if(i<11 && n>pow(pcisla[i],2))
 8      return jePrvocislo(n,i+1);
 9   else 
10      return 1;   
11 }
12 
13 int main()
14 {
15 
16    cout<<jePrvocislo(621,0);
17 
18 }

Vzorové riešenie -postupnosť volaní

Odkazy

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