Wpisy użytkownika Tomasz Wójcikowski z dnia 9 kwietnia 2009

Liczba wpisów: 1

firem
 

W jaki sposób obliczyć średnią dwóch dodatnich liczb całkowitych? Nic bardziej prostszego, powie ktoś:

int avg (int a, int b) {
  return (a+b) / 2 ;
}

Poprawnie? Tak, ale tylko, jeśli a+b <= MAX_INT. W innym przypadku dostaniemy błąd przepełnienia.
Spróbujmy zatem inaczej:

int avg (int a, int b) {
  long long c = a + b ;
  return c / 2 ;
}

Lepiej, ale wciąż będziemy mieli ten sam błąd, ponieważ konwersja na 64 bitową wartość long long nastąpi już po dodaniu, czyli po ewentualnym przepełnieniu.
Próba trzecia mogłaby wyglądać tak:
int avg (int a, int b) {
  long long c = a ;
  c += b ;
  return c / 2 ;
}
Prawie dobrze. Najpierw nastepuje konwersja wartości na long long, a dopiero później dodajemy drugą wartość.
Ale jest jeszcze jeden potencjalny problem z tym rozwiązaniem. Niektóre 64 bitowe implementacje równają wartości wielkości typoów (int) i (long long). W takim wypadku powyższa funkcja również zwróci błąd przepełnienia dla dużych wartości a i b.
Sięgnijmy więc po nieco sprytniejsze rozwiązanie.

int avg (int a, int b) {
  if (a > b) {
    return avg(b, a) ;
  }
  return a + (int)((b-a) / 2) ;
}

Jak widać operujemy wartościami wyłącznie w obrębie a <= x <= b, a więc wszystkie tymczasowe zmienne są typu int. Zdawałoby się proste zagadnienie programistyczne ma wcale nietrywialną implementację. Podobne rozważania można przeprowadzić dla większości banalnych operacji typu mnożenie, potęgowanie, silnia itp.
  • awatar Tomasz Wójcikowski: @malcom: zaskakujące, ale natknąłem się na ten problem w JS-ie. A ostateczna funkcja liczenia średniej jest i tak tylko poglądowa.
  • awatar Tomasz Wójcikowski: @malcom: w JS wogóle jest śmieszny problem z liczbami zmiennoprzecinkowymi. Sztandarowy przykład: 0.1 + 0.2 == 0.2(9)
  • awatar Krzysiek: Python: >>> 0.1 + 0.2 0.30000000000000004 >>> To zależy przecież od reprezentacji maszynowej, nie?
Pokaż wszystkie (12) ›