将32位正整数转换为以空结尾的字符串的查找表需要多少RAM?

让S n )成为数字的字符串 n .

考虑S(429496730)到S(4294967295)。通过将其划分为子范围(429496730)到S(9999999999)和S(100000000)到S(4294967295),我们可以看到它们需要(9999999999_墋429496730+1)_墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋墋11字节(9位10字节加空终止

这是41949672956字节。

考虑如何查找任何数字 n 在1到4294967295范围内。如果它在429496730到999999999范围内,则其字符串将开始( n _429496730)*将10个字节放入上述第一个子范围的表中。如果它在上面,它的字符串就开始了( n -100000000)_窆11个字节进入第二个子范围。

如果小于429496730,我们只需添加100000000,并查找( n +100000000)。S的字符串( n )从s的第一个字节后的第一个非零数字开始( n +100000000)。

因此,我们已经证明,我们最多需要41949672956字节来实现一个合理的查找函数,该函数可以轻松地为1到4294967295之间的任何整数返回指向以空结束的字符串的指针。

此外,很容易看出,两个子范围的组合表中没有字符串是任何其他字符串的子字符串,这意味着需要每个字符串。因此,对于返回指向准备好的字符串的指针的函数来说,41949672956字节是必要且足够的。

不知道这是一个“编程”问题(也不知道为什么它的答案是有用的),但让我们尝试一些数学:

创建一个字符串指针表是不值得的,因为指针本身是8个字节,最长的字符串是10个字节(注意,不添加0终止符来节省空间!),因此最好将其存储为char[10]数组的数组(即一个非常长的字符串,第一个数字在偏移量0处,第二个数字在偏移量10处,依此类推)。因此,您需要2^31*10字节=21474836480字节。