比较没有溢出的分数

Question

我用C++编写代码.我得到2个分数,a/b和c/d,其中a,b,c,d是int.有没有人知道如何做一个/ b> c/d没有溢出.例如,如果我将a,b,c,d设置为小于2147483647的4个最大质数.我如何确定a/b> c/d是否为真.我不允许使用除int之外的任何其他类型(即,我无法转换为long long或double).

Answer 1

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

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);
}

这个想法是,如果整数除法更小或更大,那么你知道答案.如果整数除法给出相同的结果,那将是棘手的.在这种情况下,您可以使用余数,并查看%b/b> c%d/d.但是,我们知道如果b /(a%b)<d /(c%d),则%b/b> c%d/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);
}

Answer 2

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