7

我正在用 C++ 编码。我得到 2 个分数，a/b 和 c/d，其中 a、b、c、d 是整数。有谁知道没有溢出的 a/b>c/d 方法。例如，如果我将 a、b、c、d 设置为小于 2147483647 的 4 个最大素数。我将如何确定 a/b>c/d 是否为真。我不允许使用除 int 以外的任何其他类型（即，我无法转换为 long long 或 double）。

4

5 回答 5

7

这是一种适用于正整数的方法：

bool greaterPositiveFraction(int a,int b,int c,int d);

bool greaterOrEqualPositiveFraction(int a,int b,int c,int d)
{
  if (b == 0) return true;
  if (d == 0) return false;
  if (a/b > c/d) return true;
  if (a/b < c/d) return false;
  return !greaterPositiveFraction(b,a%b,d,c%d);
}

bool greaterPositiveFraction(int a,int b,int c,int d)
{
  if (d == 0) return false;
  if (b == 0) return true;
  if (a/b > c/d) return true;
  if (a/b < c/d) return false;
  return !greaterOrEqualFraction(b,a%b,d,c%d);
}

这个想法是，如果整数除法更小或更大，那么你就知道答案了。如果整数除法给出相同的结果，这只是棘手的。在这种情况下，您可以只使用余数，并查看 a%b/b > c%d/d 是否。但是，我们知道 a%b/b > c%d/d if b/(a%b) < d/(c%d)，所以我们可以把问题转过来再试一次。

带有余数的负值的整数除法有点混乱，但这些情况可以很容易地处理：

bool greaterFraction(int a,int b,int c,int d)
{
  if (b<0) { b = -b; a = -a; }
  if (d<0) { d = -d; c = -c; }
  if (a<0 && c<0) return greaterPositiveFraction(-c,d,-a,b);
  if (a<0) return false;
  if (c<0) return true;
  return greaterPositiveFraction(a,b,c,d);
}
于 2012-11-11T19:14:38.763 回答
4

您可以使用标准算法（将 a*d 与 b*c 进行比较），但使用 64 位乘法以外的方法进行乘法运算。就像将您的数字分成 16 位块并使用标准的大整数乘法例程来计算结果。

于 2012-11-11T18:45:20.183 回答
0

您可以使用学校长除法来获得被除数和商，并像下面的伪代码一样继续递归除法：

bool compare(a,b,c,d)
    a/b = n + r/b
    c/d = m + q/d
    if (n == m) 
        if (r == 0 && q == 0) return false
        if (r == 0) return false
        if (q == 0) return true
        if (a < b && c < d)
            if (c/a == d/b && c%a == 0 && d%b == 0) return false
            return !compare(b,r,d,q)  //flip it to continue
    if (n > m) return true       //a/b > c/d
    else if (n < m) return false //a/b < c/d
    else return compare(r,b,q,d) //need to continue comparing
于 2012-11-11T19:05:48.897 回答
0

只需像这里一样进行 std int 除法：http ://en.wikipedia.org/wiki/Division_algorithm （请参阅带余数的整数除法（无符号））。Div int by int 不会溢出，你会得到商和提醒。现在如果 Q1 > Q2 或 Q1 < Q2 很清楚，如果 Q1==Q2 那么你比较 R1/b 和 R2/d。

例如，采用复杂的 Q1==Q2 情况，25/12 和 44/21，Q1=2 和 R2=1，Q2=2 和 R2=2，因此 Q1==Q2，您现在需要比较 1/12 和 2/ 21. 现在你做一个 12*21 的公约数，但你不需要将它们相乘，你只需要比较 1*21 和 2*12。即你比较 (1*21)/(12*21) 和 (2*12)/(12*21) 但由于除数相同，这意味着只比较 1*21 和 2*12。

嗯，但是 1*21 和 2*12 都可以溢出（如果不是 12 而是 maxint）。好吧，无论如何，也许它会给出一些想法。

要获得更好的解决方案，只需实现您自己的 128 位（或 N 位）整数类。这并不难做到，也许半天。您只需将高低 64 位部分分开并重载运算符 +-*/>><<。

于 2012-11-11T19:33:46.973 回答
0

(a/b > c/d) 可以部分写成在许多情况下避免算术运算，然后在其余情况下避免算术上溢和下溢。请注意，最后一个案例留给读者作为练习。

bool fractioncompare(int a, int b, int c, int d) {
    bool cd_negative = (c < 0 && d > 0) || (c > 0 && d < 0);
    bool ab_negative = (a < 0 && b > 0) || (a > 0 && b < 0);

    // if c/d negative and a/b positive then a/b is larger
    if(cd_negative && !ab_negative) return true;

    // if c/d postive and a/b negative then a/b is not larger
    if((!cd_negative && ab_negative) return false;

    bool both_negative = cd_negative && ab_negative;

    // limited cases were a/b > c/d can be determined without needing to 
    // do arithmetic calculations (so no risk of overflow / underflow)
    if(a > c && b < d) return !both_negative;
    if(a < c && b > d) return both_negative;

    int ab = a/b;
    int cd = c/d;

    bool no_trunc = a % b && c % d;
    if(no_trunc) return ab > cd;

    // No risk of overflow with divide and skipping the equal case avoids 
    //truncation issues
    if(ab > cd) return true;
    if(ab < cd) return false;

    // truncation may mean ab and cd aren't actually equal so do some
    // comparisons on differences to determine the result
    if(!both_negative)
    {
        // use subtraction only to avoid overflow
        if(ab == 0) return (b-(b-a) > d-(d-c));
        else return (b-(b-a) < d-(d-c));
    }
    else
    {
        // TODO subtract values with same sign and add with 
        // different signs and compare appropriately to determine result
    }

}
于 2012-11-11T20:27:39.857 回答