Razlomak

Implementirati tip podataka Razlomak koji predstavlja racionalan broj.

Reprezentacija: brojilac i imenilac su celi brojevi; imenilac je uvek pozitivan, a razlomak je uvek skraćen (std::gcd(brojilac, imenilac) == 1, ili brojilac == 0 i imenilac == 1).

Operacije:

Razlomak napravi_razlomak(int brojilac, int imenilac) — pravi skraćen razlomak sa pozitivnim imeniocem. Preduslov: imenilac != 0.
Razlomak saberi(const Razlomak& a, const Razlomak& b) — zbir dva razlomka, skraćen.
Razlomak pomnozi(const Razlomak& a, const Razlomak& b) — proizvod dva razlomka, skraćen.
bool jednaki(const Razlomak& a, const Razlomak& b) — vraća true ako su razlomci jednaki.
bool manji(const Razlomak& a, const Razlomak& b) — vraća true ako je a < b.
void ispisi(const Razlomak& r) — ispisuje razlomak u obliku brojilac/imenilac.

Savet: Za NZD koristiti std::gcd iz <numeric>.

Zadaci:

Implementirati napravi_razlomak. Dodati assert za preduslov.
Implementirati saberi i pomnozi, tako da njihov rezultat uvek prolazi kroz napravi_razlomak.
Implementirati jednaki i manji, bez prelaska na double.
Implementirati ispisi.
Zašto invarijantu treba da uspostavlja samo napravi_razlomak, a ne i ostale funkcije? Šta bi moglo da pođe po zlu kada bi neko pravio Razlomak{a, b} direktno, mimo napravi_razlomak?
(dodatno) U saberi, izraz a.imenilac * b.imenilac može da prekorači opseg int-a ranije nego što je neophodno. Izbeći to tako što se imenioci prvo skrate pomoću std::gcd(a.imenilac, b.imenilac).

Ulaz

U prvom redu se učitava broj upita $q$ $(1 \le q \le 1000)$.

Svaki od narednih $q$ redova sadrži jedan od upita, gde su br, im (i br1, im1, br2, im2) celi brojevi od kojih su imenioci uvek razliciti od nule.

S br1 im1 br2 im2 — saberi(a, b), gde su a i b razlomci dobijeni od (br1, im1) i (br2, im2)
M br1 im1 br2 im2 — pomnozi(a, b)
J br1 im1 br2 im2 — jednaki(a, b)
L br1 im1 br2 im2 — manji(a, b)

Izlaz

Za upite S i M ispisati rezultujući razlomak u obliku brojilac/imenilac (skraćen, sa pozitivnim imeniocem).

Za upite J i L ispisati DA ili NE.

Primer

Ulaz

8
S 1 2 1 3
M 1 2 1 3
J 1 2 2 4
J 1 2 1 3
L 1 3 1 2
L 1 2 1 3
S 1 2 -1 2
M 0 5 100 7

Izlaz

5/6
1/6
DA
NE
DA
NE
0/1
0/1

Postavka

`razlomak.hpp`

#ifndef RAZLOMAK_HPP
#define RAZLOMAK_HPP

namespace matf
{
  struct Razlomak {
    int brojilac;
    int imenilac;
  };

  // preduslov: imenilac != 0
  Razlomak napravi_razlomak(int brojilac, int imenilac);

  Razlomak saberi(const Razlomak& a, const Razlomak& b);
  Razlomak pomnozi(const Razlomak& a, const Razlomak& b);

  bool jednaki(const Razlomak& a, const Razlomak& b);
  bool manji(const Razlomak& a, const Razlomak& b);

  void ispisi(const Razlomak& r);

} // namespace matf

#endif // RAZLOMAK_HPP

`razlomak.cpp`

#include "razlomak.hpp"

#include <cassert>
#include <iostream>
#include <numeric>

namespace matf
{
  // preduslov: imenilac != 0
  // TODO (1): implementirati napravi_razlomak (skracen razlomak, imenilac > 0)
  Razlomak napravi_razlomak(int brojilac, int imenilac)
  {
    return undefined;
  }

  // TODO (2): implementirati saberi, rezultat mora proci kroz napravi_razlomak
  Razlomak saberi(const Razlomak& a, const Razlomak& b)
  {
    return undefined;
  }

  // TODO (2): implementirati pomnozi, rezultat mora proci kroz napravi_razlomak
  Razlomak pomnozi(const Razlomak& a, const Razlomak& b)
  {
    return undefined;
  }

  // TODO (3): implementirati jednaki, bez prelaska na double
  bool jednaki(const Razlomak& a, const Razlomak& b)
  {
    return undefined;
  }

  // TODO (3): implementirati manji, bez prelaska na double
  bool manji(const Razlomak& a, const Razlomak& b)
  {
    return undefined;
  }

  // TODO (4): implementirati ispisi, u obliku brojilac/imenilac
  void ispisi(const Razlomak& r)
  {
    return undefined;
  }

  // TODO (5): zasto invarijantu uspostavlja samo napravi_razlomak? Odgovoriti kao komentar

