java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 - 代码物语-Let code talk - ITeye技术网站

java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 - 代码物语-Let code talk - ITeye技术网站

1.      * 题目：判断一个自然数是否是某个数的平方。当然不能使用开方运算 
2.      * 方法1.squareRoot0  二分查找 
3.      * 方法2.squareRoot1   
4.      * 考虑等差数列 1 3 5 7 9...发现 
5.      * 1^2=1 
6.      * 2^2=1+3 
7.      * 3^2=1+3+5 
8.      * ... 
9.      * 因此，N-1-3-5...若刚好可减至0，则N是某正整数的平方 

1.     //return sqrt(n).Use binary search  
2.     public static int squareRoot0(int n){  
3.         int low=1;  
4.         int high=n;  
5.         while(low<=high){  
6.             int mid=(low&high)+(high^low)/2;  
7.             if(mid*mid==n){//mid*mid,overflow? I don't know how to avoid this.  
8.                 return mid;  
9.             }else if(mid*mid<n){  
10.                 low=mid+1;  
11.             }else{  
12.                 high=mid-1;  
13.             }  
14.         }  
15.         return -1;  
16.     }  
17.       
18.     //return sqrt(n).  
19.     public static int squareRoot1(int n){  
20.         int d=1;//d=1,3,5...  
21.         int count=0;  
22.         while(n>0){  
23.             n-=d;  
24.             d+=2;  
25.             count++;  
26.             if(n==0){  
27.                 return count;  
28.             }  
29.         }  
30.         return -1;  
31.     }  

Read full article from java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 - 代码物语-Let code talk - ITeye技术网站