admin管理员组

文章数量:815321

牛顿迭代法——求根好手

何为牛顿迭代法,简单来说就是

不断用 (x, f(x))的切线来逼近方程 的根。根号 a 实际上就是 的一个正实根

 

 

例如,我想求根号 2 等于多少。假如我猜测的结果为 4,虽然错的离谱,但你可以看到使用牛顿迭代法后这个值很快就趋近于根号 2 了:

( 4 + 2/ 4 ) / 2 = 2.25

( 2.25 + 2/ 2.25 ) / 2 = 1.56944..

( 1.56944..+ 2/1.56944..) / 2 = 1.42189..

( 1.42189..+ 2/1.42189..) / 2 = 1.41423..

 具体推导过程参考百度:点这里

核心就是下面一段代码

class Solution{public double sqrts(double x , double s = x)){double res = (x + s / x) / 2;if (res == x) {return x;} else {return sqrts(res);}} 
}

具体题目可以参考下面的leetcode题目

69. Sqrt(x)

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

367. 有效的完全平方数

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

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

示例 :

输入:num = 16
输出:true

本文标签: 牛顿迭代法求根好手