javascript简易计算器三个数连加(二分查找算法求任何方程的根)

javascript简易计算器三个数连加(二分查找算法求任何方程的根)(1)

市面上,二分查找算法的实现方法有很多。其共同的特点是,看起来似乎很容易,但是面试的时候,即使是同样的题目却很难复现,更不要说遇到变通的题目。

本文将会帮助你完全掌握binary-search.

1.回到数学的问题的起点

设有连续函数 f(x), 求 f(x) = 0 在区间(a, b) 上的根。我们假设在区间内的解是存在的,则必然有下面的关系:

f(a) < 0 < f(b)

函数 f 在区间a,b内必然至少有一个点为0,由此分情况讨论:

  1. f(x) > 0,则 f(x) = 0 的情况在 a 与 x 之间
  2. f(x) < 0,则 f(x) = 0 的情况在 x 与 b 之间。

如此循环而不断缩小查找区间,最终达到最小区间,跳出运行。

算法复杂度为:Θ(log(L/T)), 其中L(Length)为区间长度, T(tolerance) 为容差。

2.关于抽象思考

在撰写具体的实现之前,荡开一笔,探讨你的大脑中如何思考 f(x) > 0 这个表达式。

是读作 “f(x) 大于 0” 或者 “f(x) greater than 0" 吗?

比较符号 ">” 是最原始的运算符号,当我们用它思考的时候,大脑就不由自主的陷入到繁琐的细节之中,因此导致我们常常遇到的情况。明明一个算法很简单,比如“冒泡排序”,”插入排序“,一看就懂,但是真要动手写一个时候,往往要耗费半个多小时。

其症结只在于,我们的思考纠缠到了具体的实现上,计算机能够轻松的运行 < > 等运算符号,但是我们用以思考的语言没有将其向更高维度抽象出来。

再进一步思考,“f(x) 大于 0” 对大脑而言究竟是什么意思? 对,很简单,大于0 是正值。当我们用 “f(x)是正值" 取代”f(x)大于0"之时,大脑与直觉瞬间被激活。因为思考“正值在右边,负值在左边”,比思考“大于0的数就在数轴的右边,而小于0的数字就在数轴数轴的左边”更加符合直觉,更加不需要思考。

由此,定义出positive和negetive两个函数:

function positive(x) { return x > 0; } function negative(x) { return x < 0; }

虽然很简单,却能帮助大脑从案牍劳形的低级思考中解放出来。

3.算法实现

闲话少叙,直接上算法实现:

function search(f, neg_point, pos_point) { let midpoint = average(neg_point, pos_point); if (close_enough(neg_point, pos_point)) { return midpoint; } else { let test_value = f(midpoint); if (positive(test_value)) { return search(f, neg_point, midpoint); } else if (negative(test_value)) { return search(f, midpoint, pos_point); } else { return midpoint; } } }

第一行中,将average单独拎出来,遵循了与定义positive和negetive相同的逻辑,即在思考过程中不纠缠于初级的表达语言。

function average(a, b) { return (x y) / 2; }

函数close_enough定义tolerance容差。

function close_enough(x, y) { return abs(x - y) < 0.001; }

定义绝对值:

function abs(x) { return x >= 0 ? x : -x; }

4.测试与验证

先测试求平方根sqrt,比如求数字 7 的平方根:

console.log(search(x => x * x -7, 0, 7)); //: 2.64593505859375 //或者求立方根: console.log(search(x => x * x * x - 57, 0, 57)); : 3.8482131958007812 //或者求三角函数的值: console.log(search(x => Math.sin(x) - 1, 0, 1)

或者负责的多元求根公式:

x^3 - 3x^2 - 101 = 0

console.log(search(x => x**3 -3*x**2 - 101, 0, 101) //求得: 5.900630950927734

最后三角函数的求值:

console.log(search(x => Math.sin(x) - 1, 0, Math.PI/2))

求得:

1.570412831597925

验证:

> Math.asin(1) 1.5707963267948966

更进一步的抽象

以上定义的函数search以及验证:

function search(f, neg_point, pos_point)

的过程中,有一步必需的人工操作,就是验证 f(a) 与 f(b) 这两个值是正值还是负值,然后才能带入到方程中的正确位置。

由此,我们将其进一步抽象:

function binary_search(f, a, b) { let a_value = f(a); let b_value = f(b); return negative(a_value) && positive(b_value) ? search(f, a, b) : negative(b_value) && positive(a_value) ? search(f, b, a) : error("values are not of opposite sign"); }

进一步抽象的方案就能求任何方程的解。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页