题解 | #求解立方根#
求解立方根
https://www.nowcoder.com/practice/caf35ae421194a1090c22fe223357dca
题目要求浮点数,对于浮点数不能直接用===判断相等,可以给定一个阈值,当差值小于该阈值时便当作相等。
方法一: 牛顿迭代法求立方根
公式为:
为新的猜测之,
为当前猜测值,
是要计算的数
我们可以给定一个阈值,两次猜测的差值小于该阈值是便表明当前猜测的值已经足够接近答案。
推导过程
首先牛顿迭代法的基本思想是从一个猜测的初始值开始不断更新迭代该值,直到找到一个足够接近真实立方根的值。那么如何确保猜测的值能够逼近真实的立方根呢?可以利用函数和它的切线来逼近。可以动手把该过程画出来便于理解。
假设我们要求解的方程为,并且有一个近似解
,那么该点处的切线方程为:
令 求解
得到下一个更接近真实根的近似解
而本题中要求求解的立方根 需要求解方程:
令
对其求导得到
带入上述公式中得到:
代码如下(JavaScript Node)
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
function getCubeRoot(num) {
if(num === 0.0) return 0.0
let x = num
let lastX = 0
// 给一个阈值
while(Math.abs(x - lastX) > 0.0001) {
lastX = x
x = 1 / 3 * ((num)/ (x * x) + 2 * x )
}
return x.toFixed(1)
}
void async function () {
// Write your code here
while(line = await readline()){
let num = parseFloat(line)
console.log(getCubeRoot(num))
}
}()
方法二: 二分查找
使用二分查找时应注意两点:
- 对于0到1之间的值 应当在num与1之间进行二分,对于大于1 的值需要在1到num之间进行二分
- 对于负数第一条应该相反,可以直接取绝对值,在输出前取负
function getCubeRootBinarySearch(num) {
let neg =false
if(num < 0) neg = true
num = Math.abs(num)
let left, right
if(num < 1) {
left = num
right = 1
} else {
left = 1
right = num
}
while(left <= right) {
let mid = (right - left) / 2 + left
let cube = mid ** 3
let diff = Math.abs(cube - num)
if(diff < 0.00001) {
if(neg) mid = -mid
return Number(mid.toFixed(1))
}
if(cube < num) {
left = mid
} else {
right = mid
}
}
if(neg) left = -left
return Number(left.toFixed(1))
}