当前位置:网站首页>LeetCode69:牛顿迭代法和二分法求解x的平方根
LeetCode69:牛顿迭代法和二分法求解x的平方根
2022-08-11 10:53:00 【哆啦k梦0219】
一.牛顿迭代法
首先随便猜一个近似值 n,然后不断令 n 等于 n 和 x/n 的平均数,迭代个六七次后 n 的值就已经相当精确了。
例如,我想求根号 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..
….
这种算法的原理很简单,我们仅仅是不断用 (x, f(x))的切线来逼近方程 x^2-n=0的根。根号 n 实际上就是 x^2-n=0的一个正实根,这个函数的导数是 2x。也就是说,函数上任一点 (x,f(x)) 处的切线斜率是 2x。那么,x-f(x)/(2x) 就是一个比 x 更接近的近似值。代入 f(x)=x^2-a得到 x-(x^2-a)/(2x),也就是 (x+a/x)/2。同样的方法可以用在其它的近似值计算中。
代码如下:(近似值n取x)
class Solution {
public:
int mySqrt(int x)
{
if(x==0)
return 0;
int n = x;//n 为随便猜的值x
return int(newton(n,x));
}
double newton(double n,int x)
{
double curr = (n+x/n)/2;
if(curr == n)
{
return curr;
}
else
return newton(curr,x);
}
};
二.二分法
//0-x有序,采用二分法
class Solution {
public:
int mySqrt(int x)
{
int left = 0;
int right = x;
int ans = -1;//储存符合条件:mid*mid<=x 的值
if(x==1)
return 1;
else if(x==0)
return 0;
while(right>=left)
{
int middle = left+(right-left)/2;//(left+right)/2
if(middle*middle<=x)
{
ans = middle;
left = middle+1;
}
else
{
right = middle-1;
}
}
return ans;
}
};
边栏推荐
- 2. 类与对象——封装
- 【Study Notes】Unused graph theory knowledge
- Ali Ermian: Do you know how to tune the JVM?
- 什么是架构基本概念和架构本质
- 爆料!前华为微服务专家纯手打500页落地架构实战笔记,已开源
- 计算数组某个元素的和
- The crawler is encapsulated into an api
- mySQL transaction and its characteristic analysis
- Neural network visualization has 3 d version of the, the United States to fall!(open source)
- C# 调用高德地图API获取经纬度以及定位【万字详解附完整代码】
猜你喜欢
随机推荐
数据库的索引和其底层数据结构
[Central Task Scheduling System - Communication Development]
天花板级微服务大佬总结出这份451页笔记告诉你微服务就该这么学
chrome插件开发入门-保姆级攻略
servlet——servlet介绍 | 发布动态资源
沃土云创计划重磅来袭
C语言手写魂斗罗(一)
Neural network visualization has 3 d version of the, the United States to fall!(open source)
Getting Started with Chrome Plug-in Development - Nanny Level Raiders
爬虫封装成api
4. 继承
【Mask2Former】 解决代码中一些问题
【中央任务调度系统—通信开发】
独家采访 | 智能源于自发产生而非计划:进化论拥趸,前OpenAI研究经理、UBC大学副教授Jeff Clune
SAP 产品增强技术回顾
漫画手绘之临摹篇
如何建立编程思想和提高编程思想
十九、一起学习Lua 垃圾回收
mysql常用的一些时间函数记录
算法---跳跃游戏(Kotlin)