On 20 Wrz, 05:37, "j...@f...adres.to"
<w...@c...barg.cy> wrote:
> 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..

Nie, ale nie o to chodziło żeby króliczka złapać. Zepsułeś całą zabawę.