c++ - 有效地找到康托尔有理数集的第 N 项

Question

George Cantor 证明了一组有理数是可数的。可以使用此图1中所示的方法找到它的第 n 项。我在这里找到了解决方案2。但是对于大数字来说它非常慢，因为我的 n 可以达到 10^18。有什么办法可以快速做到这一点？

标签： c++

Answer 1

您面临的问题是算法问题。

如果您尝试使用 aden和num变量进行导航，则需要采取10^18措施。你的程序永远不会完成。（嗯，它可能，但我们不会在那里了）

您可以做的第一个优化是循环对角线。您只需要大致迭代10^9对角线。这在您可以在 PC 上计算的范围内。对于每个对角线，计算长度，检查它是否在您正在寻找的范围内，如果不是，则转到下一个对角线。

第二个优化是封闭形式的解决方案。请参阅评论中的 .pdf。