假設我有一系列數字，例如：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。但最后我還是得到了內存不足的錯誤。真的很感謝提前。
3 回答
qq_笑_17
TA貢獻1818條經驗 獲得超7個贊
您可以使用這樣一個事實，即總是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
青春有我
TA貢獻1784條經驗 獲得超8個贊
<?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（左起第二個數字）。
- 3 回答
- 0 關注
- 212 瀏覽
添加回答
舉報
0/150
提交
取消