演算法 之 aabb

題目描述：輸出所有形如aabb的4位完全平方數（即前兩位數字相等，後兩位數字也相等）。

分支和迴圈結合在一起時功能強大：

下麵列舉所有可能的結果aabb，然後判斷它們是否為完全平方數。註意a的範圍是1~9，但b可以是0.                                  

1  for(int a=1;a<=9;a++)
2      for(int b=0;b<=9;b++)
3         If(aabb是完全平方數)
4                printf（“%d\n”,aabb）;                       

        上面的程式並不完整——“aabb是完全平方數”是中文描述，而不是合法的C語言表達式，而aabb在C語言中也是另外一個變數，而不是把兩個數字a和b拼在一起。這個把這樣“不是真正程式”的“代碼”成為偽代碼（pseudocode）。雖然有一些正規的偽代碼的定義，但在實際應用中，並不需要太拘泥於為代碼的格式。主要的目標是描述演算法梗概，避開細節，啟發思路。

        寫出偽代碼之後，我們需要考慮如何把它變成真正的代碼。上面的偽代碼有兩個“非法”的地方；完全平方數判定，以及aabb這個變數。後者相對比較容易；用另外一個變數n=a×1100+b×11存儲即可。

接下來的問題就要困難一些了：如何判斷n是否為完全平方數？

方法一：PS（floor(x)，也寫做Floor(x)，其功能是“向下取整”，或者說“向下舍入”，即取不大於x的最大整數）

 1 #include<stdio.h>  
 2 #include<math.h>  
 3 int main()  
 4 {  
 5    for(int a=1;a<=9;a++)  
 6       for(int b=0;b<=9;b++)  
 7       {  
 8      　　int n=a*1100+b*11;//這裡開始使用n，因此在這裡定義n  
 9      　　int m=floor(sqrt(n)+0.5); 
10      　　if(m*m==n)  
11         printf("%d\n",n);  
12       }  
13    return 0;  
14 }  

         可不可以這樣寫？If(sqrt(n)==floor(sqrt(n))) printf(“%d\n”,n);即直接判斷sqrt(n)是否為整數。理論上當然沒問題，但這樣寫不保險，因為浮點數的運算（和函數)有可能存在誤差。假設在經過大量計算後，由於誤差的影響，整數1變成了0.99999999，floor的結果會是0而不是1,。為了減少誤差的影響，一般改成四捨五入，即floor（x+0.5）。如果難以理解，可以想象在數軸上把一個單位區間左移0.5個單元的距離。

Floor（x）等於1的區間為【1,2】，而floor（x+0.5）等於1的區間為【0.5,1.5】.

　　浮點運算可能存在誤差。再進行浮點運算比較時，應考慮到浮點誤差。

　　總結：小數部分為0.5的數也會受到浮點誤差的影響，因此任何一道嚴密的演算法競賽題目都需要想辦法解決這個問題

另一思路是枚舉平方根x，從而避免開方操作。

#include<stdio.h>  
int main()  
{  
   for(int x=1;;x++)     //for迴圈沒有指定迴圈條件  如果期待你從32開始可以不用判斷1000
   {  
      int n=x*x;  
　　　 if(n<1000) continue;
      if(n>9999)  break;  
      int high=n/100;  
      int low=n%100;  
      if(high/10==high%10&&low/10==low%10)  
     printf("%d\n",n);  
   }  
   return 0;  
} 

答案為

.