有人知道判断一个数字是否为完全平方数的逻辑吗？

Question

可能重复：
确定整数的平方根是否为整数的最快方法

有人知道判断一个数字是否为完全平方数的逻辑吗？（除了牛顿法或合成除法法）

For Eg:- 4, 16, 36, 64 are Perfect Squares.

我将输入441，逻辑应该判断它是否为完全平方数。这是亚马逊面试中的一个问题。我希望不使用任何内置函数来解决。

- Developer

---

有什么好的算法可以确定一个输入是否为完全平方数？ - Paolo Moretti

如果技巧在输入本身上，那么由于441右边有一个数字1，所以它不可能是完全平方数。 - Jalal Said

@Jalal：什么，就好像81不是一样？ :-) - regularfry

@Jalal - 441 = 21^2。至少检查一下... 此外，取以1结尾的任何数字，例如52941，将其乘以自身，您将得到一个以1结尾的平方数。 - Kobi

@regularfry：@Kobi：我觉得这只是针对2的n次幂。 - Jalal Said

Answer 1

没有Math.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进行比较。

- Henrik

---

现在试着不用加法或乘法 :) - Kibbee

不得不说，我真的很喜欢这个算法。 - Kibbee

尽管从快速基准测试来看，使用乘法似乎更快。 - Kibbee

惊人的算法，佩服啊。我后悔为什么讨厌数学 :) - Anoop

我希望我能为你提供数百万的赏金...真的非常感激... - Deepak Ingole

Answer 2

我会尽力为您翻译中文。以下是需要翻译的内容：

我会问面试官的第一个问题是：“问题的限制条件是什么？”也就是说，输入数字可以有多大？如果足够小，那么您可以预先计算所有完美平方并将它们存储在字典中：

IDictionary<long, bool> squares = new Dictionary<long, bool>;
for(long i = 1; i*i <= MAX_NUM; ++i) {
    squares[i*i] = true;
}

然后，要判断一个数字x是否是完全平方数，只需检查squares[x]是否为真即可。

- dcp

Answer 3

类似这样的东西会起作用。

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;

}

- Kibbee

---

这个与我所问的是否相符？ - Developer

抱歉，我不明白你在问什么。 - Kibbee

由于您使用了 root*root，这是否符合我所问的要求？ - Developer

我认为乘法不算是“内置函数”。如果你不能使用乘法运算符，那么可能是不可能的。 - Kibbee