c - 用于将 32 位正整数转换为以 null 结尾的字符串的查找表需要多少 RAM

Question

如果格式:{"1","2","3"}一直持续到 4,294,967,295 将使用多少 RAM？

Answer 1

令 S(n) 为数字 n 的字符串。

考虑 S(429,496,730) 到 S(4,294,967,295)。通过将其划分为子范围 S(429,496,730) 到 S(999,999,999) 和 S(1,000,000,000) 到 S(4,294,967,295)，我们可以看到它们需要 (999,999,999−429,496,730+1)•10 个字节和 (4,294,967,29) 5−1,000,000,000)•11 字节 ( 10 个字节表示 9 个数字加上一个空终止符，同样 11 个字节表示 10 个数字和一个终止符。)

这是 41,949,672,956 字节。

考虑如何查找 1 到 4,294,967,295 范围内的任意数字n。如果它在 429,496,730 到 999,999,999 范围内，则其字符串从 (n−429,496,730)*10 个字节开始进入上述第一个子范围的表。如果高于该值，则其字符串从 (n-1,000,000,000)•11 个字节开始进入第二个子范围。

如果它小于 429,496,730，我们只需添加 1,000,000,000 并查找 S(n+1,000,000,000)。 S(n) 的字符串从 S(n+1,000,000,000) 第一个字节后的第一个非零数字开始。

因此，我们已经证明，我们最多需要 41,949,672,956 字节来实现合理的查找函数，该函数可以轻松返回指向 1 到 4,294,967,295 之间的任何整数的以 null 结尾的字符串的指针。

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