import matplotlib.pyplot as plt
import numpy as np
x1 = np.linspace(-32, 32, 256)
fx = 2 * x1 # 函數(shù)定義
y1 = 0 * x1 # x軸
# f(x) = f(xi) + f'(xi)(x - xi) 其實(shí)f'為導(dǎo)函數(shù)
f2 = (x1 * x1)-16
xi = 7.8 #第一次迭代隨機(jī)7.8位置
t1 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
xi=4.9 #第二次迭代為前一次切線與x軸交點(diǎn)
t2 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
xi=4.1 #第三次迭代為第二次切線與x軸交點(diǎn)
t3 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
xi=4 #第四次迭代為第三次切線與x軸承交點(diǎn)
t4 = ((xi * xi) - 16) + 2 * xi * (x1 - xi)
plt.figure()
plt.title('y=pow(x,2)')
plt.xlabel('x')
x_ticks = np.arange(-16, 16, 2)
x_label_ticks = [('{}'.format(x)) for x in x_ticks]
plt.xticks(x_ticks, x_label_ticks)
y_ticks = np.arange(-16, 16, 2)
y_label_ticks = [('{}'.format(y)) for y in y_ticks]
plt.yticks(y_ticks, y_label_ticks)
plt.ylabel('y')
plt.plot(x1, fx, label="line f'(x)")
plt.plot(x1, t1, label="line 7.8")
plt.plot(x1, t2, label="line 4.9")
plt.plot(x1, t3, label="line 4.1")
plt.plot(x1, t4, label="line 4.0")
plt.plot(x1, y1, label="y=0")
plt.plot(x1, f2, label="f(x)")
plt.grid(True)
plt.legend(loc="upper left")
plt.axis([-16, 16, -16, 16])
plt.show()
image.png
https://leetcode-cn.com/problems/sqrtx/submissions/
二分查找實(shí)現(xiàn)大于平方根的最小值
public int mySqrt(int x) {
//為提高性能特殊判斷 x/2
if(x==1){
return 1;
}
int l = 0, r = x/2,mid=-1;
//int 相乖可能溢出
long sqrt=0;
while (l <= r) {
//mid 計(jì)算邏輯一致
mid = l + (r - l) / 2;
sqrt=(long)mid*mid;
if(sqrt==x){
//如果找到直接返回
return mid;
}
if (sqrt < x) {
//這里是mid -1
l = mid + 1;
} else {
r = mid - 1;
}
}
//取比當(dāng)前值小的最大平方根
return sqrt<x?mid:mid-1;
}
牛頓迭代法
- 原函數(shù)為f(x)=pow(x,2)
- 導(dǎo)函數(shù)為f'(x)=2x
- 在原函數(shù)隨機(jī)采點(diǎn)(x0,y0) ，在該點(diǎn)求導(dǎo)炕横，即過該點(diǎn)斜率，并導(dǎo)出該點(diǎn)的切線方程
- 已知切線為一條直線，根據(jù)切線定義與原函數(shù)曲線有且只有一個(gè)交點(diǎn)椿肩，即（x0,y0), 由導(dǎo)數(shù)定義可知，過該點(diǎn)的切線斜率為導(dǎo)數(shù)
5.在直接線任取一點(diǎn)（x,y) 玩讳，由(4)導(dǎo)出切線方程為
6.求出切線方程與x軸交點(diǎn)输枯，即y=0時(shí)
- 求出切線與x軸交點(diǎn)后，代入原函數(shù)求y 生成新的(x0,y0),過該點(diǎn)求新的切線方程券坞，反復(fù)迭代直至收斂鬓催，即
class Solution {
public int mySqrt(int n) {
if(n==0){
return 0;
}
double x0 = n / 2F;
double x;
while (true) {
x = x0;
//x0= (x0*x0+n)/(2*x0) //注意 (x0*x0+n)/2*x0 一定要加()
x0 = 0.5 * (x0 + n / x0);
//x0 = -(x0 * x0 - n) / (2 * x0) + x0;
if (x - x0 <1e-7) {
break;
}
}
return (int)x0;
}
}