  // TODO (6) (dodatno): u saberi izbeci prekoracenje skracivanjem imenilaca pomocu std::gcd

} // namespace matf

`main.cpp`

#include "razlomak.hpp"

#include <iostream>

int main()
{
  int q;
  std::cin >> q;

  while (q--) {
    char op;
    std::cin >> op;

    int br1, im1;
    std::cin >> br1 >> im1;
    matf::Razlomak a = matf::napravi_razlomak(br1, im1);

    int br2, im2;
    std::cin >> br2 >> im2;
    matf::Razlomak b = matf::napravi_razlomak(br2, im2);

    if (op == 'S') {
      matf::ispisi(matf::saberi(a, b));
    } else if (op == 'M') {
      matf::ispisi(matf::pomnozi(a, b));
    } else if (op == 'J') {
      std::cout << (matf::jednaki(a, b) ? "DA" : "NE") << '\n';
    } else if (op == 'L') {
      std::cout << (matf::manji(a, b) ? "DA" : "NE") << '\n';
    }
  }

  return 0;
}

Rešenje

`razlomak.hpp`

#ifndef RAZLOMAK_HPP
#define RAZLOMAK_HPP

namespace matf
{
  struct Razlomak {
    int brojilac;
    int imenilac;
    // invarijantu (skracen razlomak, imenilac > 0) uspostavlja samo
    // napravi_razlomak; ostale funkcije je samo koriste
  };

  // preduslov: imenilac != 0
  Razlomak napravi_razlomak(int brojilac, int imenilac);

  Razlomak saberi(const Razlomak& a, const Razlomak& b);
  Razlomak pomnozi(const Razlomak& a, const Razlomak& b);

  bool jednaki(const Razlomak& a, const Razlomak& b);
  bool manji(const Razlomak& a, const Razlomak& b);

  void ispisi(const Razlomak& r);

} // namespace matf

#endif // RAZLOMAK_HPP

`razlomak.cpp`

#include "razlomak.hpp"

#include <cassert>
#include <iostream>
#include <numeric>

namespace matf
{

  // O(log(min(|brojilac|, |imenilac|))); uspostavlja invarijantu: skracen
  // razlomak, imenilac > 0. Jedino ovde se Razlomak pravi "od nule" -- sve
  // ostale funkcije pretpostavljaju da je argument vec skracen.
  Razlomak napravi_razlomak(int brojilac, int imenilac)
  {
    assert(imenilac != 0);
    if (imenilac < 0) {
      brojilac = -brojilac;
      imenilac = -imenilac;
    }
    int g = std::gcd(brojilac, imenilac);
    return Razlomak{ brojilac / g, imenilac / g };
  }

  // O(log(min(|brojilac|, |imenilac|))); rezultat prolazi kroz napravi_razlomak, pa invarijanta vazi.
  Razlomak saberi(const Razlomak& a, const Razlomak& b)
  {
    int brojilac = a.brojilac * b.imenilac + b.brojilac * a.imenilac;
    int imenilac = a.imenilac * b.imenilac;
    return napravi_razlomak(brojilac, imenilac);
  }

  // O(log(min(|brojilac|, |imenilac|))); rezultat prolazi kroz napravi_razlomak, pa invarijanta vazi.
  Razlomak pomnozi(const Razlomak& a, const Razlomak& b)
  {
    int brojilac = a.brojilac * b.brojilac;
    int imenilac = a.imenilac * b.imenilac;
    return napravi_razlomak(brojilac, imenilac);
  }

  // O(1); oba argumenta su vec skracena sa pozitivnim imeniocem, pa je
  // jednakost razlomaka ista stvar kao jednakost (brojilac, imenilac) parova.
  bool jednaki(const Razlomak& a, const Razlomak& b)
  {
    return a.brojilac == b.brojilac && a.imenilac == b.imenilac;
  }

  // O(1); oba imenioca su pozitivna (invarijanta), pa unakrsno mnozenje ne
  // menja smer nejednakosti.
  bool manji(const Razlomak& a, const Razlomak& b)
  {
    return a.brojilac * b.imenilac < b.brojilac * a.imenilac;
  }

  // O(1)
  void ispisi(const Razlomak& r)
  {
    std::cout << r.brojilac << '/' << r.imenilac << std::endl;
  }

} // namespace matf

`main.cpp`

#include "razlomak.hpp"

#include <iostream>

int main()
{
  int q;
  std::cin >> q;

  while (q--) {
    char op;
    std::cin >> op;

    int br1, im1;
    std::cin >> br1 >> im1;
    matf::Razlomak a = matf::napravi_razlomak(br1, im1);

    int br2, im2;
    std::cin >> br2 >> im2;
    matf::Razlomak b = matf::napravi_razlomak(br2, im2);

    if (op == 'S') {
      matf::ispisi(matf::saberi(a, b));
    } else if (op == 'M') {
      matf::ispisi(matf::pomnozi(a, b));
    } else if (op == 'J') {
      std::cout << (matf::jednaki(a, b) ? "DA" : "NE") << std::endl;
    } else if (op == 'L') {
      std::cout << (matf::manji(a, b) ? "DA" : "NE") << std::endl;
    }
  }

  return 0;
}