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代码-判断4个自然数大小
java代码-例子3-13 输入一个自然数,判断该数是否为素数
已知不相同的数不超过10000个,现在需要在其中查找某个自然数,如找到则输出并统计这个自然数出现的次数,如没找到则输出NO。 Input 输入由多组测试数据组成。 每组测试数据输入包含n+1行; 第一行是两个整数n...
C语言程序设计-求一个n位自然数的各位数字的积;(n 是小于10的自然数).c
本程序用CUDA编程在linux环境下实现了判断一个自然数是否为素数的操作。
跟我学Java面向对象程序设计技术及应用——识别某个自然数是否为质数(素数)的Java 程序实现示例 1 什么是质数(素数) 1 什么是质数(素数) 对于什么是质数(Prime Number),读者可以查询百科。在百科中的定义...
(2) 在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3) 按此规则进行处理,直到不能再添加自然数为止。 例如,set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。 注意半数集是多重集...
C语言程序设计-计算从1开始到n的自然数中偶数的平方的和,n由键盘输入,并在main()函数中输出。(n是偶数).c
用JAVA编写求自然数n到m的和,经过调试没有错误!
对任意给定的一个自然数n,将分母小于等于n的不可约的真分数按升序排列,并且在第一个分数之前加上0/1,在最后一个分数之后加上1/1,这个序列称为n级法雷数列,以Fn表示。如F5为:0/1,1/5, 1/4, 1/3, 2/5, 1/2, 3/5,...
当你输入一个数据时,系统会自动判断它是否是一个素数,很好用的,实用,简单。欢迎下载,并且是免费的。
输入一个自然数n,求1~n之间的所有自然数之和。
c++ 实现一个自然数表示成几个自然数的和,输出所有自然数和的表示方式
最大公约数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
属于课程实例,输出一个自然数的各项因子。
编写一个程序。要求将一个自然数拆分成任意个自然数相加,要求这几个数的乘积是最大的 自然数n拆分成m个自然数,要求这几个数的乘积是最大的,必为n/m及其临近数.
java代码-例子3-6 求前20个自然数的积。
输出大等于n的最小的完全平方数。 若一个数能表示成某个自然数的平方的形式,则称这个数为完全平方数 Tips:注意数据范围