x 的平方根

工程优化 牛顿迭代法

牛顿迭代法是用来求一个函数的极小值点

即一阶导等于0

将f(x)在x0处泰勒展开

$$ f(x)=f(x0)+f'(x0)(x-x0)+\frac{1}{2} f''(x0)(x-x0)^2+o(x-x0) $$

$$ f'(x) = f'(x0)+f''(x0)(x-x0) $$

解 $$ f'(x)=0 $$

即 $$ f'(x) = f'(x0)+f''(x0)(x-x0)=0 $$

$$ x=x0-\frac{f'(x0)}{f''(x0)} $$

这样不断迭代知道你想要的精度即可

题目：

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

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

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

示例 1：

输入：x = 4 输出：2 示例 2：

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

提示：

0 <= x <= 2^31 - 1

思路：

可知题目是求下面的式子：

$$ x^2=C $$

即 $$ x^2-c=0 $$

牛顿迭代法是让一阶导等于0，那么我们不妨认为上式就是原目标函数的一阶导，那么原函数是

$$ f(x)=\frac{1}{3}x^3-cx+d $$

d 为常数

可知

$$ f'(x)=x^2-C $$

$$ f''(x)=2x $$

可知求解的公式是

$$ x=x0-\frac{f'(x0)}{f''(x0)}=x0-\frac{x^2-C}{2x} $$

我们为了要求那个整数，那么我们终止条件就是接近目标位置的距离小于1即可

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<map>
using namespace std;

class Solution {
public:
    int mySqrt(int x) {
        double ans = 1, t=1;
        while (abs(t) > 0.1)
        {
            t = (ans * ans - x) / (2 * ans);
            ans = ans - t;
        }
        return int(ans);
    }
};

int main()
{
    //freopen("D:/c++/dev-data/in.txt", "r", stdin);
    /*int nums[] = { 1,0,1 };
    vector<int> v_nums;
    for (int i = 0; i != 3; i++)v_nums.push_back(nums[i]);*/
    int x = 4;
    Solution s;
    int ans=s.mySqrt(x);
    cout << ans << endl;
    return 0;
}