-4

伙计们，我正在学习名为 LINT（大整数）的课程，直到知道为止，一切都很顺利。我坚持实施 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

在某些时候它会更大（在简化的场景中），如果是这样，我必须分开，但在这种情况下，我遇到了递归调用，我不知道如何打破它。
注意：例如，作为 tmp，我必须使用 LINT 而不是 int，因为这些数字不适合 int。
所以一般来说，我要问的是还有其他方法可以进行除法吗？或者我的想法可能存在错误的逻辑（很可能）。谢谢你。

4

2 回答 2

2

当做你的部分时（1）你不能分开；你必须反复减去，或者猜测减去一个倍数，就像你用手做一样。您可以通过为所需的倍数设置上限和下限并在范围内进行二进制切分来更有效地“猜测”。

我自己也做过类似的事情；练习运算符重载是一个方便的练习。如果您愿意，我可以提供一段代码，尽管它使用数组和半生不熟的异常，所以我不愿在本网站的专业读者面前提供它。

于 2010-06-21T10:14:28.007 回答
0

首先，请不要在这样的课程上工作。使用 CGAL 的 big int，我认为有一些 boost bigint 提交，此外，还有大约三四个其他流行的实现。

二、划分算法描述在这里：http ://en.wikipedia.org/wiki/Long_division

[编辑] 正确的方法：结果的数字 k (C)：如果 A 的第一个数字（从左起），称它为 A[nA-1] 小于 B[nB-1]，将零写入 C [k]。k--（移动到下一位）。否则，您将寻找最大位数 C[k]，以便 C[k]*B*10^k <= A。这是在循环中完成的。实际上，上一句是这句的私人案例。但它还没有完成。你做 A-=C[k]*B*10^k （否则减去的部分为零）。只有这样，

k--（下一位）。循环直到 k==0。

不需要递归。只有两个嵌套循环。

一个循环用于 k（结果的数字），一个循环用于查找每个数字，一个循环（靠近它）用于减法（-= 运算符）。

于 2010-06-21T09:46:59.663 回答