Zapis intervala cijelih brojeva u računalu

Kada u računalu želimo prikazati interval cijelih brojeva, isključeni zapis intervala [lo, hi> obično je prikladniji od uključenog zapisa.

• STL (standard template library) koristi ovaj način zapisa intervala
• pokazuje se da se rjeđe moraju koristiti izrazi s +/- 1 prilagodbama, što smanjuje vjerojatnost pojave pogreške u programu

Po konvenciji često ovakvim intervalima dajemo imena varijabli lo i hi što čitatelju odmah daje do znanja da je hi isključeni element.

Zgodna stvar je da prazni interval [x, x> označava i neku poziciju na brojevnom pravcu (neposredno prije x).

Presjek dvaju intervala

Presjek dvaju intervala možemo shvatiti promatranjem logičkih izraza koji predstavljaju same intervale:

[lo1, hi1> je zapravo x >= lo1 && x < hi1.
[lo2, hi2> je isto tako x >= lo2 && x < hi2.

Stoga, kako bi x bio u oba intervala mora vrijediti x >= lo1 && x < hi1 && x >= lo2 && x < hi2, a budući da je operator && komutativan i asocijativan, taj izraz možemo prepisati u (x >= lo1 && x >= lo2) && (x < hi1 && x < hi2).

Sada je vidljivije da je izraz ekvivalentan s x >= max(lo1, lo2) && x < min(hi1, hi2).

Implementacija

void traverse(int lo, int hi) {
  for (int it = lo; it < hi; ++it);
}

bool nonempty(int lo, int hi) {
  return lo < hi;
}

int count(int lo, int hi) {
  return nonempty(lo, hi) ? hi - lo : 0;
}

bool intersects(int lo1, int hi1, int lo2, int hi2) {
  return nonempty(std::max(lo1, lo2), std::min(hi1, hi2));
}

bool contains(int lo, int hi, int x) {
  return x >= lo && x < hi;
}

bool contains(int lo1, int hi1, int lo2, int hi2) {
  return lo2 >= lo1 && hi2 <= hi1;
}

// rezultantni intervali su disjunktni, odnosno nemaju presjek
// ukoliko je count(lo, hi) paran broj, tada oba intervala imaju jednaku velicinu.
// u suprotnom prvi interval sadrzi jedan broj manje.
// int mid = (lo + hi) / 2 je ekvivalentno, osim sto ima opasnost od overflow-a
void split(int lo, int hi) {
  int mid = lo + (hi - lo) / 2;
  (lo, mid);
  (mid, hi);
}

© 2014. Anton Grbin

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License