数据算法 二叉树排序 email bootstrap后台模版 ddos压力测试 python程序界面 etl数据 后台管理网站模板 python基础语法 python链接mysql数据库 java实例 java新特性 shell编程学习 crazytalk 动态加载js 网络工程师教程 笔记本测试软件 联发科mt6750 管理文件 如何用ai设计字体 编程之家 逗号的作用 网络电子书 目标聚光灯 勇敢者的游戏3 Mapper flushdns 黑域怎么用 财务报表软件免费版 只狼钟 剪影的意思 移动硬盘检测工具 黑市商人在哪 vpstudio lol皮肤修改器 苹果手机怎么拒接电话 苹果商店怎么换地区 ps名片制作教程 苹果视频剪辑 linux系统怎么用
当前位置: 首页 > 学习教程  > 编程语言

184-求x的平方根(两种实现方法)

2021/2/13 20:16:55 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目如下: 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.828…

题目如下:
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去

解题方法1

使用朴素的二分解法,即可解决问题

#include<stdio.h>
int mySqrt(int x)
{
	if (x < 2)
	{
		return x;
	}
	int left = 1;      
	int right = x / 2; 
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (x / mid > mid)
		{
			left = mid + 1;
		}
		else if (x / mid < mid)
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
	}
	return right;
}

int main()
{
	printf("%d\n",mySqrt(8));
	printf("%d\n",mySqrt(4));
	printf("%d\n",mySqrt(16));

	return 0;
}

运行截图如下:
在这里插入图片描述

解题方法2

牛顿迭代法(Newton’s method)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

产生背景:
多数方程不存在求根公式,因此求精确根非常困难,甚至不可解,从而寻找方程的近似根就显得特别重要。方法使用函数 的泰勒级数的前面几项来寻找方程 的根。牛顿迭代法是求方程根的重要方法之一,其最大优点是在方程 的单根附近具有平方收敛,而且该法还可以用来求方程的重根、复根,此时线性收敛,但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。

在这里插入图片描述
利用迭代算法解决问题,需要做好以下三个方面的工作:
一、确定迭代变量
在可以用迭代算法解决的问题中,至少存在一个可直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。
二、建立迭代关系式
所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制
在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析得出可用来结束迭代过程的条件。

#include<stdio.h>

int s;//定义全局变量s
double sqrts(double x)
{
	double res = (x + s / x) / 2;
	if (res == x)
	{
		return x;
	}
	else
	{
		return sqrts(res);
	}
}

int mySqrt(int x)
{
	s = x;
	if (x == 0)
		return 0;
	return ((int)(sqrts(x)));
}

int main()
{
	printf("%d\n",mySqrt(8));
	printf("%d\n",mySqrt(4));
	printf("%d\n",mySqrt(16));

	return 0;
}

运行截图如下:
在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_700434.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?