网站开发.net,商城开发价格,分析凡客诚品失败的原因,怎样设计自己的网站文章目录 给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。原理牛顿法#xff08;数值分析中使用到的#xff09;:二分法 解决方案java 实现实例执行结果 python 实现实例 给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。
由于返回类型是整数计算并返回 x 的 算术平方根 。原理牛顿法数值分析中使用到的:二分法 解决方案java 实现实例执行结果 python 实现实例 给你一个非负整数 x 计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1
输入x 4 输出2 示例 2
输入x 8 输出2 解释8 的算术平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。
提示
0 x 231 - 1 来源力扣LeetCode 链接https://leetcode-cn.com/problems/sqrtx 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 原理
牛顿法数值分析中使用到的:
在迭代过程中以直线代替曲线用一阶泰勒展式即在当前点的切线代替原曲线求直线与 xx 轴的交点重复这个过程直到收敛。
首先随便猜一个近似值 xx然后不断令x等于x和a/x的平均数迭代个六七次后 xx 的值就已经相当精确了构造方程x − a2 0令f ( x ) x − a 2 ,然后不断用(x,f(x))的切线来不断逼近方程$x^{2} $ 上述函数导数为2x也就是说函数上任意一点(x,f(x))处的切线斜率为2x。
那么x-f(x)/(2x)就是一个比x更接近的近似值代入f ( x ) x 2 − a 可以得到x − ( x2 − a ) / ( 2 x )变形即可得到(xa/x)/2 这里的a是目标值
二分法
这道题目由于只要求取开平方后的整数部分因此搜索范围有限可以考虑使用二分法。
构造数组从0到输入x该数组中每个元素与其所在位置相等定义两个指针左指针left和右指针right初始位置分别位于数组两端
执行循环循环的控制条件是左指针不能跑到右指针的右边去每轮循环获得中点所在位置查看该数的平方s与输入x之间的大小关系 1s x相当于找到了开方结果直接返回这个数 2s x平方结果较大删除数组右半部分 3s x平方结果较小删除数组左半部分
跳出循环时返回右指针所在位置。
解决方案
二分查找法应用于搜索平方根的思想很简单其实就是“猜”但是是有策略的“猜”用“排除法”在有限的区间里一次排除一半的区间元素最后只剩下一个数这个数就是题目要求的向下取整的平方根整数。
牛顿法最初提出的时候是用于求解方程的根它的基本思想是“以直代曲”在迭代中搜索得到方程的近似解。
java 实现
实例
public class Solution {public int mySqrt(int x) {if (x 0) {return 0;}// 注意针对特殊测试用例例如 2147395599// 要把搜索的范围设置成长整型long left 1;long right x / 2;while (left right) {// 注意这里一定取右中位数如果取左中位数代码会进入死循环// long mid left (right - left 1) / 2;long mid (left right 1) 1;long square mid * mid;if (square x) {right mid - 1;} else {left mid;}}// 因为一定存在因此无需后处理return (int) left;}}执行结果 python 实现
实例
class Solution(object):def mySqrt(self, x)::type x: int:rtype: int核心思想1. 直接return int(sqrt(x)) 直接ac2. 使用暴力遍历方法 for i in range(1,x) 尝试 i*i 是否 x 或者 i*i x 但是 (i1)(i1) x3. 使用牛顿法数值分析中使用到的:在迭代过程中以直线代替曲线用一阶泰勒展式即在当前点的切线代替原曲线求直线与 xx 轴的交点重复这个过程直到收敛。首先随便猜一个近似值 xx然后不断令x等于x和a/x的平均数迭代个六七次后 xx 的值就已经相当精确了构造方程x - a^{2} 0令f(x)x-a^{2},然后不断用(x,f(x))的切线来不断逼近方程x^{2}上述函数导数为2x也就是说函数上任意一点(x,f(x))处的切线斜率为2x。那么x-f(x)/(2x)就是一个比x更接近的近似值代入f(x)x^{2}-a可以得到x-(x^{2}-a)/(2x)变形即可得到(xa/x)/2 这里的a是目标值if x 0:return 0cur_x x # 令初始值为xwhile cur_x-x/cur_x 1e-6:cur_x (cur_x x/cur_x)/2 # 利用公式(xa/x)/2计算得到新的areturn int(cur_x)if __name__ __main__:s Solution()print(s.mySqrt(8))
