如何找到类似于1491625...的数字中第n个数字？

Question

让我们将以1开头的数字的平方连接起来。那么，这个字符串中的第n位是什么？

例如，第10位数字是4。

1 4 9 16 25 36 49 64 81

这只是我普通思维中的一个普通问题。今晚如何解决才能睡得好？有没有不需要循环的算法？

- user467871

---

该函数是否已提供现成的数字 (1491625...)，还是它需要自行计算？提取第n位数应该很容易（不管是什么进制 - 但我假设您说的是十进制？）。 - user395760

@ephemient 是的，谢谢。现在是晚上。对此很抱歉。 - user467871

Answer 1

您可以通过获取10的幂次方的平方根来枚举在该序列中有多少个1位数、2位数、3位数等数字，以此确定第n个数字所属的数。从那里开始，这应该相当简单。

这应该是O(log n)复杂度。

- Oliver Charlesworth

---

+1 更进一步的优化是不要每次计算平方根，因为sqrt(10^n) = sqrt(10^(n-1)) * sqrt(10)，这是每个10的幂需要一次乘法运算。 - biziclop

@biziclop：这是个好主意！我猜随着n变得非常大，数值不准确可能会导致迭代计算发散。 - Oliver Charlesworth

是的，在使用浮点运算进行实践时，它会出现这种情况。但作为一种理论算法，它是可行的。 - biziclop

当你到达所需数字并尝试找到其平方的第k位数字时，可以应用另一种简化方法。如果该数字的平方长度为m位数，则无需计算该数字的平方，只需计算其最后(m-k+1)位数字即可。 - biziclop

@OliCharlesworth，你能给个例子吗？从你的回答中我不确定如何实现getDigit(0x87A99C006D61, 10) == 4。 - Segfault

Answer 2

ceil(log₁₀(x+1))将给出数字中的位数。遍历平方数，计算总长度的数量，并一旦达到或超过目标长度n，就知道您需要最后一个数字的第m个数字，其中m是某个数字（易于计算）。通过除以10^m-1然后使用模10获取此数字的第m个数字。

总体而言，空间开销恒定，运行时间为O(n)。

- moinudin

---

ceil(log10 X+1) 是一个更好的估计值（例如，尝试一下 ceil(log10 10)，并数一下 10 的位数）。 - Vatine

由于我自己也犯过同样的错误，所以很容易（或者说相对容易）理解。另一种选择是使用 floor(log10 X)+1。 - Vatine

Answer 3

为了解决这个问题，我使用了Python生成器。我的Python解决方案如下：

def _countup(n):
    while True:
        yield n
        n += 1

def get_nth_element(n):
    i = 0 # Initialized just to keep track of iterations.
    final_string = ''
    cu_generator = _countup(0)

    while True:
        num = cu_generator.next()
        final_string += str(num * num)
        if len(final_string) > n:
            print "Number of iterations %s" % i
            return final_string[n]
        i += 1

RUN：

>>> get_nth_element(1000)
Number of iterations 229
'2'

>>> get_nth_element(10000)
Number of iterations 1637
'7'

- aatifh

Answer 4

Haskell中的惰性无限列表使得这个表达式变得非常简单。

ghci> concat [show $ i*i | i <- [1..]] !! 9
'4'

- ephemient

---

我的（修改后的）替代方案：concatMap (show . (^2)) [1..] - user395760

@delnan 有很多更加晦涩的方法，比如 [1..] >>= show . join (*) :) - ephemient

Answer 5

为什么不循环，取每个数字，平方并增加计数器，检查每一步是否已达到n？您不必跟踪整个数字。这是一个简单的模拟练习。我恐怕无法为此识别出模式或公式。

- Senthil Kumaran

---

有更有效的方法来完成这个任务。比如说，如果你想要得到第二十亿位数字，那么需要进行很多次平方运算才能得到结果。 - biziclop

Answer 6

这是 ephemient 的 Haskell 答案直接移植到 Scala 的版本

Iterator.from(1).flatMap(x=>(x*x).toString.iterator).drop(9).next

返回 4

O(n)

• Iterator.from(1) 创建一个无限迭代器，计数为 1,2,3,4,....。
• 然后 (x*x).toString 计算其中每个数的平方并将其转换为字符串。
• flatMap( ... .iterator) 将它们连接起来，成为一个无限的字符迭代器。
• drop(9) 从迭代器中删除前9个元素（索引从0到8），并给我们一个新的迭代器，等待在索引9处。
• next 返回那个单独的字符。

- Ken Bloom

---

我不理解这段代码，但我猜它类似于线性搜索，只是循环而已。O(n) - user467871