写点什么

LeetCode 题解:69. x 的平方根,牛顿迭代法 + 递归,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 02 月 03 日
LeetCode题解:69. x 的平方根,牛顿迭代法+递归,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/sqrtx/


解题思路:


  1. 要理解牛顿迭代法,我们需要先回顾一下导数,或者可以看这一篇[导数入门](https://www.shuxuele.com/calculus/derivatives-introduction.html)。

  2. 题解参考了二分查找 + 牛顿法(Python 代码、Java 代码)、[牛顿迭代法](https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/)、[69. x 的平方根-二分查找, 牛顿法](https://leetcode-cn.com/problems/sqrtx/solution/69-x-de-ping-fang-gen-er-fen-cha-zhao-niu-dun-fa-b/)。

  3. 根据题意,该题是这样一个方程 $x^{2}=a$,已知 $a$求 $x$。可以将其用函数 $f(x)=x^{2}-a$代替。

  4. 这个函数的导数是 $2x$,也就是 $2x0=\cfrac{f(x)-f(x0)}{x-x_0}$。

  5. 将 $f(x)=0$带入,可以得到 $2x0=\cfrac{-f(x0)}{x-x_0}$。

  6. 将 $f(x0)=x0^{2}-a$带入,可以得到 $2x0=\cfrac{a-x0^{2}}{x-x_0}$。

  7. 将等式整理,可以得到 $x=\cfrac{x0+\cfrac{a}{x0}}{2}$。


/** * @param {number} x * @return {number} */var mySqrt = function (x) {  function sqrt(x0) {    // 当遇到第一个x0 * x0 <= x的值时,表示已经得到最接近的结果,将x0的整数部分返回即可    // 用Math.floor将x0*x0向下取整    // 避免例如TestCase: 5,会出现x0 * x0=5.000000000000001,造成死循环    if (Math.floor(x0 * x0) <= x) {      return Math.floor(x0);    }
// 套用分析得到的迭代公式,计算出新的x0 x0 = (x0 + x / x0) / 2;
return sqrt(x0); }
return sqrt(x);};
复制代码


发布于: 2021 年 02 月 03 日阅读数: 15
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:69. x 的平方根,牛顿迭代法+递归,JavaScript,详细注释