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é.