文档章节

69. Sqrt(x)

Do0M
 Do0M
发布于 2017/08/26 21:35
字数 279
阅读 3
收藏 0

Implement int sqrt(int x).

Compute and return the square root of x.

实现一个求平方根的算法,直接调用sqrt好像也行,不过不能用float,要用int记录(2147395599开平方是46339.99989,如果用float直接变成46340)。

int mySqrt(int x) {
    int a=sqrt(x);
    return a;
}


一般有两种算法,二分法和牛顿迭代法(泰勒公式)。还有一种是卡马克的开平方根取倒数改的算法,速度非常快,可惜是估计值,精度很低,所以不行。

二分法:

int mySqrt(int x)
{
	long long low = 0;
	long long high = x;

	while (low < high)
	{
		long long mid = (high - low) / 2 + low;

		if (mid * mid == x)
			return mid;
		else if (mid * mid > x)
			high = mid - 1;
		else
			low = mid + 1;//因为是取整数,所以直接加1就可以
	}

	return low * low > x ? low - 1 : low;
}

牛顿迭代法:

long r = x;
    while (r*r > x)
        r = (r + x/r) / 2;
    return r;

关于卡马克求平方根的论述:

http://blog.csdn.net/hunterlew/article/details/45341253

文中可以看到,虽然迭代公式和牛顿迭代略有不同(卡马克求的是开根号取导数,所以目标函数不同),但本质一样。


本文转载自:http://blog.csdn.net/limk96/article/details/72901599

共有 人打赏支持
Do0M
粉丝 0
博文 8
码字总数 24
作品 0
私信 提问
69. Sqrt(x) - LeetCode

Question 69. Sqrt(x) Solution 题目大意: 求一个数的平方根 思路: 二分查找 Python实现:

yysue
10/01
0
0
Leetcode 69. Sqrt(x)

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Binary Search Newton's Method Reference https://leetcode.com/problems/sqrtx/description/......

SnailTyan
08/03
0
0
【机器学习实战】极大似然法

http://baike.baidu.com/link?url=3Ej1VIItwWd35sXeoRWRhcJkJLCFvzPzNIoTkAfai8ZIS4Ppcch4maQ25FjNCU1Eplsp4k3oPKLyv6VIsPhsq 一、 最大似然法是一种具有理论性的点估计法,基本思想是,当从......

HarryWu
2016/03/21
52
0
LeetCode 69. Sqrt(x)

分析 难度 易 来源 https://leetcode.com/problems/sqrtx/description/ 题目 Implement . Compute and return the square root of x, where x is guaranteed to be a non-negative integer.......

flowingfog
10/19
0
0
LeetCode算法题-Sqrt(Java实现)

这是悦乐书的第158次更新,第160篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第17题(顺位题号是69)。 计算并返回x的平方根,其中x保证为非负整数。 由于返回类型是整数,...

小川94
11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

day02:管道符、shell及环境变量

1、管道符:"|" 用于将前一个指令的输出作为后一个指令的输入,且管道符后面跟的是命令(针对文档的操作):cat less head tail grep cut sort wc uniq tee tr split sed awk等) [root@localho...

芬野de博客
13分钟前
4
0
Kubernetes系列——Kubernetes 组件、对象(二)

一、Kubernetes 组件 介绍了Kubernetes集群所需的各种二进制组件。 Master 组件 Master组件提供集群的管理控制中心。Master组件可以在集群中任何节点上运行。但是为了简单起见,通常在一...

吴伟祥
23分钟前
4
0
Flink-数据流编程模型

1、抽象等级 Flink提供了不同级别的抽象来开发流/批处理应用程序。 1) 低层级的抽象 最低层次的抽象仅仅提供有状态流。它通过Process函数嵌入到DataStream API中。它允许用户自由地处理来自一...

liwei2000
40分钟前
5
0
Java开发Swing实战JFrame和JTabbedPane容器的用法详细解析

概述: 项目是一个桌面程序,涉及标签和按钮组件、布局管理器组件、面板组件、列表框和下拉框组件等组件,以及Swing事件处理机制。 下面先从最基础的界面开始。 /** * @author: lishuai * @...

金铭鼎IT教育
46分钟前
14
0
flask 之旅

环境 为了正确地跑起来,你的应用需要依赖许多不同的软件。 就算是再怎么否认这一点的人,也无法否认至少需要依赖Flask本身。 你的应用的运行环境,在当你想要让它跑起来时,是至关重要的。 ...

hblt-j
46分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部