算法'好'号 [英] Algorithm for 'good' number

问题描述

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

我在PHP做了实现这一点，但复杂性是很大的（我在寻找那些好号和计数他们，所以复杂度为O（10 ^ N））。

 ＆LT; PHP
    $ N = 5;
    $ K ​​= 5;

    $分钟= $ K * 1;
    $最大= $ K * 2;
    $计数器= 0;

    为（$ I =战俘（10，$ N-1）; $ I＆LT;战俘（10，$ N）; $ I ++）
    {
        $数= $ I;
        $preV = $编号％10;
        $数= $数/ 10;

        而（$数量＆GT; = 10）
        {
            $ CRNT = $编号％10;
            $数= $数/ 10;
            如果（（$ CRNT + $preV）GT; $分钟，（$ CRNT + $preV）LT; $最大值）{
                回声好一些：$ I \ N的;
                $计数器++;
            }
            $preV = $ CRNT;
        }
    }

    回声反：$计数\ N;
？＆GT;
 

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

  N = 100 //给出
设k = 10 //给定

计数器= 0;

对于（I = 10; I＆LT; 100;我++）
{
    如果（（I / 10）+（ⅰ％10）＆GT; K）＆安培;＆安培; （（I / 10）+（ⅰ％10）2 * k）的
        反++;
}

总=计数器^（N-1）
 

解决方案

所有这些调用 POW 肯定不会帮助。

你可以做的就是让所有的好的两位数字的映射。一旦你有你的映射，所有你需要做的是检查每一个对数字的号码是​​不错的。为此，您可以通过连续除以10和模100。

这样的事情会做的伎俩，只要你不给它一个负数，并假设你已经设置了 $好阵列。

 函数isgood（$ NUM）{
    而（$ num个＆GT; = 100安培;＆安培; $好[$ NUM％100]）{
        $ NUM / = 10;
    }
    返回$好[$ NUM％100]。
}
 

下一个最明显的事情是memoize的大序列。这是一个动态编程原理。我们已经通过存储2位数字序列的善已经memoized小序列。但是你可以很容易地使用这些生成的3，4，5，6位数......无论你的可用内存允许序列。使用已有的备忘录，以产生一个额外的数字序列。

所以，如果你建立了memoisation达5位数字，那么你每次除以1000，并获得了巨大的速度提升。

A give number x is 'good' if the sum of any two consecutive digit of the number x are between k and 2k. I need to find an algorithm that for a given number k and a given number n, find how many 'good' n-digit numbers exist.

I made an implementation for this in PHP, but the complexity is to big (i am searching for all those 'good' number and counting them, so the complexity is 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";
?>

Can someone confirm me if this can be the solution:

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)

解决方案

All those calls to pow certainly won't be helping.

What you can do is make a mapping of all the two-digit numbers that are 'good'. Once you have your mapping, all you need to do is check that every pair of digits in your number is good. You can do this by successive division by 10 and modulo 100.

Something like this would do the trick, provided you don't give it a negative number, and assuming you've set up your $good array.

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

The next most obvious thing to do is memoize larger sequences. This is a dynamic programming principle. We've already memoized small sequences by storing the 'goodness' of 2-digit sequences. But you could easily use those to generate sequences of 3, 4, 5, 6 digits... Whatever your available memory allows. Use the memos you already have in order to generate the sequences with one extra digit.

So, if you built up memoisation for up to 5-digit numbers, then you divide by 1000 every time, and get a great speedup.

这篇关于算法'好'号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！