Veliki brojevi u listi

Nenegativan ceo broj sa mnogo cifara čuva se kao jednostruko povezana lista cifara, od cifre najmanje težine ka cifri najveće (broj 342 je lista 2 4 3). Napisati funkcije

Cvor<int>* saberi(Cvor<int>* a, Cvor<int>* b);
void pomnozi(Cvor<int>* broj, int k);

Funkcija saberi vraća novu listu koja predstavlja zbir, a liste a i b ne menja. Funkcija pomnozi množi broj malim prirodnim brojem k u mestu, dodajući nove čvorove na kraj dok ima prenosa.

Korišćenjem funkcije pomnozi računa se i $n!$.

Pitanje za razmišljanje: Zašto je izabran baš ovakav redosled cifara? Šta se dešava sa prenosom posle poslednje cifre, i sa brojevima različite dužine?

Ulaz

U prvom redu učitava se nenegativan ceo broj a, a u drugom nenegativan ceo broj b, svaki sa najviše $10^5$ cifara i bez vodećih nula. U trećem redu učitava se broj n $(0 \le n \le 3000)$.

Izlaz

U prvom redu ispisati zbir a + b, a u drugom tačnu vrednost $n!$.

Primer

Ulaz

342
465
25

Izlaz

807
15511210043330985984000000

Postavka

main.cpp

#include <iostream>
#include <string>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Vraca novu listu cifara koja predstavlja zbir brojeva a i b.
    Cvor<int>* saberi(Cvor<int>* a, Cvor<int>* b)
    {
        // Ovde ide vasa implementacija
        return nullptr;
    }

    // Mnozi broj malim prirodnim brojem k. Lista broja nije prazna.
    void pomnozi(Cvor<int>* broj, int k)
    {
        // Ovde ide vasa implementacija
    }

} // namespace matf

// Pravi listu cifara od zapisa broja; cifra najmanje tezine je na pocetku.
Cvor<int>* u_listu(const std::string& zapis)
{
    Cvor<int>* pocetak = nullptr;
    for (char c : zapis)
        pocetak = new Cvor<int>(c - '0', pocetak);
    return pocetak;
}

// Ispisuje broj tako sto cifre slaze u nisku, od poslednje ka prvoj.
void ispisi_broj(Cvor<int>* broj)
{
    std::string zapis;
    for (Cvor<int>* p = broj; p != nullptr; p = p->sledeci)
        zapis += char('0' + p->podatak);
    for (std::size_t i = zapis.size(); i > 0; --i)
        std::cout << zapis[i - 1];
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    std::string a, b;
    int n;
    std::cin >> a >> b >> n;

    Cvor<int>* x = u_listu(a);
    Cvor<int>* y = u_listu(b);
    Cvor<int>* zbir = matf::saberi(x, y);
    ispisi_broj(zbir);

    Cvor<int>* faktorijel = new Cvor<int>(1, nullptr);
    for (int i = 2; i <= n; ++i)
        matf::pomnozi(faktorijel, i);
    ispisi_broj(faktorijel);

    oslobodi(x);
    oslobodi(y);
    oslobodi(zbir);
    oslobodi(faktorijel);
    return 0;
}

Rešenje

main.cpp

#include <iostream>
#include <string>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Vraca novu listu cifara koja predstavlja zbir brojeva a i b.
    Cvor<int>* saberi(Cvor<int>* a, Cvor<int>* b)
    {
        Cvor<int> privremeni(0, nullptr);
        Cvor<int>* poslednji = &privremeni;

        int prenos = 0;
        while (a != nullptr || b != nullptr || prenos != 0) {
            int zbir = prenos;
            if (a != nullptr) {
                zbir += a->podatak;
                a = a->sledeci;
            }
            if (b != nullptr) {
                zbir += b->podatak;
                b = b->sledeci;
            }

            poslednji->sledeci = new Cvor<int>(zbir % 10, nullptr);
            poslednji = poslednji->sledeci;
            prenos = zbir / 10;
        }

        return privremeni.sledeci;
    }

    // Mnozi broj malim prirodnim brojem k. Lista broja nije prazna.
    void pomnozi(Cvor<int>* broj, int k)
    {
        int prenos = 0;
        Cvor<int>* poslednji = nullptr;
        for (Cvor<int>* p = broj; p != nullptr; p = p->sledeci) {
            int proizvod = p->podatak * k + prenos;
            p->podatak = proizvod % 10;
            prenos = proizvod / 10;
            poslednji = p;
        }

        while (prenos != 0) {
            poslednji->sledeci = new Cvor<int>(prenos % 10, nullptr);
            poslednji = poslednji->sledeci;
            prenos /= 10;
        }
    }

} // namespace matf

// Pravi listu cifara od zapisa broja; cifra najmanje tezine je na pocetku.
Cvor<int>* u_listu(const std::string& zapis)
{
    Cvor<int>* pocetak = nullptr;
    for (char c : zapis)
        pocetak = new Cvor<int>(c - '0', pocetak);
    return pocetak;
}

// Ispisuje broj tako sto cifre slaze u nisku, od poslednje ka prvoj.
void ispisi_broj(Cvor<int>* broj)
{
    std::string zapis;
    for (Cvor<int>* p = broj; p != nullptr; p = p->sledeci)
        zapis += char('0' + p->podatak);
    for (std::size_t i = zapis.size(); i > 0; --i)
        std::cout << zapis[i - 1];
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    std::string a, b;
    int n;
    std::cin >> a >> b >> n;

    Cvor<int>* x = u_listu(a);
    Cvor<int>* y = u_listu(b);
    Cvor<int>* zbir = matf::saberi(x, y);
    ispisi_broj(zbir);

    Cvor<int>* faktorijel = new Cvor<int>(1, nullptr);
    for (int i = 2; i <= n; ++i)
        matf::pomnozi(faktorijel, i);
    ispisi_broj(faktorijel);

    oslobodi(x);
    oslobodi(y);
    oslobodi(zbir);
    oslobodi(faktorijel);
    return 0;
}