Dnia 20-09-2010 o 05:37:26 j...@f...adres.to
<w...@c...barg.cy> napisał(a):
> 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?

Obawiam się, że tak :). Algorytm ma działać dla dowolnych ułamków, których
liczniki i mianowniki mieszczą się w zakresie long int. Na przykład
11/2147483629 i 17/2147483647 (nie ukrywam, że dobrałem złośliwie :) ).

Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o większej
precyzji, np. long long int. Równie dobrze możemy przyjąć, że licznik i
mianownik są typu long long int i że mianowniki są z górnej granicy tego
zakresu.

> j..

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !