按给定数字查找数字

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

<?php

function getDigit($Nth){

    if($Nth < 10) return $Nth;

    $no_of_digits = 1;

    $current_contribution = 9;

    $actual_length = 9;

    $prev_length = 0;

    $starting_number = 1;

    $power_of_10 = 1;

    while($actual_length < $Nth){

        $no_of_digits++;

        $current_contribution *= 10;

        $prev_length = $actual_length;

        $actual_length += ($current_contribution * $no_of_digits);

        $power_of_10 *= 10;

        $starting_number *= 10;

    }

    $Nth = $Nth - $prev_length;

    $offset = $Nth % $no_of_digits === 0 ? intval($Nth / $no_of_digits) - 1 : intval($Nth / $no_of_digits);

    $number = strval($starting_number + $offset);

    for($i=1;$i<=$no_of_digits;++$i){

        if(($Nth - $i) % $no_of_digits === 0){

            return $number[$i-1];

        }

    }

}

// first 100 Digits 

for($i=1;$i<=100;++$i){

    echo getDigit($i),PHP_EOL;

}

演示： https : //3v4l.org/3l0I7

算法：

要找到第 n^个数字，我们将首先找到数字，然后选择该数字的哪个数字作为答案。

找到号码：

• 如果我们仔细观察，该系列是按顺序增加的，如表所示。

桌子：

| Digits| Total numbers(of current digit)| Total Digits | Total digits of whole string  |

|-------|--------------------------------|--------------|-------------------------------|

| 1     | 9                              | 9            | 9                             |

| 2     | 90                             | 180          | 189                           |

| 3     | 900                            | 2700         | 2889                          |

| 4     | 9000                           | 36000        | 38889                         |

• 上表告诉我们，如果我们想找到^第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 0 0 1 0 1 1 0 2 1  0  3  1  0  4  1  0  5  1  0  6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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