本文实例讲述了JavaScript迭代、迭代、穷举、递归等常用算法。分享给大家供大家参考,具体如下:
累加和累积
累加:将一系列的数据加到一个变量里面。最后的得到累加的结果
比如:将1到100的数求累加和
小球从高处落下,每次返回到原来一半,求第十次小球落地时小球走过的路程
累积:将一系列的数据乘积到一个变量里面,得到累积的结果。
常见的就是n的阶乘
var n=100; var result= 1; for(var i=1;i<=n;i++){ result *=i; }
一般形式:
累加:V +=e;
累积:v*=e;
V代表累加和累积,e代表累加/累积项
算法要点:
(1)初始化
初始化v和e
累加:v = 0;
累积:v = 1;
e的初始化,如果累加/积项比较复杂,可能会分解为几个子项分别初始化,比如计算圆周率的问题,累计项分解为符号、分子和分母三部分。
(2)循环的控制条件
一种是固定的次数,比如计算弹跳距离的问题,计算数列前20项之和的问题,
次数不固定,而是要满足某个条件:计算圆周率问题要求最后一项的绝对值,要小于10-6。
(3)确定累加/积项的变化
比如数列的前20项之和,是将当前的分子分母之和作为下一次的分母,当前的分母作为分子。
再比如求圆周率问题,是将符号取反、分母加2,然后的出下一项。
迭代
迭代法也就是辗转法
规律:就是可以不断地用旧的值得到新的值,直到我们想要的得到的结果。
遇到了迭代的问题怎么解决
1. 找到迭代的变量(旧的值)
2. 确定迭代的关系
3. 知道想要的结果是什么(结束循环的条件)
(1)就是知道最终结果
(2)循环的次数
递推
找到数学规律:通过公式计算到下一项的值,一直到我们要的结果为止
例如:兔子产子:通过前俩项得到下一项
递推分为顺推和逆推。
穷举
遇到一个问题,找不到更好的解决办法,(找不到数学公式或者规律)时,使用“最笨”的办法,利用计算机计算速度快的特点,将所有可能性全部列出来
并将我们想要得到的结果记录下来
穷举方法的特点:是算法简单,相应的程序也简单,但是计算量往往很大。但是计算机的优势就是运算速度快,所以此算法可以扬长避短,往往可以取得不错的效果。
案例:有一个三位数,个位数字比百位数字大,而百位数字又比十位数字大,并且各位数字之和等于各位数字相乘之积,求此三位数
递归
所谓递归,就是在函数内部又去调用自己。
例如,求阶乘问题,在fact函数内部又去调用fact函数了
递归算法如果按照常规思路去理解是非常复杂的,函数调用一层一层嵌套调用,然后又一层一层返回,不妨换个思路去理解递归。
递归实际上就是将规模为n的问题降价为n-1的问题进行求解。也就是去找n和n-1之间的关系。