c++ - 使用链表计算巨数

好吧，我得到了一个构建可伸缩数据类型以用于Fibonacci生成器的任务，当我去测试序列中的第1000个数字时，我的任务就快完成了。

我注意到它脱离对齐状态，并确定问题出在序列的第262位。经过一些调试后，我发现链接列表从7个整数移动到8个整数，但是我不知道它与问题有关。

我要寻找的号码是:

2 542 592 393 026 885 507 715 496 646 813 780 22094594554 04057157121231

我得到的号码是:

1 154 259 239 326 885 507 715 496 646 813 780 220 945 054 040 571 721 231 231

您可能会注意到，它们直到最后一块(左端)非常相似。

我的消息来源对SO有点长，所以我总结了一下:

https://gist.github.com/anonymous/5802620

在行378的函数中发生了承载超过1,000,000,000的事情的魔力:
https://gist.github.com/anonymous/5802620#file-main-cpp-L378

作为更新，我仍然得到“接近但没有雪茄”的输出。这是可能是罪魁祸首的代码(包括提供的答案):

Giant Giant::operator + (const Giant & rightSide)
{
   Giant returned;
   int extra = 0;

   for(int i = 0;
      i < chunks.getNumItems() && i < rightSide.chunks.getNumItems(); i++)
   {
      int num = chunks.getData(i) + rightSide.chunks.getData(i);
      returned.chunks.insert((num + extra) % chunkSize,
         returned.chunks.getNumItems());
      extra = (num + extra) / chunkSize;
   }

   if(chunks.getNumItems() > rightSide.chunks.getNumItems())
   {
      for(int i = rightSide.chunks.getNumItems();
          i < chunks.getNumItems(); ++i)
      {
         returned.chunks.insert(extra + chunks.getData(i),
            returned.chunks.getNumItems());
         extra = 0;
      }
   }
   else if(chunks.getNumItems() < rightSide.chunks.getNumItems())
   {
      for(int i = chunks.getNumItems();
          i < rightSide.chunks.getNumItems(); ++i)
      {
         returned.chunks.insert(extra + rightSide.chunks.getData(i),
            returned.chunks.getNumItems());
         extra = 0;
      }
   }

   if (extra != 0)
   {
       returned.chunks.insert(extra, returned.chunks.getNumItems());
   }

   return returned;
}

更新
该类的一名成员走了过来，我们浏览了一下代码。问题出在这里:

ostream & operator << (ostream & out, const Giant & giant)
{
   for(int i = giant.chunks.getNumItems() - 1;
      i >= 0; i -= 1)
   {
      if (i != giant.chunks.getNumItems()-1)
         out << setw(9) << setfill('0');
      out << giant.chunks.getData(i);
   }
   return out;
}

我忘了强制显示导致问题的前导零。找到了解决方案。

最佳答案

您的问题似乎出在387和389行上。您在等式中没有足够快地解决extra的问题。这些行应分别具有((num + extra) % chunkSize)和extra = (num + extra )/ chunkSize;。在您当前的实现中，细分中的一个细分可能是没有进位的1000000000，而不是有进位的0(如果您要查看的是我的意图，则为0)。

关于c++ - 使用链表计算巨数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17160374/