有人知道找出一个数字是完美平方的逻辑吗
本文关键字:完美 数字 一个 | 更新日期: 2023-09-27 18:00:51
可能重复:
最快的方法来确定一个整数';s的平方根是一个整数
有人知道找出一个数字是完全平方的逻辑吗?(Other than Newtons Method or Synthetic Division Method
(
For Eg:- 4, 16, 36, 64 are Perfect Squares.
我将以441
的形式给出输入,逻辑应该说它是否是完美平方。
这是亚马逊访谈中的一个问题。
我想去掉任何内置的函数
没有数学。Sqrt,甚至没有乘法:
static bool IsSquare(int n)
{
int i = 1;
for (; ; )
{
if (n < 0)
return false;
if (n == 0)
return true;
n -= i;
i += 2;
}
}
注意,平方是奇数整数的部分和。i
取值1、3、5、7。。。。部分和1,1+3=4,1+3+5=9。。。是正方形。因此,在n -= i
之后,我们从n
的原始值中减去了平方,我们可以将结果与0进行比较。
我会问面试官的第一个问题是,"问题的限制是什么?"也就是说,输入的数字能有多大?如果它足够小,那么你可以预先计算所有的完美平方,并将它们存储在字典中:
IDictionary<long, bool> squares = new Dictionary<long, bool>;
for(long i = 1; i*i <= MAX_NUM; ++i) {
squares[i*i] = true;
}
然后,要知道一个数字x是否是一个完美的正方形,你只需要检查正方形[x],看看它是否是真的。
类似的东西会起作用。
public Boolean IsSquare(double input)
{
double root, product;
Boolean isSquare,isGTInput;
root = 1;
product = 0;
isSquare = false;
isGTInput = false;
while (!isSquare && !isGTInput)
{
product = root * root;
if (product == input)
isSquare = true;
else if (product > input)
isGTInput = true;
root += 1;
}
return isSquare;
}