新普金娱乐网址


天籁数学——数列篇(2)

网上公开源码的一些链接(地理持续革新)

数学ACM败北之路

  • 二月 03, 2019
  • 数学
  • 没有评论

   
校赛打完,已过7月,该是准备背起行囊,踏上考研之路了,自然,得先阔别一下ACM了,想起这几年ACM路,感慨颇多,不得不一诉心肠,与我们享用一下本身的ACM历程,假诺有人能从此文取得一些利益,那我就很安心了。

 

   
倘诺说作为一个做了快两年ACM的一个ACMer来说,我并不是成功的,至少在大家高校不是,或者说,是败北的,我说的挫败并不是突显在尚未得出很好的实绩,而是反映在友好前进的暂缓上。升高的放缓是能够通过rating图看出来的,现在看着友好的rating图,往往能回顾到当初一步一步走过来的惨淡与喜欢。对,ACM是劳动的,但偶尔欢愉的,我想半数以上ACMer都是尊敬上了AC之后的快感之后才逐步的欣赏上ACM的,没有人自发喜欢去做算法题,只要你喜欢,你投入,你就足以获取得到,提高的快感也是令人欢悦的当你发现自己的品位在一步一步地增强后,你会愈发自信,越来越喜欢上这项竞技。可是,很多事都是顺应马太效应的,强者愈强,弱者愈弱,ACM好像也切合这么些规律。

      
这一篇说下第三种特性数列,等比数列,同样我们也应该驾驭它的”基本属性”,“扩展性质”和“判定方法”。

   
我是在大一的时候才晓得ACM的,当时还不让带电脑,同学带了计算机,然后猛地有一天推荐自己上OJ,我当时都不知道OJ是甚,后来在机房上了一晃才了解,原来是做题的网站,然后我凭借刚学的C语言写了几道水题,兴趣一下来了,此后,我平时去机房做题,因为在机房带的时光总是短暂的,所以自己仍旧把题记下来,或者是打印下来,在纸上写出代码,再抽时间去机房敲到电脑上运行,再交题,有一部分对了,有一对会错,于是还得改,又拿回去改。就那样,一个本子很快就写完了。于是,就这么,我爱上了编程,爱上了ACM。

一:基本特性

   
到大一下学期,傍了一个大三的学长,打校赛,基本是他单挑,不仅进了决赛,还拿了三等奖,我和本身一个好对象及时着实只是端茶倒水读读题而已。当时有一种想强大自己的私欲,于是从头读书很多算法,固然很多都学得不是很懂,毕竟基础不够,然后就到了暑假集训,跌跌撞撞进了暑假集训,但是仍旧很弱,于是各类排尾数光荣的被刷了。后来就打道回府去了,本来可以呆在母校继续接着练习的,可是觉得仍然跟集训队的人融不到共同,没什么共同话题,并且不太喜欢里面的空气和条件。回家也没闲着,每一天社团大家(群里面的)刷水题,开首群里有一个比较厉害的人,也跟我一块儿刷题,刷了几乎半个多月的水题,还学了下数论,不过觉得升高照旧不大,唯一的上扬就是手速进步了。当时我有一个童真的想法:当时的档次只好出CF的A,B两题的,于是我去练手速,争取火速过掉A,B两题,,现在认为是多么的可笑。至今可以在hust
vj上来看自身放过的手速场。。

     1:通项公式:         an=a1qn-1

   
然后开学后自然打算废弃了的,去搞了弹指间工程地方的事物,可是下八个月的一场趣味赛自己做的还不易,又把瘾给勾了起来,到了13年1八月份,我才真的初步系统地学习算法,要说自己的ACM之路从此间开始的都能说得过去,我的博客也是在那段岁月开展的,当时只想开个博客来记录自己的算经济学习心得,没悟出今时前日,此博客已经成了如此形容,世事弄人。

     2:  前n项和公式:   Sn=
a1(1-qn)/(1-q)

   
14年好不简单进步相比较大的一年,这一年学了无数算法,水平也初阶发育,顺利的进到暑假集训,然后幸运的得到了区域赛名额,为啥我说幸运,那是有缘由的,我在队里承担数据结构和模拟等码农类的题,什么数学啊,DP啊,图论啊,都玩不动,图论还好点,搜索也还行,结果最后一场互连网赛,我那些数学若菜,居然推出去正确的公式,然后写了一发,挂了一发,优化再交,过了,凭借那题,大家解放了,本来是名次最后的,眼看就要没戏了。就如此糊里糊涂地进去到了区域赛准备阶段。既然上天如此布置,那么自有她的道理,我们后边只能加紧训练了,到1月份,参预区域赛,由于最终一题脑子混乱,居然没看出来一道几何,本来版都带了,于是遗憾拿铜,事实讲明,出来混,总是要还的。然则好歹是拿过奖了。

二: 判定方法

   
区域赛完之后,就从头松懈了,然后一度没有做过题,最后寒假集训个人赛的时候是因为DP真是没入门,导致各样被旁人踩,种种名次末尾,当时早就绝望,回家后的集训也是,各样被人踩,在家里看了很久的DP,题做了几许,不是许多,所以仍旧没怎么控制。最后赶到该校,就准备校赛了,渐渐的,因为自己保研希望有点小,仍旧拔取去考研了,于是比赛,题都没如何做了,最终校赛战绩也不是很好,就那样,我大多停止了自家的ACM之旅。

    1:  an+1/an=q (q是常数)          =>  
 {an}是等比数列。

   
