找回老闆的密碼

問題：老闆忘了保險箱的密碼，他隻記得是四位數字，前兩個數字相同，後兩個數字也相同，并且該數字是一個數的平方，請幫忙找回該老闆的密碼

對于這個問題，至少有三種解法，因為我隻想到了三種:)

下面用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，如需轉載請自行聯系原作者