找回老板的密码

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

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

下面用php来实现

1. // 解法一 
2. function getPwd() 
3. { 
4.     $arr = array(); 
5.     for ($i = 1; $i < 9; $i++) 
6.     { 
7.         for ($j = 0; $j < 9; $j++) 
8.         { 
9.             $code = sqrt(1100 * $i + 11 * $j); 
10.             if (ceil($code) == $code) 
11.             { 
12.                 $arr[] = $code * $code; 
13.             } 
14.         } 
15.     } 
16.     return $arr; 
17. } 
18.  
19. $rs = getPwd(); 
20. print_r($rs); 

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

运行结果：

1. Array 
2. ( 
3.     [0] => 7744 
4. ) 

只有一个，哦也。

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

执行的时间为：0.0003秒

下面看看算法二：

1. // 解法二
   
2. function isValid($num) 
3. { 
4.     return $num/1000%10 === $num/100%10 && $num/10%10 === $num%10; 
5. } 
6.  
7. function getPwd() 
8. { 
9.     $arr = array(); 
10.     for($i = 32; $i < 100; $i++) 
11.     { 
12.         if (isValid($i * $i)) 
13.         { 
14.             $arr[] = $i * $i; 
15.         } 
16.     } 
17.     return $arr; 
18. } 
19. $rs = getPwd(); 
    
20. print_r($rs); 

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

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

1. // 算法三 
2. function isValid($num) 
3. { 
4.     return $num/1000%10 === $num/100%10 && $num/10%10 === $num%10; 
5. } 
6.  
7. function getPwd() 
8. { 
9.     $min = floor(sqrt(1100/121)); 
10.     $max = ceil(sqrt(9999/121)); 
11.     $arr = array(); 
12.     for ($i = $min; $i < $max; $i++) 
13.     { 
14.         $code = $i * $i * 121; 
15.         if (isValid($code)) 
16.         { 
17.             $arr[] = $code; 
18.         } 
19.     } 
20.     return $arr; 
21. } 
22. $rs = getPwd(); 
23. print_r($rs); 

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

1. Array 
2. ( 
3.     [0] => 7744 
4. ) 

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