`

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

 
阅读更多

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

0
0
分享到:
评论
1 楼 GoldRoger 2016-05-11  
第二个方法很好

相关推荐

    java代码-例子3-13 输入一个自然数,判断该数是否为素数

    以下是一个简单的Java程序,用于判断输入的自然数是否为素数: ```java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); ...

    判断一个数是否为素数的java代码

    在Java编程中,判断一个数是否为素数是常见的算法问题,尤其对于初学者来说,掌握这个概念及其实现方法至关重要。下面我们将详细讲解如何编写一个Java程序来判断一个整数是否为素数。 首先,我们需要理解素数的定义...

    JAVA中判断一个整数是否为质数

    在Java编程语言中,判断一个整数是否为质数是一个常见的数学问题,也是计算机科学基础课程中的典型示例。质数定义为只能被1和它本身整除的大于1的自然数,例如2、3、5、7、11等。在实际应用中,检查一个数是否为质数...

    C语言程序设计-求一个n位自然数的各位数字的积;(n 是小于10的自然数).c

    C语言程序设计-求一个n位自然数的各位数字的积;(n 是小于10的自然数).c

    java代码-判断4个自然数大小

    在Java编程语言中,判断四个自然数的大小是一项基本任务,常常用于排序或者比较操作。以下将详细讲解如何实现这个功能,并提供相关的编程知识点。 首先,我们要了解自然数的概念。在数学中,自然数通常指的是非负...

    Search Number 科研调查时得到了n个自然数,每个数均不超过1500000000。已知不相同的数不超过10000个,现在需要在其中查找某个自然数,如找到则输出并统计这个自然数出现的次数,如没找到则输出NO。

    本题是一道经典的查找问题,涉及到的数据规模为:科研调查中获得了一系列的自然数(总数为n),这些数字都不超过1500000000,并且不同的数字不会超过10000个。题目要求在这些数字中查找特定的自然数x,如果找到了,...

    java 小程序,求素数和判断闰年

    在这个“java小程序”中,我们有两个关键的算法实现:检查一个数是否为素数以及判断是否为闰年。 首先,让我们深入理解素数的概念。素数是大于1的自然数,除了1和它自身外,不能被其他自然数整除的数。例如,2、3、...

    java编写看一个数是否是素数

    今天,我们将学习使用 Java 编写一个程序来判断一个数是否是素数。 首先,让我们来了解什么是素数。素数(Prime Number)是一个大于1的自然数,只能被1和自己整除。例如,2、3、5、7、11等都是素数。判断一个数是否...

    用JAVA编写求自然数n到m的和

    这个程序的核心是for循环,它是Java中的控制流结构之一,允许我们重复执行一段代码直到满足某个条件。在求和问题中,我们从n开始,每次迭代增加1,直到达到或超过m。循环体内的代码负责将当前的i值添加到总和中。 ...

    CUDA程序并行实现一个自然数是否为素数的判断

    在本项目中,“CUDA程序并行实现一个自然数是否为素数的判断”是通过CUDA技术在Linux环境下对自然数进行高效素数检测的实现。下面将详细讲解相关知识点。 1. **CUDA编程模型** CUDA编程模型允许开发者直接编写C/...

    c语言:实现一个函数,判断一个数是不是素数

    在C语言中,判断一个数是否为素数是一项常见的编程任务。素数是大于1的自然数,除了1和它自身外,不能被其他自然数整除的数。本篇文章将详细讲解如何通过编写C语言函数来实现这个功能。 首先,我们需要理解素数的...

    Java-exercise.rar_Java,Smith数_smith

    具体来说,一个Smith数是这样的:它的每一位数字之和等于它的素因数(不包括1)的每一位数字之和。例如,12345是一个Smith数,因为1+2+3+4+5=1+2+5+7,而12345的素因数有5, 7, 11, 13(即5×7×11×13),它们的数字...

    java小练习,Java练习小程序,Java必用

    - 给定一个正整数n,判断它是否为完全平方数。 - 完全平方数定义:可以表示为某个整数的平方。 - 可以使用Math.sqrt()函数求解平方根,并判断结果是否为整数。 14. **日期计算**: - 计算两个日期之间的天数差...

    java:判断一个数是否为素数的函数

    判断一个数是否为素数是算法与编程中经常遇到的问题,也广泛应用于各种算法设计之中。在Java语言中,可以通过编写函数来实现这一判断。 Java代码块中的函数isPrime是一个典型的用于判断整数是否为素数的函数。这个...

    JAVA基础经典数值运算代码75个

    这个"JAVA基础经典数值运算代码75个"集合,显然涵盖了多种基础和经典的数值运算示例,包括但不限于兔子数列(Fibonacci序列)、完数判断、素数检测以及数组中的最大和次大数等。下面我们将详细探讨这些知识点。 ...

    C# 判断一个数是否为素数

    本篇文章将深入探讨如何使用C#来判断一个数是否为素数,这不仅是对C#语言基础技能的实践,也是对算法理解的深化。 ### C# 判断一个数是否为素数 #### 知识点一:素数定义 首先,了解什么是素数非常重要。素数...

    Java经典编程题(附答案)

    寻找符合条件的整数,需要检查每个数加100和268后是否为完全平方数,可以通过平方根和平方运算来判断。 【程序14】 计算日期在当年的位置,需要考虑闰年的情况,对于3月之前的天数需要额外处理。 【程序15】 对三...

    JAVA语言编写计算器

    在编程领域,使用Java语言编写一个计算器是一项基础且实用的任务,它可以执行基本的数学运算,同时还能进行一些高级计算,如开平方根、判断完数和素数等。以下是对这些知识点的详细解释: 1. **Java语言**:Java是...

Global site tag (gtag.js) - Google Analytics