2021-11-04有效的完全平方数

题目描述:

给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false 。

进阶:不要 使用任何内置的库函数,如  sqrt 。

解法:

最直接的解法是遍历从 1 到 num 的整数,如果存在某个整数的平方是给定的 num,则 num 是一个完全平方数。如果num大于4,还可以只遍历 1 到 num / 2 之间的数,因为 x 大于 2 时,有2021-11-04有效的完全平方数

但是当给定的num很大时以上的操作比较耗费时间,想要提高效率可以使用二分法或者牛顿法,这里采用牛顿法。

考虑函数 2021-11-04有效的完全平方数 ,这个函数零点就有一个是 2021-11-04有效的完全平方数 ,又因为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);    
}

上一篇:简单迭代法求方程根


下一篇:全球时区概念