7

私はC++でコーディングしています。a、b、c、dがintであるa / bとc / dの2つの分数が与えられます。オーバーフローせずに a/b>c/d を実行する方法を知っている人はいますか? たとえば、a、b、c、d を 2147483647 未満の 4 つの最大の素数として設定した場合、a/b>c/d が true であるかどうかを判断するにはどうすればよいでしょうか。int 以外の型は使用できません (つまり、long long または double に変換できません)。

4

5 に答える 5

7

正の整数に対して機能する 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);
}

アイデアは、整数除算が小さいか大きい場合、答えがわかるということです。整数除算で同じ結果が得られる場合にのみ注意が必要です。この場合、残りを使用して、a%b/b > c%d/d かどうかを確認できます。ただし、b/(a%b) < d/(c%d) の場合、a%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);
}
于 2012-11-11T19:14:38.763 に答える
4

標準アルゴリズム (a*d と b*c を比較) を実行できますが、64 ビット乗算以外のものを使用して乗算を実行できます。同様に、数値を 16 ビットのチャンクに分割し、標準の biginteger 乗算ルーチンを使用して結果を計算します。

于 2012-11-11T18:45:20.183 に答える
0

http://en.wikipedia.org/wiki/Division_algorithmのようにstdint除算を実行してください（余りのある整数除算（符号なし）を参照）。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の場合）。とにかくOK多分それはいくつかのアイデアを与えるでしょう。

より良い解決策として、独自の128ビット（またはNビット）整数クラスを実装するだけです。これはそれほど難しいことではなく、おそらく半日です。高低の64ビットパーツを分離し、演算子+-* />><<をオーバーロードするだけです。

于 2012-11-11T19:33:46.973 に答える
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

(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 に答える