-1

如果数字 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)
4

3 回答 3

2

所有这些电话pow肯定不会有帮助。

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

如果你不给它一个负数，并且假设你已经设置了你的$good数组，这样的事情就可以解决问题。

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

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

因此，如果您为最多 5 位数字建立记忆，那么您每次除以 1000，并获得很大的加速。

于 2013-07-19T00:20:21.930 回答
1

n找到带有数字和最高数字的“不好数字”的数量d是一个简单的动态规划问题。

10^n是“好数字”加上“不好数字”的数量。

我不会给你更多的帮助。

于 2013-07-19T00:19:42.567 回答
0

您的算法计算有多少 2 位整数不好。然后它返回这个值的幂n - 1。这应该让你得到n不好的数字数量。如果你从数字整数的总数中减去这个值n，你应该得到你想要的。或者我们可以通过改变符号来避免这样做：

for($i=10; $i<100; $i++) {
 if( ($i/10) + ($i%10) > $k && ($i/10) + ($i%10) < 2*$k ) {
  $cnt++;
 }
}
$result = pow($cnt, $n-1);

这应该会为您提供好的n数字整数的数量，但让我们看看是否真的如此。

那么，cnt将给出好的 2 位整数的数量。因此，在前两个位置上，我们可以放置以下任何一个cnt：

0 1 2 3 4 5 ...
x y

那么，位置 1 和位置 2 呢？好吧，位置 1 由第一个放置固定。

0 1 2 3 4 5 ...
x y
  y z

所以我们必须证明存在 的cnt可能性z，我不明白为什么会这样，所以我会说算法是错误的。您的算法可能会多计。

于 2013-07-19T09:49:39.470 回答