5. cvičení

Příklad: převod čísel z desítkové do dvojkové soustavy

Algoritmus výpočtu je pěkně vysvětlen zde.

#include <iostream>

using namespace std;

void do_binarni(int n)
{
    // velikost pole: pocet bitu typu int
    int zbytky[sizeof(int) * 8];
    int index = 0;
    while (n > 0) {
        // spocitat zbytek, ulozit do pole
        zbytky[index] = n % 2;
        // posunout index
        index += 1;
        // vydelit, ulozit do n
        n /= 2;
    }

    // vypis binarnich cislic (v opacnem poradi)
    for (int i = index - 1; i >= 0; i--) {
        cout << zbytky[i];
    }
    cout << endl;
}

int main()
{
    cout << "Zadej prirozene cislo: ";
    int cislo = 0;
    cin >> cislo;

    if (cislo > 0) {
        do_binarni(cislo);
        return 0;
    }
    else {
        cout << "zadane cislo neni prirozene" << endl;
        return 1;
    }
}

Bonusový úkol: Zobecnění pro převod čísel z desítkové soustavy do soustavy o základu \(b\), kde \(2<b<10\).

Příklad: rozklad přirozeného čísla na součin prvočísel

Prvočísla ukládejte do pole, na konci programu proveďte kontrolu (pronásobení všech prvočísel v poli a porovnání se zadaným číslem) a vypište čísla na obrazovku.

#include <iostream>

using namespace std;

void rozloz_na_prvocinitele(int n)
{
    // stejna velikost jako v prvnim prikladu
    int prvocinitele[sizeof(int) * 8];

    int index = 0;
    for (int i = 2; i <= n; i++) {
        // - zjistit jestli "i" je delitel cisla "n"
        if (n % i == 0) {
            // pokud ano, tak:
            // ulozit "i" do pole
            prvocinitele[index] = i;
            // posunout index
            index++;
            // spocitat n = n / i
            n /= i;
            // i-- (aby se "i" zkontrolovalo znovu)
            i--;
        }
    }

    // vypis
    for (int i = 0; i < index; i++) {
        cout << prvocinitele[i];
        if (i < index - 1) {
            cout << " * ";
        }
    }
    cout << endl;
}

int main()
{
    cout << "Zadej prirozene cislo: ";
    int cislo = 0;
    cin >> cislo;

    if (cislo > 0) {
        rozloz_na_prvocinitele(cislo);
        return 0;
    }
    else {
        cout << "zadane cislo neni prirozene" << endl;
        return 1;
    }
}

Bonusový úkol: Pomocí rozkladu čísla na součin prvočísel určete největšího společného dělitele (NSD) a nejmenší společný násobek (NSN) dvou zadaných čísel.

Bonusový úkol: Znáte nějaký jiný (lepší) algoritmus pro určení největšího společného dělitele dvou přirozených čísel?

Last updated: Tue 20 October 2020