`
lyw985
  • 浏览: 40752 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

判断一个自然数是否是某个数的平方

 
阅读更多
判断一个自然数是否是某个数的平方。


51CTO上的参考答案如下 写道

假设待判断的数字是 N。

方法1:

遍历从1到N的数字,求取平方并和N进行比较。

如果平方小于N,则继续遍历;如果等于N,则成功退出;如果大于N,则失败退出。

复杂度为O(n^0.5)。

方法2:

使用二分查找法,对1到N之间的数字进行判断。

复杂度为O(log n)。

方法3:

由于

(n+1)^2
=n^2 + 2n + 1,
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)

注意到这些项构成了等差数列(每项之间相差2)。

所以我们可以比较 N-1, N - 1 - 3, N - 1 - 3 - 5 ... 和0的关系。

如果大于0,则继续减;如果等于0,则成功退出;如果小于 0,则失败退出。

复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法,所以速度会更快些。


方法3不是很看得懂。。。

我的想法 写道

public static boolean getResult(int number) {
	int in = number;
	int num = 0;
	for (int i = 2; i <= in;) {
		if (in % i == 0) {
			in = in / i;
			num++;
			if (in == 1 && num % 2 == 0) {
				return true;
			}
		} else {
			if (num % 2 != 0) {
				return false;
			}
			i++;
		}
	}
	return false;
}



不知道有木有更好的算法
分享到:
评论

相关推荐

    Java经典编程题(附答案)

    完数是指一个数等于其所有因子(除了自身外)之和。遍历1到1000,计算因子和,若等于原数则为完数。 【程序10】 球下落反弹问题涉及等比数列求和,每次下落的高度减半,需要计算前10次落地的总距离和第10次反弹的...

    谷歌笔试题2010

    不使用开方运算来判断一个自然数是否为另一个数的平方。 **解决方案**: 1. **方法1**: - 遍历从1到N的所有数字,计算每个数字的平方并与N比较。 - 如果平方小于N,继续遍历下一个数字; - 如果平方等于N,则...

    ACM之特殊的数

    快速判断一个数是否为完全平方数的方法有牛顿迭代法或位操作技巧。 3. **回文数**:回文数是指正读反读都一样的数,如121或12321。这类问题通常涉及到字符串处理和双指针技术。 4. **斐波那契数列**:斐波那契数列...

    2.1数字的美(上)1

    几乎所有的实数都是超越数,但确定一个特定的数是否超越通常非常困难。 总的来说,这个主题涵盖了从基础的数字类型到更高级的数学概念,包括数论、集合论和实数理论,这些都是算法设计和分析的基础。通过这样的学习...

    人教版五年级数学(下册)课课练(43页).doc

    另一个数是7。最小的自然数,其等于除了它本身以外的所有因数之和,这个数是6(1+2+3=6)。 - 最大的两位数是99,设第二个数为x,则99+3x-4=第二个数。解这个方程可得x的值。对于有3个因数的最小自然数,它是完全...

    自然数n次幂的求和公式及其因式分解的Matlab求解.zip

    自然数的n次幂求和公式是数学中的一个重要概念,特别是在数论和组合数学中有着广泛应用。这个公式描述了从1到某个正整数n的所有自然数的n次幂之和。例如,当我们想要计算1^2 + 2^2 + 3^2 + ... + n^2的和时,就涉及...

    小学五年级奥数题第1课《数的整除问题》试题附答案.docx

    通过以上知识点的学习,学生应能够掌握如何判断一个数是否能被另一个数整除,以及如何利用整除性质进行推理和计算。同时,通过配套的奥数试题和答案,学生可以检验自己的理解和应用能力,不断巩固和提高对数的整除...

    多线程求连续质数和的完全幂

    判断一个数是否为完全平方数,可以采用数学方法,如检查其平方根的整数部分是否等于其平方根的浮点部分。 然后,我们来看“多线程”。在计算机编程中,多线程是指程序中同时执行多个独立的执行路径。通过多线程,...

    C语言提升之路基础100题全新整理

    5. **完全平方数**:一个数可以表示为某个整数的平方,例如1、4、9等。在程序3中,需要找到一个数,使得加上100和168后分别成为完全平方数。 6. **水仙花数**:三位数,其各位数字的立方和等于原数。例如,153是一...

    五年级数学上册 第三单元《倍数与因数》单元试卷 北师大版 试题.doc

    一个数是6的倍数,它一定是2和3的倍数;个位上是3的倍数的数不一定能被3整除。 10. **选择题**:在1~20的数中,6的倍数有4个;合数至少有3个因数;1既不是质数也不是合数;最小的合数是4;偶数不一定是合数,如2是...

    百度、华为、因特尔、微软、谷歌等大公司笔试面试

    4. **判断平方数**:面试题4讨论了三种方法来判断一个自然数是否是某个数的平方。方法1是直接遍历,时间复杂度为O(sqrt(n));方法2是使用二分查找,时间复杂度为O(log n);方法3是基于等差数列的性质,通过减法判断...

    沪科版七年级数学(下册)复习知识点总结.doc

    平方根是指一个数的平方等于另一个数的情况。例如,如果 a 的平方等于 b,那么 a 是 b 的平方根。平方根可以用 ± 表示,其中 ± 表示正负两个可能的结果。正数的平方根有两个,互为相反数;0 的平方根是 0;负数...

    四年级奥数数字谜综合(有答案).doc

    12. **数字的倍数性质**:如果一个数是另一个数的倍数,那么它的一些属性(如除以质数的余数)也会传递给这个倍数。在解题中,利用这一性质可以确定数字的可能值。 综上所述,这些知识点在解决四年级奥数数字谜问题...

    湖南省二级VF程序设计题

    1. **求出[10,1000]内所有能被7和9中至少一个数整除的整数的个数** 此题考察的是循环结构和条件判断语句。在VF中,使用`FOR`循环遍历指定范围内的数字,并利用`MOD`函数判断数字是否能被7或9整除。代码中出现了一...

    欧拉计划.doc

    斐波那契数列是一个经典的数学序列,其中每个数是前两个数的和。本例中,代码通过迭代生成斐波那契数列直到某一值,并检查每个数是否为偶数,如果是,则将其加入到总和中。最终输出所有偶数项的总和。 **关键概念**...

    2021年人教版五年级数学下册第二单元测试卷及答案二数学知识.doc

    2. 因数与倍数关系:一个数a是另一个数b的倍数,意味着存在某个整数c使得a = b × c;反之,b是a的因数。例如,在3×4=12中,12是3和4的倍数,而3和4是12的因数。 3. 自然数、偶数与奇数:最小的自然数是0,它不是...

    2015年小升初参考:重点中学分班考试往年试题(2).doc

    然后判断该数是否能为某个数的平方。 16、这是一道关于水管问题的题目。甲乙水管同时开启,排水管关闭,注水速度加快,可以计算出甲乙水管同时开启的注水效率。再根据题意,水池四分之一注水用了相同的时间,从而...

    程序框图及算法的基本逻辑结构.doc

    例如,判断一个数是否为质数的算法就包含了条件构造,先检查数是否大于1,然后依次检查能否被2到其平方根之间的数整除。 3. **循环构造**:循环构造允许重复执行一段代码直到满足某个条件为止。在程序框图中,循环...

    2论攻坚-数字推理+尹燕+(讲义+笔记)(2021文职招考系统班:1期).pdf

    例如数列1, 16, 49, 100, 169中的每一项都是1、4、7等自然数的平方。 3. 分数数列:分数数列由分数构成,需要找出分数之间的规律。 4. 图形数阵:图形数阵涉及的是图形中数字的排列规律。这种题目通常需要将二维的...

    五年级上册期末试数学题3精选.doc

    20. 最小倍数的概念:一个数的最大因数和最小倍数都是它本身。所以,如果一个数的最大因数是15,它的最小倍数也是15。 21. 判断题: - 杯子翻转后朝上的概率问题:10次翻转后,朝上的概率是1/2。 - 面积相等的...

Global site tag (gtag.js) - Google Analytics