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

Prvočísla definujme ako:

• Čí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é.

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 }

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

Úprava hranice delenia: z<(n-1)

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í