嗯,我接到了一项任务,要构建一个可在斐波那契生成器中使用的可扩展数据类型,当我去测试序列中的第 1000 个数字时,我的任务即将完成。
我注意到它没有对齐,并确定问题出在序列中的第 262 个数字处。经过一番调试,我发现这是链表从 7 个整数移动到 8 个整数的地方,但我不知道这与问题有关。
我要查找的号码是:
2 542 592 393 026 885 507 715 496 646 813 780 220 945 054 040 571 721 231
我得到的数字是:
1 154 259 239 326 885 507 715 496 646 813 780 220 945 054 040 571 721 231
正如您可能注意到的,直到最后一个 block (左端)它们都非常相似。
我的来源有点长,所以我提出了一个要点:
https://gist.github.com/anonymous/5802620
携带任何超过 1,000,000,000 的东西的魔力发生在第 378 行的函数中: 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 行。您没有足够快地在等式中计算额外
。这些行应分别具有 ((num + extra) % chunkSize)
和 extra = (num + extra )/chunkSize;
。根据您当前的实现,其中一个段可能是 1000000000 没有进位,而不是 0 有进位(如果我正在阅读您的意图,如果您想要的话)。
关于c++ - 使用链接列表计算巨数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17160374/