“好”数字的算法

如果数字 x 的任意两个连续数字之和在 k 和 2k 之间，则给定数字 x 是“好”。 我需要找到一种算法，对于给定的数字 k 和给定的数字 n，找出存在多少个“好”n 位数字。

我在 PHP 中为此实现了一个实现，但复杂性太大（我正在搜索所有这些“好”数字并计算它们，因此复杂性为 O(10^n)）。

<?php
    $n = 5;
    $k = 5;

    $min = $k*1;
    $max = $k*2;
    $counter = 0;

    for ($i = pow(10, $n-1); $i<pow(10,$n); $i++)
    {
        $number = $i;
        $prev = $number % 10;
        $number = $number / 10;

        while($number >= 10)
        {
            $crnt = $number % 10;
            $number = $number / 10;
            if ( ($crnt+$prev) > $min AND ($crnt+$prev) < $max ) {
                echo "good number: $i\n";
                $counter++;
            }
            $prev = $crnt;
        }
    }

    echo "counter: ".$counter."\n";
?>

有人可以证实我这是否可以解决：

n=100 // given
k=10  // given

counter = 0;

for(i=10; i<100; i++)
{
    if( (i/10)+(i%10) > k ) && ( (i/10)+(i%10) < 2*k )
        counter++;
}

total = counter^(n-1)

所有这些电话pow当然不会有帮助。

您可以做的是对所有“好”的两位数字进行映射。完成映射后，您所需要做的就是检查号码中的每一对数字是否正确。您可以通过连续除以 10 并模 100 来完成此操作。

只要你不给它一个负数，并且假设你已经设置了你的$good array.

function isgood( $num ) {
    while( $num >= 100 && $good[$num%100] ) {
        $num /= 10;
    }
    return $good[$num%100];
}

接下来最明显的事情是记住更大的序列。这就是动态规划原理。我们已经通过存储两位数序列的“优点”来记忆小序列。但您可以轻松地使用它们来生成 3、4、5、6 位数字的序列……无论您的可用内存允许多少。使用您已有的备忘录来生成带有一位额外数字的序列。

因此，如果您建立最多 5 位数字的记忆，那么每次除以 1000，就会获得很大的速度提升。