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

冷不防 2022-10-29 11:25 160阅读 0赞

**题目如下：**  
实现 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;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 解题方法2 ##

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

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

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

#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;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/9eb03c6ca1bf48e89d94e12767ebda2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/517a3c180d9543d2b17afe467f046bd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/4fec14559945485a908cc266e1879bc2.png