-4

みんな私は学習目的で LINT (large int) と呼ばれるクラスに取り組んでいますが、知るまではすべてうまくいきました。operator/(const LINT&) の実装に行き詰まっています。ここでの問題は、LINT を LINT で除算したいときに、再帰的な fnc 呼び出しが発生することです。つまり、次のようになります。

//unfinished
LINT_rep LINT_rep::divide_(const LINT_rep& bottom)const
{
typedef LINT_rep::Iterator iter;
 iter topBeg = begin();
 iter topEnd = end();
 iter bottomBeg = bottom.begin();
 iter bottomEnd = bottom.end();
LINT_rep topTmp;//for storing smallest number (dividend) which can be used to divide by divisor
 while (topBeg != topEnd)
 {
  topTmp.insert_(*topBeg);//Number not large enough add another digit
 if (topTmp >= bottom)
 {//ok number >= we can divide 
     LINT_rep topShelf = topTmp / bottom;//HERE I'M RUNNING INTO TROUBLE
 }
 else
 {


 }
 ++topBeg;
 }
 return LINT_rep("-1");//DUMMY
}

私がやろうとしているのは、これらの数値を手で割るかのようにこれを実装することです。たとえば、被除数 1589 と除数 27 の場合、次のようになります。

  1. 最初の桁が>=除数であるかどうかを確認し、そうであれば除算します
  2. そうでない場合は、最初の桁に別の桁を追加し、a > b かどうかを確認します

ある時点で（単純化されたシナリオでは）大きくなり、そうであれば分割する必要がありますが、この場合、再帰呼び出しに遭遇していて、それを壊す方法がわかりません。
1 つの注意: tmp として、たとえば int の代わりに LINT を使用する必要があります。これらの数値は int に適合しないためです。
それで、一般的に私が求めているのは、除算を行う他の方法はありますか? または、私の考えに誤った論理があるのか​​もしれません (かなり可能性があります)。ありがとうございました。

4

2 に答える 2

2

自分の役割を果たしているとき (1) 分割することはできません。手で行う場合と同じように、繰り返し減算するか、倍数を減算するために推測する必要があります。必要な倍数の上限と下限を設定し、範囲内でバイナリチョップを実行することで、より効果的に「推測」できます。

私も同様のことをしました。演算子のオーバーロードを練習するのに便利な演習です。必要に応じてコードのスニペットを提供できますが、配列と中途半端な例外を使用しているため、このサイトの専門家の読者の前で提供することをためらっています.

于 2010-06-21T10:14:28.007 に答える
0

まず、そのようなクラスで作業しないでください。CGAL の big int を使用し、ブースト bigint の提出がいくつかありました。また、他に 3 つまたは 4 つの一般的な実装があると思います。

第二に、除算アルゴリズムがここで説明されています: http://en.wikipedia.org/wiki/Long_division

[編集] 正しい方法: 結果 (C) の桁 k: A の最初の桁 (左から) を A[nA-1] と呼び、B[nB-1] より小さい場合、C にゼロを書き込みます。 [k]。k-- (次の桁に移動)。それ以外の場合は、C[k]*B*10^k <= A となる最大桁 C[k] を探します。これはループで行われます。実際、前の文はこの文の私的なケースです。しかし、それはまだ終わっていません。A-=C[k]*B*10^k を実行します (それ以外の場合、減算された部分はゼロでした)。その時だけ、

k-- (次の桁)。k==0 までループします。

再帰は必要ありません。ネストされたループが 2 つだけです。

k (結果の桁) の 1 つのループ、すべての桁を見つけるための 1 つのループ、減算 (-= 演算子) のための 1 つのループ (その近く)。

于 2010-06-21T09:46:59.663 に答える