当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-03-28   作者:bylijinnan   来源:转载   浏览次数:
摘要: public class SquareRoot { /** * 题目:判断一个自然数是否是某个数的平方。当然不能使用开方运算 * 方法1.squareRoot0 二分查找 * 方法2.squareRoot1 * 考虑等差数列 1 3 5 7 9...发现 * 1^2=1 * 2^2=1+3 * 3^2=1+3+5 * ...

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 search
	public 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;
	}
}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
几年前,Insus.NET有尝试把Array转换为IList接口,然后使用IList.Contains()方法。 当时评论时,也
顺时针打印出1到一个数的平方矩阵,假如数为3,则3的平方为9,要打印的矩阵为: 1 2 3 8 9 4 7 6 5
#include <iostream> using namespace std; int numOnesInBinary(int num) //统计一个数在内
public boolean hasNextInt() 如果通过使用nextInt()方法,此扫描器输入信息中的下一个标记可以解释
public boolean hasNextInt() 如果通过使用nextInt()方法,此扫描器输入信息中的下一个标记可以解释
WaitForSingleObject的应用 你还再为怎么判断一个程序是否结束而苦恼吗?或许你在想可以用一个循环
[color=#eeddcc] parseInt('db') 返回NaN 用parseInt('db')==NaN 返回false 解决方法: 判断是否是数
判断一个对象是否存在(赋值)的三种办法如下: if obj <> nil then ... if Boolean(obj) then .
文章结束给大家来个程序员笑话:[M] // 倏地的判断$a数组是不是是$b数组的集子 $a = array(135,138)
这是从CSDN看到的金山面试题 问题:数据库1中存放着a类数据,数据库2中存放着以天为单位划分的表30
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号