天籁数学——数列篇（1）

       好久没写博客了，这个系列就来聊聊数学，我们知道数学是一种工具，更是一种思想，在我们的日常生活和工作中都有广泛的应用。

       比如算法中有一种叫做“递推思想”，转化到数学上来说就是“数列”，而我们苦逼的coding，复杂度搞死也只能控制在O(N)，但有没有

想过对这种问题可以一针见血，一刀毙命,这就需要用到“数学”上的知识。猴子吃桃 问题就是一个活生生的例子，评论上给出了很好的解决方

案，学习数学就应该能让它解决点实际上的问题，下面来推导一下。

     为了方便，将递推公式写成：

  a_n=2a_n-1+2  ①

已知首项：a₁=1

将①变形得

 a_n+2=2(a_n-1+2)        ②

由②可推导

 a_n-1+2=2(a_n-2+2)    ③

 a_n-2+2=2(a_n-3+2)    ④

   …

 a₃+2=2(a₂+2)          …

 a₂+2=2(a₁+2)          …

然后我们将这N-1项相乘，化简得

a_n+2=2^n-1(a₁+2)  ⑤

又因为 a1=1 则通项公式为

a_n=2^n-1*3-2        ⑥

根据”递推公式“我们求出了”通项公式“，现在我们可以秒杀任何一天的桃子数量，现在又来问题了，如何求出前N天的桃子总和，在

数列中对应的就是求前n项和的问题，在得知a_n的情况下，求S_n也是秒杀效果。

⑥式是典型的{na_n+b_n}模型，针对这个模型，我们拆分成{na_n}+{b_n}，然后分别计算它们的前n项和，最后合并。

  3*2^n-1 的前n项和为：   S_n=3*2⁰+3*2¹+3*2²+3*2³+…+ 3*2^n-1         ⑦

变形⑦可知                  2S_n=3*2¹+3*2²+3*2³+…+3*2ⁿ                  ⑧

⑦-⑧得（错位相减）

                                 -S_n=3*2⁰-3*2ⁿ

                         =>    S_n=3*2ⁿ-3                                            

 2的前n项和为： =>    Tn=2n

综合两部分结果可知：S_m=3*2^m-3-2m。

最后我们推导出了 猴子吃桃 问题的前n项和，当你苦逼coding的时候，人家早已推导出了，而且复杂度宇宙第一…

 

上面的场景只是想让大家知道数列对我们来说非常重要，后面我会拿算法上的题目用数学来KO，让你知道不懂数学简直就弱爆了，

作为数列专题篇，基础知识必不可少，同样我也可以巩固和复习,嘿嘿。

 

在数列中：通项公式，递推公式，前n项和始终贯穿于数列学习的始终，首篇要了解下面几点：

①：  能够目测简单数列的通项公式。

        比如：1,4,9,16,….. 

               1,0,1,0….

②：  能够根据递推公式求数列的通项公式，比如（猴子吃桃问题）

③：  能够根据数列的前n项和求数列的通项公式。

         an=    s1         (n=1)

                   s_n-s_n-1 (n>=2)

④： 能够求数列的前n项的和S_n

       常用方法：倒序相加，错位相减， 分项相消法（有技巧），倍数法。

⑤： 能够理解{a_n+b_n},{a_nb_n}模型的前N项求和问题。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net