纵观我的整整ACM历程,我觉得自己败北的因素至关主要在偏下地点:

    2:an=cqn                             =>  
 {an}是等比数列。

1.数学基础太懦弱

    3:  an+12=an*an+2               
=>    {an}是等比数列。

   
初高中以来数学就是很相似的那种,不太会用数学来分析难点,高数更是学的一坨屎。其实,个人感觉那么些竞赛拼到底拼的要么数学,数学没那么好的话,智商高也行,然则半数以上人的智力应该都大约吧,所以说,如若您觉得温馨智商不是很超级的话,那么依然把数学学好呢,不管您搞不搞ACM,只要您是搞工程技术方面的,数学是最基本的技巧了。为啥数学那么重大?举个例子,一个贪婪,不用数学分析的话也许就靠灵感,感觉怎么贪对就怎么贪,贪错了大不断再来,不过只要您用数学的文化推一下,你就会连忙地得到一个科学的贪婪方法,既不浪费时间,又能保障正确率,为什么高兴还不去做呢。

 

2.平昔不与人多沟通,走的弯路太多

三:扩大性质   

   
那地点是一个相比较大的因由,开头的时候完全想着刷水题就是一个事例,对待一个可能不那么简单明白的算法,没有拿下的决定,想着那么些难,先学其它一个啊。算艺术学习也仅限于通晓而已,没有可以很好的运用,满意于刷一些模板题就够了,不言而喻就是一句话,中上品的题做得太少,思维操练不够,代码能力训练不够。其实溯其向来,依旧一个不肯直面困难,不自信的标题。

     1:    an=am*qn-m;

3.浮躁

     2:   若m+n=p+q 则
aman=apaq;

   
另一方面就是浮躁了,学东西总是浮在上头,浮沙怎可筑高台。任何一个技能或课程,都像一个金字塔,塔基越广,金字塔尖才能堆得越高,所以,基础才是王道。

     3:  
若{an}是等比数列,若每隔k项取出一项,那么取得的新数列仍是等比数列。

 

                                     比如: k=3时
a1,a4,a7。

   
就算本人的ACM之路败北了,不过我依然不后悔自己做了那件事,不后悔我选用了那般一条路,现在思考,玩ACM的小日子如故是心情舒畅的。况且整个经历给了本人更加多的构思,思考怎么学习,思考怎么工作,思考如何是好人。

     4: 若{an}是等比数列,则arar+1,
ar+2ar+3,
ar+4ar+5照旧成等比数列。

   
假使您是一个正值玩ACM的ACMer,希望本文可以协理您。倘诺您不是,并且有您协调的想法,欢迎一起沟通。^_^

                                     比如:r=1时  则数列
a1a2,  a3a4,
 a5a6成等比数列。

         
                                                                       
                                                                       
                                              2015.3.22

     5:  若{an}是等比数列,则ar+ar+1,  
ar+s+ar+s+1,   ar+2s+ar+2s+1
仍成等比数列。

                                     比如:r=1,s=10 则数列
a1+a2, a11+a12,
a21+a22成等比数列。

     6:
 若{an}是等比数列,Sn是前n项和,则Sk,S2k-Sk,S3k-S2k仍成等比数列,公比为qk

 

四:二种模型难点

  
 1: 大家知道an/an-1=q(常数)时就觉得{an}是等比数列,当q=bn时该怎么处理,其实模型为an/an-1=bn

          证明:  
 an/a1=(an/an-1)*(an-1/an-2)*(an-2/an-3)….*(a2/a1)

                =>  
an/a1=bn*bn-1*bn-2……b1

                =>  
an=a1*(b1b2b3…bn)

               则:      
 数学 1  

    2: 当数列的递推模型为an=b1an-1+b2an-2,可以看看大家前些天要切磋的是an,
 an-1,  an-2时期的递归关系。

        那种模型能够刹那间秒杀“斐波那契数列难题”。

       求解进程如下:

       ①:
 将an,an-1,an-2替换成x2,x,1

              则得 x2=b1x+b2,该方程也就是{an}的二阶特征方程,然后解出特征根x1,x2

       ②: 数学 2

            
 然后将a1,a2代入an后得到一组二元五次方程,求出c1,c2,最终取得an的通项公式。

 

五:多少个小实际应用 

     1: 斐波那契难点 

          
具体细节就隐瞒了,大家一向看它的递归公式,当a1=1,a2=1,
an=an-1+an-2

解答: 我们用特征方程

        
首先将an,an-1,an-2替换成x2,x,1,则得到{an}
的一个二阶特征方程为:

         x2=x+1   ①

         由①得(求根公式)

                        x1=(1-√5)/2  

                        x2=(1+√5)/2

        因为x1!=x2,则

                      
an=c1[(1-√5)/2]n+c2[(1+√5)/2]n   ②

         又因为a1=a2=1,则

                      
c1[(1-√5)/2]+c2[(1+√5)/2]=1        ③

                    
  c1[(1-√5)/2]2+c2[(1+√5)/2]2=1
    ④

         求解方程得

                     c1=-(√5/5)

                     c2=(√5/5)

         将c1,c2代入②式可得

      
an= (-(√5/5)[(1-√5)/2])n+(√5/5)*[(1+√5)/2]n

好了,大家知晓通项公式了,想怎么秒杀就怎么秒杀了。

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图