Razlomci preko pokazivača

Data je struktura Razlomak koja čuva long long brojilac i long long imenilac, pri čemu je imenilac različit od nule.

Zadaci:

  1. void skrati(Razlomak* r) — svodi razlomak na najmanje cele brojeve, sa pozitivnim imeniocem;
  2. Razlomak zbir(const Razlomak& a, const Razlomak& b) — vraća novi, skraćen zbir dva razlomka.
  3. const Razlomak* veci(const Razlomak* a, const Razlomak* b) — pokazivač na veći od dva razlomka, ako su jednaki onda vraća a.

Ulaz

U prvom redu učitava se broj razlomaka n. Zatim n redova, svaki sa po dva cela broja brojilac imenilac, gde je imenilac != 0.

Izlaz

Za svaki učitani razlomak ispisati ga u skraćenom obliku brojilac/imenilac sa pozitivnim imeniocem. Zatim ispisati skračen zbir svih razlomaka. Zatim ispisati najveći razlomak.

Primer

Ulaz

4
6 8
-2 3
5 -10
0 7

Izlaz

3/4
-2/3
-1/2
0/1
-5/12
3/4

Postavka

main.cpp

#include <iostream>
#include <vector>
#include <numeric>

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

  // TODO (1): implementirati skrati preko pokazivaca (koristiti ->)
  // skracen razlomak sa pozitivnim imeniocem, 0 postaje 0/1
  void skrati(Razlomak* r)
  {
    return undefined;
  }

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

  // TODO (3): implementirati veci
  // pokazivac na veci od *a i *b (a na nerešeno)
  const Razlomak* veci(const Razlomak* a, const Razlomak* b)
  {
    return undefined;
  }

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

} // namespace matf

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

  std::vector<matf::Razlomak> v(n);
  for (int i = 0; i < n; ++i)
    std::cin >> v[i].brojilac >> v[i].imenilac;

  for (int i = 0; i < n; ++i) {
    matf::skrati(&v[i]);
    matf::ispisi(v[i]);
  }

  matf::Razlomak zbir{0, 1};
  for (int i = 0; i < n; ++i)
    zbir = matf::zbir(zbir, v[i]);
  matf::ispisi(zbir);

  const matf::Razlomak* najveci = &v[0];
  for (int i = 1; i < n; ++i)
    najveci = matf::veci(najveci, &v[i]);
  matf::ispisi(*najveci);

  return 0;
}

Rešenje

main.cpp

#include <iostream>
#include <vector>
#include <numeric>

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

  // O(log(min(|brojilac|, |imenilac|))); svodi *r na skracen razlomak sa
  // pozitivnim imeniocem. 0 postaje 0/1.
  void skrati(Razlomak* r)
  {
    if (r->imenilac < 0) {
      r->brojilac = -r->brojilac;
      r->imenilac = -r->imenilac;
    }
    long long g = std::gcd(r->brojilac, r->imenilac);   // g >= 1 jer je imenilac != 0
    r->brojilac /= g;
    r->imenilac /= g;
  }

  // O(log(...)); vraca novi, skracen razlomak a + b. a i b se ne kopiraju ni menjaju.
  Razlomak zbir(const Razlomak& a, const Razlomak& b)
  {
    Razlomak c{ a.brojilac * b.imenilac + b.brojilac * a.imenilac, a.imenilac * b.imenilac };
    skrati(&c);
    return c;
  }

  // O(1); pokazivac na veci od *a i *b (a ako su jednaki).
  // Oba razlomka vec moraju imati pozitivan imenilac.
  const Razlomak* veci(const Razlomak* a, const Razlomak* b)
  {
    if (b->brojilac * a->imenilac > a->brojilac * b->imenilac)
      return b;
    return a;
  }

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

} // namespace matf

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

  std::vector<matf::Razlomak> v(n);
  for (int i = 0; i < n; ++i)
    std::cin >> v[i].brojilac >> v[i].imenilac;

  for (int i = 0; i < n; ++i) {
    matf::skrati(&v[i]);
    matf::ispisi(v[i]);
  }

  matf::Razlomak zbir{0, 1};
  for (int i = 0; i < n; ++i)
    zbir = matf::zbir(zbir, v[i]);
  matf::ispisi(zbir);

  const matf::Razlomak* najveci = &v[0];
  for (int i = 1; i < n; ++i)
    najveci = matf::veci(najveci, &v[i]);
  matf::ispisi(*najveci);

  return 0;
}