Wojciech "Spook" Sura wrote:
> Witam!
>
> Zastanawiam się, w jaki sposób porównywać ułamki zwykłe?
>
> Przypuśćmy, że mam dane dwa ułamki, a/b i c/d. Chcę sprawdzić, czy są
> równe.
>
> 1. Metoda brutalna:
>
> float f1 = a/b;
> float f2 = c/d;
> return f1 == f2;
>
> f1 == f2 wygląda jak herezja, ale weźmy pod uwagę, że operacje
> zmiennoprzecinkowe są wykonywane deterministycznie i jeśli ułamki
> faktycznie są równe, warunek będzie spełniony. Niestety, nie mamy tu
> równoważności: być może bowiem uda się znaleźć inny ułamek zwykły, który
> da w wyniku taką samą liczbę zmiennoprzecinkową, ale wynikłą z
> niedoskonałości zapisu zmiennoprzecinkowego. Najwyraźniej więc metoda
> nie jest zbyt skuteczna.
>
> 2. Wspólny mianownik
>
> int tmpGCD = GCD(b, c);
>
> return (a * (d / tmpGCD)) == (c * (b / tmpGCD));
>
> Problem pojawi się wówczas, gdy złośliwie podrzucimy dwa ułamki o dużych
> mianownikach, których GCD wynosi 1, na przykład 1/2147483629 i
> 1/2147483647. Ich wspólnym mianownikiem jest 4611685977625198592, co
> oczywiście wykracza poza zakres long int. Co więcej, jedynym znanym mi
> sposobem na sprawdzenie, czy iloczyn dwóch liczb mieści się w zakresie
> inta jest przypisanie go do zmiennej typu double i porównanie z
> największym możliwym intem wyciągniętym z std::limits. Nie jest to zbyt
> wydajne rozwiązanie...
>
> Czy macie może jakiś lepszy pomysł?
>
> Pozdrawiam -- Spook.
>
Zakładam, że a,b,c,d są typu int,
oraz ułamek to uporządkowana para, czyli A = (a,b), B=(c,d),
czyli (w pseudokodzie)
struct fraction {int nominator, int denominator};

Wtedy:
a/b < c/d <=> a*d < c*b

W pseudokodzie funkcja, którą można użyć do sortowania będzie:

boolean compare(struct fraction A, struct fraction B) {
long left = (long)A.nominator * (long)B.denominator;
long right = (long)A.denominator * (long)B.nominator;
if(left<right) return -1;
if(left>right) return 1;
return 0;
}

Coś więcej potrzeba?

j..