题目描述:
给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
进阶:不要 使用任何内置的库函数,如 sqrt 。
解法:
最直接的解法是遍历从 1 到 num 的整数,如果存在某个整数的平方是给定的 num,则 num 是一个完全平方数。如果num大于4,还可以只遍历 1 到 num / 2 之间的数,因为 x 大于 2 时,有。
但是当给定的num很大时以上的操作比较耗费时间,想要提高效率可以使用二分法或者牛顿法,这里采用牛顿法。
考虑函数 ,这个函数零点就有一个是 ,又因为f(x) 为凸函数,使用牛顿法可以求出这个正零点的近似值。
注意到,如果这个零点严格上是一个整数,那么求出的近似值一定时大于这个整数的浮点数,使用浮点数到整数的强制类型转换时会直接去掉浮点数的小数部分,也就是可以得到严格的零点x0,此时可以使用x0*x0==num验证。当然如果num不是完全平方数,得到的x0*x0一定不等于num。
代码如下:
bool isPerfectSquare(int num){
double x1 = num;
double x2;
while(true){
x2 = 0.5*(x1 + num / x1); // 下一点
printf("x1=%f, x2=%f\n", x1, x2);
if(x1 - x2 < 1e-5)
break;
x1 = x2;
}
int x = (int) x2;
printf("==%d==\n", x);
return (x*x==num);
}