按给定数字查找数字

Question

假设我有一系列数字，例如：

12345678910111213141516... (until unlimited)

然后我想通过给定的数字从中获取一个数字。例如：

• 第 10 位：1

• 第 17 位：3

• ...

我试图通过使用 PHP 来使算法做到这一点，但它总是向我显示一个错误，因为如果我给出的给定数字超过10.000.000，我所做的循环就会超出内存大小。Allowed Memory Size of 134217728 Bytes Exhausted

我该如何处理而无需修改memory_limitphp.ini 文件？

以下是我试图找出算法的内容：我对本地机器可以处理的循环上限的最大值进行了基准测试，我发现它是10.000.000，然后我假设我需要做一个单独的循环，如果给定的数字/参数大于 10.000.000。但最后我还是得到了内存不足的错误。真的很感谢提前。

Answer 1

您可以使用这样一个事实，即总是10^n - 10^(n-1)有 n 位长数字（即使是 1 位，因为我看到 0 不存在）。有了这些知识，您就可以跳过潜在的大量数字。您从 n=1 开始，并检查 n 位数字的数量是否小于所需的数字。如果是，则从所需的数字中减少 n 位数字的数量，将 n 增加 1 并重新开始。例如：您想知道该号码中的第 512 位数字 1 位数字的数量 (10) 是否低于所需的数字 (512)？是的，因此所需的数字应该减少那么多（512 - 9）。2 位数字的数量 (90) 是否低于所需的数字（现在是 503）？是的，因此所需的数字应该减少那么多（503 - 90）。3位数字的数量（900）是否低于所需的数字（现在是413）？不，所以所需的数字是 3 位数的数字之一。413 / 3 是 137（向下取整），因此它是第 137 个 3 位数字（即 237）的其中一位。413 % 3 (modulo) 是 2，所以它是第二个数字，所以它应该是 3。这其中可能有误算，但总体逻辑应该不会太远。编辑：您也可以使用生成器，但这可以增加大数字的运行时间function getNthDigit() {    for ($i = 0;; ++$i) { // Start with 0, which is the 0-th digit        foreach (str_split((string)$i) as $digit) {            yield $digit;        }    }}$desiredDigit = 512;foreach (getNthDigit() as $number => $digit) {    if ($number == $desiredDigit) {        break;    }}// $digit should be the desired digit

Answer 2

<?phpfunction getDigit($Nth){&nbsp; &nbsp; if($Nth < 10) return $Nth;&nbsp; &nbsp; $no_of_digits = 1;&nbsp; &nbsp; $current_contribution = 9;&nbsp; &nbsp; $actual_length = 9;&nbsp; &nbsp; $prev_length = 0;&nbsp; &nbsp; $starting_number = 1;&nbsp; &nbsp; $power_of_10 = 1;&nbsp; &nbsp; while($actual_length < $Nth){&nbsp; &nbsp; &nbsp; &nbsp; $no_of_digits++;&nbsp; &nbsp; &nbsp; &nbsp; $current_contribution *= 10;&nbsp; &nbsp; &nbsp; &nbsp; $prev_length = $actual_length;&nbsp; &nbsp; &nbsp; &nbsp; $actual_length += ($current_contribution * $no_of_digits);&nbsp; &nbsp; &nbsp; &nbsp; $power_of_10 *= 10;&nbsp; &nbsp; &nbsp; &nbsp; $starting_number *= 10;&nbsp; &nbsp; }&nbsp; &nbsp; $Nth = $Nth - $prev_length;&nbsp; &nbsp; $offset = $Nth % $no_of_digits === 0 ? intval($Nth / $no_of_digits) - 1 : intval($Nth / $no_of_digits);&nbsp; &nbsp; $number = strval($starting_number + $offset);&nbsp; &nbsp; for($i=1;$i<=$no_of_digits;++$i){&nbsp; &nbsp; &nbsp; &nbsp; if(($Nth - $i) % $no_of_digits === 0){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return $number[$i-1];&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}// first 100 Digits&nbsp;for($i=1;$i<=100;++$i){&nbsp; &nbsp; echo getDigit($i),PHP_EOL;}演示：&nbsp;https&nbsp;:&nbsp;//3v4l.org/3l0I7算法：要找到第 n个数字，我们将首先找到数字，然后选择该数字的哪个数字作为答案。找到号码：如果我们仔细观察，该系列是按顺序增加的，如表所示。桌子：| Digits| Total numbers(of current digit)| Total Digits | Total digits of whole string&nbsp; ||-------|--------------------------------|--------------|-------------------------------|| 1&nbsp; &nbsp; &nbsp;| 9&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | 9&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | 9&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|| 2&nbsp; &nbsp; &nbsp;| 90&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;| 180&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | 189&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|| 3&nbsp; &nbsp; &nbsp;| 900&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | 2700&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;| 2889&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; || 4&nbsp; &nbsp; &nbsp;| 9000&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;| 36000&nbsp; &nbsp; &nbsp; &nbsp; | 38889&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|上表告诉我们，如果我们想找到第500位数字，那么它是 3 位数字的某个数字。如果我们选择第17位数字，那么它是 2 位数字的某个数字，依此类推。现在，让我们以第200位为例。由于它小于2889和大于189，它来自一个3 位数字。我们要做的是将 分解200为较小的数字，例如200 - 189 = 11。这11意味着它是某个 3 位数字的第 11 位，以 的初始3数字编号100（3 位数字的起始数字）开头。现在，我们做11 / 3（其中3是位数）并得到商为3。这3意味着它的3数字超过了起始数字100，我们可以说100 + 3 = 103（因为它是 100,101,102，然后是第 4 个数字 103）。现在，我们知道这个数字是103。剩下的就是找出来自 的哪个数字103。请注意，有时我们会遇到偶数可整性的极端情况，例如 12 / 3。在这种情况下，我们从商中减去 1，因为我们的 3 位数字系列从 100 开始而不是 101（对于其他数字，依此类推）。找出数字：现在，我们知道这个数字是第103一个200数字（也11就是我们上面计算的）。为了找出哪一个，我们依次写下3位数字并仔细观察。序列：1&nbsp;0&nbsp;0&nbsp;1&nbsp;0&nbsp;1&nbsp;1&nbsp;0&nbsp;2&nbsp;1&nbsp;&nbsp;0&nbsp;&nbsp;3&nbsp;&nbsp;1&nbsp;&nbsp;0&nbsp;&nbsp;4&nbsp;&nbsp;1&nbsp;&nbsp;0&nbsp;&nbsp;5&nbsp;&nbsp;1&nbsp;&nbsp;0&nbsp;&nbsp;6 1&nbsp;2&nbsp;3&nbsp;4&nbsp;5&nbsp;6&nbsp;7&nbsp;8&nbsp;9&nbsp;10&nbsp;11&nbsp;12&nbsp;13&nbsp;14&nbsp;15&nbsp;16&nbsp;17&nbsp;18&nbsp;19&nbsp;20&nbsp;21如果你观察，你可以理解，最高的 MSB 数字遵循 1、4、7、10、13 等序列。第二高的 MSB 遵循 2、5、8、11、14 等序列，最后一个 MSB（是 LSB) 遵循 3,6,9,12,15 等的序列。所以，从上面的序列，很明显11（我们在200最初分解后得到的）属于第二个最高 MSB 数字的序列。因此，103的最终答案是0（左起第二个数字）。

Answer 3

$num = '12345678910111213141516';echo $num[16];结果：3