4

2 つの配列 (被除数、除数) があります。

dividend[] = {1,2,0,9,8,7,5,6,6};
divisor[] = {9,8};

次のような結果（配当/除数）が必要です。

quotient[] = {1,2,3,4,5,6,7};

私は配列減算を使用してこれを行いました：

  • 被除数が 0 または除数未満になるまで被除数から除数を引き、そのたびに商を 1 ずつ増やします。

しかし、それには膨大な時間がかかります。これを行うより良い方法はありますか？

4

7 に答える 7

3

それ以外に、すでにこれを行っている BigInt クラス (またはあなたの言語で同等のもの) を使用することを検討しましたか?

于 2010-07-23T21:31:09.690 に答える
3

長い分割を行います。

除数に 1 を加えたサイズの一時ストレージを用意し、ゼロに初期化します。

accumulator[] = {0,0,0};

ループを実行します。

  1. 商の各桁を 1 スペース左にシフトします。
  2. アキュムレータの各桁を 1 スペース右にシフトします。
  3. 最上位から始まる被除数の次の桁を取得し、アキュムレータの最下位の場所に格納します。
  4. accumulator / divisor商の最下位桁を計算して結果に設定します。アキュムレータを剰余に設定します。

除算命令を持たない CPU のアセンブリ言語では、この同じアルゴリズムをよく使用していました。

于 2010-07-23T20:44:01.650 に答える
2

長い分割を使用できますhttp://en.wikipedia.org/wiki/Long_division

于 2010-07-24T06:07:22.943 に答える
1

これを行うより良い方法はありますか？

ロングディビジョンが使えます。

于 2010-07-23T20:41:06.860 に答える
1

Long 除算アルゴリズムまたはより一般的なPolynomial Long Divisionを使用できます。

于 2010-07-23T20:41:22.423 に答える
0

ほら！A は被除数です。B は除数です。C は商の整数、R は余りです。 それぞれの「巨大な」数は、大きな数を保持するベクトルです。huge[0] では、数値の桁数が保持され、数値が逆方向に記憶されます。 数値が 1234 の場合、コア応答ベクトルは次のようになります。

v[0]=4; //number of digits
v[1]=4;
v[2]=3;
v[3]=2;
v[4]=1;

....

SHL(H,1) does: H=H*10;
SGN(A,B) Compares the A and B numbers
SUBSTRACT(A,B) does: A=A-B;
DIVIDHUGE: makes the division using the mentioned procedures...

void Shl(Huge H, int Count)
/* H <- H*10ACount */
{ 
  memmove(&H[Count+1],&H[1],sizeof(int)*H[0]);
  memset(&H[1],0,sizeof(int)*Count);
   H[0]+=Count;
}
    int Sgn(Huge H1, Huge H2) {
      while (H1[0] && !H1[H1[0]]) H1[0]--;
      while (H2[0] && !H2[H2[0]]) H2[0]--;

      if (H1[0] < H2[0]) {
        return -1;
      } else if (H1[0] > H2[0]) {
        return +1;
      }

      for (int i = H1[0]; i > 0; --i) {
        if (H1[i] < H2[i]) {
          return -1;
        } else if (H1[i] > H2[i]) {
          return +1;
        }
      }
      return 0;
    }

        void Subtract(Huge A, Huge B)
        /* A <- A-B */
        { int i, T=0;

          for (i=B[0]+1;i<=A[0];) B[i++]=0;
          for (i=1;i<=A[0];i++)
            A[i]+= (T=(A[i]-=B[i]+T)<0) ? 10 : 0;
          while (!A[A[0]]) A[0]--;
        }


            void DivideHuge(Huge A, Huge B, Huge C, Huge R)
            /* A/B = C rest R */
            { int i;

              R[0]=0;C[0]=A[0];
              for (i=A[0];i;i--)
                { Shl(R,1);R[1]=A[i];
                  C[i]=0;
                  while (Sgn(B,R)!=1)
                    { C[i]++;
                      Subtract(R,B);
                    }
                }
              while (!C[C[0]] && C[0]>1) C[0]--;
            }
于 2010-08-01T18:39:25.567 に答える
0

それらを整数に変換してから、通常の除算を使用してみませんか?

疑似コードで：

int dividend_number
foreach i in dividend
    dividend_number *= 10
    dividend_number += i

int divisor_number
foreach i in divisor
    divisor_number *= 10
    divisor_number += i

int answer = dividend_number / divisor_number;
于 2010-07-23T20:41:29.467 に答える