找回老板的密码

问题：老板忘了保险箱的密码，他只记得是四位数字，前两个数字相同，后两个数字也相同，并且该数字是一个数的平方，请帮忙找回该老板的密码

对于这个问题，至少有三种解法，因为我只想到了三种:)

下面用php来实现

// 解法一 

function getPwd() 

{ 

    $arr = array(); 

    for ($i = 1; $i < 9; $i++) 

    { 

        for ($j = 0; $j < 9; $j++) 

        { 

            $code = sqrt(1100 * $i + 11 * $j); 

            if (ceil($code) == $code) 

            { 

                $arr[] = $code * $code; 

            } 

        } 

    } 

    return $arr; 

} 

$rs = getPwd(); 

print_r($rs); 

算法很简单，一个形如AABB的数，一定是由1100*A + 11*B组成的，如果这个数开方与AB相等，那这个数就是密码。

运行结果：

Array 

( 

    [0] => 7744 

) 

只有一个，哦也。

虽说是找到密码了，但这个算法却不是最优的。嵌套循环会执行8*9=72次。

执行的时间为：0.0003秒

下面看看算法二：

// 解法二

function isValid($num) 

    return $num/1000%10 === $num/100%10 && $num/10%10 === $num%10; 

    for($i = 32; $i < 100; $i++) 

        if (isValid($i * $i)) 

            $arr[] = $i * $i; 

这个算法比上面的好一些，因为做了预判断，四位数的范围是1000-9999，所以循环的范围就限制到了32*32至100*100，循环次数为68次，执行时间约为0.0002秒

但这还不是最优的，下面看算法三：

// 算法三 

    $min = floor(sqrt(1100/121)); 

    $max = ceil(sqrt(9999/121)); 

    for ($i = $min; $i < $max; $i++) 

        $code = $i * $i * 121; 

        if (isValid($code)) 

            $arr[] = $code; 

先看一下执行时间：6.2942504882812E-5，输出结果：

这个算法做了更多的分析，形如AABB的能被11整除并能开方的数也一定能被121整除，于是可以确定循环的范围为1100/121的平方根至9999/121的平方根，取整后的范围为3-10，这意味着只需要循环7次就能找出所有的结果。可见，算法三是这三种算法中效率最高的。

本文转自 ustb80 51CTO博客，原文链接：http://blog.51cto.com/ustb80/1030910，如需转载请自行联系原作者