首頁(yè) 猿問(wèn) 按給定數(shù)字查找數(shù)字

按給定數(shù)字查找數(shù)字

PHP

胡說(shuō)叔叔 2021-12-03 16:19:10

假設(shè)我有一系列數(shù)字，例如：12345678910111213141516... (until unlimited)然后我想通過(guò)給定的數(shù)字從中獲取一個(gè)數(shù)字。例如：第 10 位：1第 17 位：3...我試圖通過(guò)使用 PHP 來(lái)使算法做到這一點(diǎn)，但它總是向我顯示一個(gè)錯(cuò)誤，因?yàn)槿绻医o出的給定數(shù)字超過(guò)10.000.000，我所做的循環(huán)就會(huì)超出內(nèi)存大小。Allowed Memory Size of 134217728 Bytes Exhausted我該如何處理而無(wú)需修改memory_limitphp.ini 文件？以下是我試圖找出算法的內(nèi)容：我對(duì)本地機(jī)器可以處理的循環(huán)上限的最大值進(jìn)行了基準(zhǔn)測(cè)試，我發(fā)現(xiàn)它是10.000.000，然后我假設(shè)我需要做一個(gè)單獨(dú)的循環(huán)，如果給定的數(shù)字/參數(shù)大于 10.000.000。但最后我還是得到了內(nèi)存不足的錯(cuò)誤。真的很感謝提前。

查看完整描述

3 回答

qq_笑_17

TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超7個(gè)贊

您可以使用這樣一個(gè)事實(shí)，即總是10^n - 10^(n-1)有 n 位長(zhǎng)數(shù)字（即使是 1 位，因?yàn)槲铱吹?0 不存在）。

有了這些知識(shí)，您就可以跳過(guò)潛在的大量數(shù)字。您從 n=1 開(kāi)始，并檢查 n 位數(shù)字的數(shù)量是否小于所需的數(shù)字。如果是，則從所需的數(shù)字中減少 n 位數(shù)字的數(shù)量，將 n 增加 1 并重新開(kāi)始。

例如：您想知道該號(hào)碼中的第 512 位數(shù)字 1 位數(shù)字的數(shù)量 (10) 是否低于所需的數(shù)字 (512)？是的，因此所需的數(shù)字應(yīng)該減少那么多（512 - 9）。2 位數(shù)字的數(shù)量 (90) 是否低于所需的數(shù)字（現(xiàn)在是 503）？是的，因此所需的數(shù)字應(yīng)該減少那么多（503 - 90）。3位數(shù)字的數(shù)量（900）是否低于所需的數(shù)字（現(xiàn)在是413）？不，所以所需的數(shù)字是 3 位數(shù)的數(shù)字之一。413 / 3 是 137（向下取整），因此它是第 137 個(gè) 3 位數(shù)字（即 237）的其中一位。413 % 3 (modulo) 是 2，所以它是第二個(gè)數(shù)字，所以它應(yīng)該是 3。

這其中可能有誤算，但總體邏輯應(yīng)該不會(huì)太遠(yuǎn)。

編輯：您也可以使用生成器，但這可以增加大數(shù)字的運(yùn)行時(shí)間

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

反對(duì) 回復(fù) 2021-12-03

青春有我

TA貢獻(xiàn)1784條經(jīng)驗(yàn) 獲得超8個(gè)贊

<?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^個(gè)數(shù)字，我們將首先找到數(shù)字，然后選擇該數(shù)字的哪個(gè)數(shù)字作為答案。

找到號(hào)碼：

如果我們仔細(xì)觀察，該系列是按順序增加的，如表所示。

桌子：

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

| 1 | 9 | 9 | 9 |

| 2 | 90 | 180 | 189 |

| 3 | 900 | 2700 | 2889 |

| 4 | 9000 | 36000 | 38889 |

上表告訴我們，如果我們想找到^第500^位數(shù)字，那么它是 3 位數(shù)字的某個(gè)數(shù)字。如果我們選擇^第17^位數(shù)字，那么它是 2 位數(shù)字的某個(gè)數(shù)字，依此類推。
現(xiàn)在，讓我們以^第200位為例。由于它小于2889和大于189，它來(lái)自一個(gè)3 位數(shù)字。
我們要做的是將分解200為較小的數(shù)字，例如200 - 189 = 11。這11意味著它是某個(gè) 3 位數(shù)字的第 11 位，以的初始3數(shù)字編號(hào)100（3 位數(shù)字的起始數(shù)字）開(kāi)頭。
現(xiàn)在，我們做11 / 3（其中3是位數(shù)）并得到商為3。這3意味著它的3數(shù)字超過(guò)了起始數(shù)字100，我們可以說(shuō)100 + 3 = 103（因?yàn)樗?100,101,102，然后是第 4 個(gè)數(shù)字 103）。
現(xiàn)在，我們知道這個(gè)數(shù)字是103。剩下的就是找出來(lái)自的哪個(gè)數(shù)字103。
請(qǐng)注意，有時(shí)我們會(huì)遇到偶數(shù)可整性的極端情況，例如 12 / 3。在這種情況下，我們從商中減去 1，因?yàn)槲覀兊?3 位數(shù)字系列從 100 開(kāi)始而不是 101（對(duì)于其他數(shù)字，依此類推）。

找出數(shù)字：

現(xiàn)在，我們知道這個(gè)數(shù)字是第103一個(gè)200數(shù)字（也11就是我們上面計(jì)算的）。為了找出哪一個(gè)，我們依次寫下3位數(shù)字并仔細(xì)觀察。

序列：

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 數(shù)字遵循 1、4、7、10、13 等序列。第二高的 MSB 遵循 2、5、8、11、14 等序列，最后一個(gè) MSB（是 LSB) 遵循 3,6,9,12,15 等的序列。
所以，從上面的序列，很明顯11（我們?cè)?code>200最初分解后得到的）屬于^{第二個(gè)}最高 MSB 數(shù)字的序列。
因此，103的最終答案是0（左起第二個(gè)數(shù)字）。