day1基础算法

《day1基础算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基础算法策略长沙市第一中学曹利国第一部分递推策略递推的概念与基本思想给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0

2、示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？abc图1递推的应用（一般递推问题）例题1:Hanoi塔问题.Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？

3、abc图1分析设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n>=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。∴hn=2hn-1+1边界条件：h1=1递推的应用（一般递推问题）例2：实数数列一个实

4、数数列共有n项，已知ai=(ai-1-ai+1)/2+d，(1

5、ai和a1与a2的关系式。分析设ai=Pia2+Qid+Ria1，我们来寻求Pi,Qi,Ri的变化规律。∵ai=ai-2-2ai-1+2d∴ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1∴Pi=Pi-2-2Pi-1……②Qi=Qi-2-2Qi-1+2……③Ri=Ri-2-2Ri-1……④显然，P1=0Q1=0R1=1（i=1）P2=1Q2=0R2=0（i=2）将初值P1Q1R1和P2Q2R2代入②③④可以求出PnQnRn

6、∵an=Pna2+Qnd+Rna1∴a2=(an-Qnd+Rna1)/Pn然后根据公式①递推求出am，问题解决。改进算法但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过30时，求出的am就明显偏离正确值。显然，这种算法虽简单但不可靠。为了减少误差，我们可设计如下算法：∵ai=Pia2+Qid+Ria1=Pi-1a3+Qi-1d+Ri-1a2=Pi-2a4+Qi-2d+Ri-2a3……=Pi-2+kak+Qi-2+kd+Ri-2+kak-1∴an=Pn-k+2ak

7、+Qn-k+2d+Rn-k+2ak-1ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2……⑤根据公式⑤，可以顺推a2、a3、…、aM。虽然仍然存在实数误差，但由于Pn-k+2递减，因此最后得出的am要比直接利用公式①精确得多。递推的应用（一般递推问题）例题：贮油点。一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？编

8、程计算及打印建立的贮油点序号，各贮油点