java-判断一个自然数是否是某个数的平方。当然不能使用开方运算

编程技术  /  houtizong 发布于 3年前   56

public class SquareRoot {/** * 题目：判断一个自然数是否是某个数的平方。当然不能使用开方运算 * 方法1.squareRoot0二分查找 * 方法2.squareRoot1 * 考虑等差数列 1 3 5 7 9...发现 * 1^2=1 * 2^2=1+3 * 3^2=1+3+5 * ... * 因此，N-1-3-5...若刚好可减至0，则N是某正整数的平方 */public static void main(String[] args) {for(int i=0;i<100;i++){squareRootOf(i);}}public static void squareRootOf(int n){if(n<1){return;}int x0=squareRoot0(n);if(x0!=-1){System.out.printf("%d*%d=%d%n", x0,x0,n);}int x1=squareRoot1(n);if(x1!=-1){System.out.printf("%d*%d=%d%n", x1,x1,n);}}//return sqrt(n).Use binary searchpublic static int squareRoot0(int n){int low=1;int high=n;while(low<=high){int mid=(low&high)+(high^low)/2;if(mid*mid==n){//mid*mid,overflow? I don't know how to avoid this.return mid;}else if(mid*mid<n){low=mid+1;}else{high=mid-1;}}return -1;}//return sqrt(n).public static int squareRoot1(int n){int d=1;//d=1,3,5...int count=0;while(n>0){n-=d;d+=2;count++;if(n==0){return count;}}return -1;}}