递推思想

递推思想（精选10篇）

递推思想 篇1

世界是千变万化的, 各种事物都在相互转化, 好的可以转化为坏的;多的可以转化为少的, 丑陋的可以转化为漂亮的, 复杂的可以转化为简单的……

递推数列是数列的重要内容, 是数学高考和竞赛的亮点, 纵观近几年各地高考数学试题, “递推数列”几乎为必考题, 且多以“压轴题”的姿态出现.数列中蕴含着丰富的数学思想, 而递推数列反映的是数列的本质特征, 具有很强的逻辑性, 是学习逻辑推理和化归能力的好素材, 也是数学教学中渗透数学思想方法的好载体.

数学中的转化思想在学习过程中应用非常普遍.解决许多问题实际上都是在转化, 将问题由难转易, 由陌生转熟悉, 从而使问题得到解决.

例1已知数列{an}满足an=2an-1+3且a1=1, 求数列{an}的通项公式.

解方法1 (递推法) :

方法2 (构造法) :设an+1+μ=2 an (+μ) , 即μ=3, ∴数列an{+3}是以a1+3=4为首项、2为公比的等比数列, 则an+3=4·2n-1=2n+1, 即an=2n+1-3.

例1不论是递推法还是构造法, 都是把递推关系转化为等比数列问题, 才能使问题顺利解决.

例2已知a1=1, an=an-1+n, 求an.

解方法1 (递推法) :

方法2 (累加法) :an-an-1=n, 依次类推有:an-1-an-2=n-1、an-2-an-3=n-2、…、a2-a1=2, 将各式叠加并整理得

例1不论是递推法还是累加法, 只有把递推关系转化为等差数列问题, 题目的问题就不难了.

例3已知a1=1, an=-an-1+2n-1, 求an.

∴是以为首项, 为公比的等比数列, 即

例3是通过待定系数法把递推关系转化为等比数列问题, 问题才会迎刃而解.

例4已知a1=10, an+1=an2, 求an.

解对递推式an+1=an2左右两边分别取对数得lgan+1=2lgan, 令lgan=bn, 则bn+1=2bn, 即数列{bn}是以b1=lg10=1为首项, 2为公比的等比数列, 即bn=2n-1, 因而得an=10bn=102 n-1.

例4对递推式两边取对数, 这样一来, 问题就可以转化成等比数列进行求解了.

例5已知a1=4, , 求an.

解对递推式左右两边取倒数得

∴数列{bn-2}是以b1-2=2为首项、2为公比的等比数列,

则bn-2=2·2n-1=2n,

即bn=2n+2, ∴

例4对递推式两边取倒数, 通过待定系数法, 问题就可以转化成等比数列进行求解了.

人为的转化总是朝着进步的方向, 递推数列的应用问题求解, 主要是运用转化思想把问题的解决方向更加明确, 转化为两类基本数列 (等差数列、等比数列) 的问题来求解, 最后取得成功, 其中的喜悦感油然而生.

递推数列初探 篇2

1.累加法

例1已知数列{an},a1=1，n∈N*，an=an-1+1n2-n（n≥2，n∈N*），求通项公式an．

解：∵ an-an-1=1n2-n=1n(n-1)=1n-1-1n（n≥2）．

∴ an=a1+(a2-a1)+(a3-a2)+…+(an-an-1)

=1+1-12+12-13+…+1n-1-1n=2-1n．

评注：形如an=an-1+f(n)的递推数列，其中数列{f(n)}可求和，则可通过恒等式an=a1+(a2-a1)+(a2-a2)+…+(an-an-1)累加求通项．

2. 累乘法

例2已知数列{an}，a1=1，an＞0，(n+1)a2n-na2n-1+anan-1=0（n≥2，n∈N*），求数列an通项公式．解：∵ na2n-(n-1)a2n-1+anan-1=0，∴ ［nan-(n-1)an-1］(an+an-1)=0．

∵ an＞0，∴ an+an-1＞0，∴ nan-(n-1)an-1=0，∴ anan-1=n-1n．

∴ an=a1•a2a1•a3a2…anan-1=1•12•23…n-1n=1n．

评注：形如anan-1=f(n)的递推数列，其中数列{f(n)}可求积，则可通过恒等式an=a1•a2a1•a3a2…anan-1累乘求通项．

3.构造法

① 待定系数法

例3已知数列{an}，a1=1，an=3an-1+2（n≥2，n∈N*），求数列{an}通项公式．

解：∵ an=3an-1+2，令an+x=3(an+x)，

∴ x=1，∴ an+1=3(an+1)，∴ {an+1}为等比数列，首项为a1+1=2，公比q=3，∴ an+1=2•3n-1，∴ an=2•3n-1-1．

评注：形如an=qan-1+d（q，d为常数，q≠0，q≠1），可通过待定系数法凑配成an+dq-1=qan+dq-1，构造等比数列an+dq-1求通项，特别的，当q=1时{an}为等差数列．

② 取倒数法

例4已知f(x)=2x2x+1，数列an=f(an-1)(n≥2，n∈N*)，且a1=f(1)，求数列{an}的通项公式．

解：∵ an=f(an-1)，∴ an=2an-12an-1+1，∴ 1an=2an-1+12an-1，∴ 1an=12an-1+1，令1an+x=121an-1+x，∴ x=-2，∴ 1an-2是等比数列，首项为1a1-2=1f(2)-2=-12，公比q=12，∴ 1an-2=1a1-2•qn-1=-12•12n-1，∴ 1an=-2-n+2，∴ an=2n2n+1-1．

评注：形如an=can-1an-1+d（c,d为常数，c≠d,c≠0,d≠0）的递推数列，可通过取倒数1an=dc•1an-1+1c，再通过待定系数法构造等比数列求通项，特别的，当c=d时数列1an为等差数列．

③ 取对数法

例5已知数列{an}，a1=10，an=10a2n-1，(n≥2，n∈N*)，an＞0求数列{an}的通项公式．

解：∵ an=10a2n-1，∴ lgan=2lgan-1+1，令(lgan+x)=2(lgan-1+x)，∴ x=1，∴ {lgan+1}为等比数列，首项为lga1+1=2，公比q=2，∴ lgan+1=2n，∴ an=102n-1．

评注：形如an=can-1p（c，p为常数，an＞0，c＞0,p＞0，p≠1），两边取对数lgan=plgan-1+lgc，再通过待定系数法构造等比数列求通项，当p=1时，数列{lgan}为等差数列．

④ 换元法

例6已知数列{an}，a1=1，an=2an-1+3n（n≥2，n∈N*），求数列{an}的通项公式．

解：∵ an=2an-1+3n，∴ an3n=2an-13n+1，

∴ an3n=23•an-13n-1+1，令bn=an3n，bn+x=23（bn-1+x），

∴ x=-3，∴ {bn-3}为等比数列，首项为b1-3=-83，公比q=23，∴ bn-3=an3n-3=-83•23n-1=-2n+23n，∴ an=3n+1-2n+2．

评注：形如an=qan-1+dn（q，d为常数，q≠0，d≠0，q≠1，d≠1，d≠q）的递推数列，可变换成andn=qd•an-1dn-1+1，令bn=andn，转化为bn=qdbn-1+1，通过待定系数法求通项．特别的，q=d时，bn为等差数列．

4.数学归纳法

例7已知数列{an}满足a1=1，且4an+1-anan+1+2an=9（n∈N*），求数列{an}的通项公式．

解：∵ a1=1，4an+1-anan+1+2an=9(n∈N*)，∴ a2=73，a3=135，a4=197．

猜想： an=1+6(n-1)2n-1．

下证：当n=1时，猜想成立．当n=k（k∈N*）时，猜想成立，即ak=1+6(k-1)2k-1则当n=k+1时，有ak+1=2-1ak-4=2-16k-52k-1-4=6k+12k+1=1+6［(k+1)-1］2(k+1)-1．

∴ 当n=k+1时也成立．综上可知an=1+6（n-1）2n-1成立．

评注：数学归纳法求通项公式遵循“归纳，猜想，证明”，三步曲．

从数列的递推关系式求出数列通项的过程中，有时需要构造一个全新的数列，有时需要从特殊归纳到一般结论，这实际上是一次思维的整理，和创新的过程．

递推思想在概率中的应用 篇3

常见的递推公式有:an+1=λan+b, an=λan-1+μan-2, 等等.

数列的递推公式在数学的有关问题的解决中有着较广泛的应用, 下面举几例说明递推在概率问题中的应用.

例1:A、B两人拿两颗骰子做抛掷游戏, 规则如下:若掷出的点数之和为3的倍数时, 原掷骰子的人再继续掷;若掷出的点数不是3的倍数时, 就由对方接着掷, 第一次由A开始掷,

(1) 前4次抛掷中, A恰好掷3次的概率为多少?

(2) 若第n次由A掷的概率为Pn, 求Pn.

分析: (1) 中的问题可以用列举的方法:

在抛掷的6×6=36种不同的结果中, 共有12种结果中点数和是3的倍数.

由题可知:A掷的下一次仍由A掷的概率为:12/36=1/3, 在A掷的下一次由B掷的概率为:.

因此, 前4次抛掷中, A恰好掷3次, 共有以下3种情况:AAAB、AABA、ABAA, 而这3种情况发生的概率分别是:

在 (2) 中, 由题可知:P1=1, P2=1/3, 第 (n-1) 次由A、B掷的概率分别是Pn-1、1-Pn-1 (n>2) , 则第n次由A掷的概率是:

于是有递推关系:

在这道题中, 注意到由数列的递推关系得出由n-1到n的递推公式, 从而得出其一般形式.

例2 (第十二届加拿大数学奥林匹克试题) :抛掷一枚硬币, 每次正面出现得1分, 反面出现得2分, 试证:恰好得到n分的概率是.

解:设恰好得到n分的概率是Pn, 则得 (n-1) 分的概率是Pn-1, 则得 (n-2) 分的概率是Pn-2, 得n分的前提是:先得 (n-1) 分, 再掷一次正面, 此时概率是, 或为先得 (n-2) 分, 再掷一次反面, 此时概率是.因这两种情况是互斥的, 故有, 易得P1=1/2, P2=3/4, 所以, 得到递推关系:

例3:设正四面体的四个顶点是A, B, C, D, 各棱长度均为1米, 有一个小虫从点A开始按以下规则前进:在每一顶点处用同样的概率选择通过这个顶点的三条棱之一, 并一直爬到这条棱的尽头, 求它爬了7米后恰好首次位于顶点A的概率.

解:考虑一般情况, 若小虫走过n米之后又回到点A, 则它走了 (n-1) 米后就在B, C, D三点中的一点.小虫走了 (n-1) 米到达点A与没有到达点A是对立事件, 若设Pn表示小虫走过n米之后又回到点A的概率, 则Pn-1表示小虫走过 (n-1) 米之后又回到点A的概率, (1-Pn-1) 表示小虫走过 (n-1) 米之后不回到点A的概率.因为从B, C, D三点到点A是等可能的, 概率都为1/3, 于是有Pn= (1/3) (1-Pn-1) , 因为起始时小虫在点A, 所以P0=1, 故得到递推关系:

由P0=1逐步递推可得:P7=182/792, 所以小虫走过7米之后又回到点A的概率为P7=182/792.

分析: (1) 略.

(2) 由题知:第n次棋子移动到A点, 则第 (n-1) 次棋子在B、C两点, 所以概率为:, 同理可得:.

两式相减得:, 而p1=r1=1/2, 所以pn=rn.

(3) 由上可知:,

又pn-1+qn-1+rn-1=1,

即2pn-1+qn-1=1,

代入得:,

例析递推数列与计数问题 篇4

递推数列是一类广泛而复杂的问题,其特点是逻辑推理性强,求解方法开放、灵活.数列应用问题的特征是内容广泛,对信息收集、语言转换和数据处理能力的要求高.本文介绍递推数列在计数问题中的几个应用,供同学们参考.一、 排列问题 例1 把1元与2元的硬币共n元放成一排,总共有多少种不同的放法?解 设放法总数为xn,则x1=1,x2=2.

把xn种放法分为两类:(1)头一枚是1元的放法数应是xn-1;(2)头一枚是2元的放法应是xn-2.

于是xn=xn-1+xn-2(n=3,4,5,…).

下面用待定系数法求通项xn.

引入参数a,b,设xn-axn-1=b(xn-1-axn-2),也即xn=(a+b)xn-1-abxn-2.

故a+b=1,ab=-1.参数a,b可视为x2-x-1=0的两个根,则a=,b=或a=,b=.

于是xn-xn-1=xn-1-xn-2①,xn-xn-1=xn-1-xn-2②.

由①式知数列xn-xn-1是首项为x2-x1=,公比为q1=的等比数列,所以有xn-xn-1=n-2=n③.

由②式知数列xn-xn-1是首项为x2-x1=,公比为q2=的等比数列,所以有xn-xn-1=n-2=n④.

由③④消去xn-1,即得xn=n+1-n+1.

评析 这是著名的斐波那契数列.本题采用待定系数法化归为等比数列求通项问题.二、 染色问题 例2 把一个圆分成n(n≥2)个扇形,依次记为S1,S2,…,Sn,每一个扇形可用红、黄、蓝三种颜色中的任一种涂色,但要求相邻扇形的颜色互不相同,问一共有多少种涂色方法?解 设分成n个扇形时,涂法的总数为an(n≥2).

当n=2时,S1有3种涂法,S2与S1的颜色不能相同,故对于S1的每一种涂法,S2仅有两种涂法,这样共有a2=3×2=6种涂法;当n>2时,由于S1有3种涂法,S2有两种涂法,接着S3,S4,…,Sn-1,Sn依次有两种涂法,即共有3×2n-1种涂法,但其中Sn与S1的颜色相同时有an-1种涂法,故有an=3×2n-1-an-1(n≥2),两边同时除以2n,得=-•,即-1=--1.

所以数列-1是以首项为-1=,公比为-的等比数列,所以-1=,即an=2n1+=2[2n-1+(-1)n].

故当n>2时,一共有2[2n-1+(-1)n]种涂色方法.

评析 染色问题是中学数学奥赛的热点问题,说不定也将成为数学高考的热点问题.三、 更列问题 例3 五个人排成一列,重新站队时,各人都不站在原来的位置上,那么不同的站队方式共有多少种?解 首先我们把人数推广到n个人,即n个人排成一列,重新站队时,各人都不站在原来的位置上.设满足这样的站队方式有an种,现在我们来通过合理分步,恰当分类找出递推关系:

第一步:第一个人不站在原来的第一个位置,有n-1种站法;

第二步:假设第一个人站在第i(i≠1)个位置,则第i个人的站法可以分为两类:第一类,第i个人恰好站在第一个位置,则余下的n-2个人有an-2种站队方式;第二类,第i个人不站在第一个位置,则就是第i个人不站在第一个位置,第二个人不站在第二个位置,第三个人不站在第三个位置,……,第n个人不站在第n个位置,也即余下的n-1个人排队,所以有an-1种站队方式.

由分步计数原理和分类计数原理,我们便得到了数列{an}的递推关系式:an=(n-1)(an-2+an-1).显然,a1=0,a2=1,再由递推关系有a3=2,a4=9,a5=44,故共有44种.四、 传球问题 例4 甲、乙、丙、丁四人相互传球,第一次甲传给乙、丙、丁中的任一人,第二次由拿球者再传给其他人中任一人,这样共传了四次,求第四次球仍传回到甲的方法种数.解 先把这个题目进行推广:m(m∈N+)个人相互进行n(n∈N+)次传球,由甲先传,第一次甲传给其他m-1个人中的任一人,第二次由拿球者再传给其他人中任一人,这样经过n次传球,最后球仍回到甲手中的传球方法有多少种?(这里m为常数)

设不同的传球方法共有an种,现在我们来通过合理分步,恰当分类找出递推关系:

第一步进行第一次传球:甲传给其他人,有m-1种传球方法;

第二步进行第二次传球:拿球者把球传给其他人,仍有m-1种传球方法;

同理,第三次、第四次……第n-1次传球都有m-1种传球方法,最后进行第n次传球,由于只能传给甲,故只有一次传球方法.故有(m-1)n-1种传球方法,但要注意第n-1次传球不能传给甲,否则就不存在第n次传球,因此要去掉第n-1次传球,球恰好传给甲的传球方法数,这就是由甲先传,经过n-1次传球后球又回到甲手中的传球方法,显然,这里有an-1种传球方法,所以有递推关系:an=(m-1)n-1-an-1,又易得a1=0.

而在本题中,m=4,所以an=3n-1-an-1,所以a2=3-a1=3,a3=32-a2=6,a4=33-a3=21,故第四次球仍传回到甲的方法种数共有21种.

评析 从上面的解答与分析我们可以看到,用递推法解答排列组合问题的关键所在就是得到递推关系式.

1. 欲登上第10级楼梯,如果规定每步只能跨上一级或两级,则不同的走法共有多少种?

2. 用4种不同颜色涂四边形的4个顶点,要求每点染一种颜色,相邻的顶点染不同的颜色,求不同的染色方法种数.

递推思想 篇5

C语言是很多学习程序设计的入门课程, 因为C语言具有语言简洁、数据符号丰富、易于结构化等特点, 便于在实际应用中实现。本文对“穷举”和“递推”算法进行分析, 了解其基本思想, 然后针对不同的算法, 对相关的问题进行细致的论述。在对“穷举”算法的研究中, 先对这一算法在简单问题中的应用进行分析, 其次对其测试标准的转化技巧进行了研究探析, 最后对测试范围进行了分析和论述。在对“递推”算法的研究中, 通过对基本思想的概念理解, 结合顺推和逆推的案例进行了详细的论述。

2“穷举”算法分析

“穷举”算法的基本思想:在既有的范围内, 根据相应的测试标准, 对问题的答案进行逐一验证, 进而求得答案的算法过程, 在这一过程中的循环遍历直至得出答案后终止程序运行[1]。从“穷举”算法的基本思想可以看出, 测试范围和测试标准是代码编写和程序运行的关键点所在。

2.1“穷举”算法在简单实例中的应用

比如求解1-100内17倍数的个数, 当然这是个比较简单的数学题目, 根据已有的数学知识不难得出这一题目答案:1-100内17的倍数有5个;但结合C语言程序, 通过一定的程序语言和“穷举”算法该怎样实现并得出这一数字呢?根据“穷举”算法的思想, 在这一范围内对所有数字进行逐一验证, 最终得出符合条件的数字, 进而得出数量。

而在C语言中, 这也是属于较为简单的题目, 所以相对应的逻辑程序也较为简单, 首先需要设置1-100之间每两个相邻数字之间的差为1, 其次判断条件为17的倍数, 然后设定计数器的初始值为0;经过这一简单逻辑的梳理, 在C语言的编写过程中, 每当程序查找到一个满足条件的数字时, 计数器的数字会自动加1。在以上分析的基础上, 可以得到以下C语言代码程序:

#include<stdio.h>

Viod main ()

{int i, count=0;//程序开始处定义两个整形变量, i为循环变量, 0为计数器初始值;

for (i=1;i<100;i++) //设置for循环, 设定i的初始值为1, 循环的条件为100以内;

{if (i%17==0) Count++;}//设置判定条件, i=17的倍数;当i是17的倍数的时候, 计数器则自动+1;

Printf (“1-100之间是17倍数的数字的个数为:%dn”, count) ;}//输出总数, 符合条件的17的倍数的个数为5。

2.2 分析测试标准转换技巧

对测试标准的转换分析, 本文结合“四叶玫瑰数”进行分析, 由于“四叶玫瑰数”的概念, 可以更加直观形象地体现出测试标准的转换技巧, “四叶玫瑰数”就是四位数的自幂数的名称;例:1634=1*1*1+6*6*6+3*3*3+4*4*4.可以很明显地看出, “四叶玫瑰数”的定义为:数字各位的立方之和等于数字本身。

为了实现C语言程序中的转换, 就“四叶玫瑰数”的例子来说, 将某一四位数的四个数字进行变量的设置, a, b, c, d分别为个十百千在代码中的代表字符, 即可得到一个测试标准的公式:d*1000+c*100+b*10+a*1==d4+c4+b4b+a4。

假如给定条件, 设置测试的范围为1000-9999, 大致逻辑同1-100内17倍数, 相邻数字之间的差为1, 结合得出的4层循环公式, 根据设定的条件, 编写对应的C语言代码, 可得出最终有三个符合条件的数字即:1634, 8208, 9474。

2.3 对“穷举”算法测试范围的把握分析

对于前面两个相对简单的例子, 主要是利用循环遍历的思路进行程序的设定编写, 从而得到所求的答案;但在这一部分所要结合的案例为“鸡兔同笼”, 对测试范围的把握, 以及对循环次数的控制方法的分析。

案例给出条件为:笼子里有鸡兔共48只, 脚的数量为132, 求鸡和兔各自的数量?这样的题目, 若用常规的数学方程思路来考虑, 设出两个方程变量, 列出等式则很容易可以得出答案:鸡30和兔18。但现在利用C语言的模式来考虑的话, 同样可以设置两个变量鸡的数量为i, 兔的数量为j, 那么相对应的测试标准则为: (i==48-j) && (2*i+4*j==132) .

根据实际情况进行分析, 假设132只脚都为鸡, 但总数量为48, 所以得出i<48, 同样的逻辑可以推理出j<33;在这些数据和条件下可以实现代码的编写:

#include<stdio.h>

Viod main ()

{int i, j;//设置鸡和兔数量两个变量;

for (i=1;i<48;i++) //i的循环范围需小于48;

for (j=1;j<48;j++) //j的循环范围需小于33;

{if ( (i==48-j) && (2*i+4*j==132) ) //与数学方程思维类似, 列出变量等式, 满足头48个, 脚132个;

Prntf (“there are%d chicken, there are%d rabbitsn”, i, j) ;}}//最终会显示出运行结果数量分别为30和18.

这一例子只是众多问题中的一个, 是一个有解的问题, 但在实际情况中, 也会有很多问题, 在详细的分析、代码的设计、程序的编写等运行之后并没有结果;针对无解的情况, 在编写代码之初可以将这一问题考虑进去, 在其中设置相应的变量加以标识, 在程序运行过程中, 当遇到这样的情况时, 系统会自动输出相应的提示[2]。

3“递推”算法的研究

3.1“递推”算法的基本思想分析

“递推”算法的基本思想为按照固有的法则, 读一个或多个元素进行推算, 在规定的步骤内, 最终得出所需的元素。基于这一思想, 其中的固有法则通常理解为各元素之间的关系, 从它们的关系中可以体现出数值变化的规律;一个或多个元素则是指递推一开始的取值数字;规定的步骤是指递推的次数;从中可以看出, “递推”算法有三个关键的条件:递推初始值, 递推法则和递推次数。

以“10的阶乘”为例来分析这三个关键条件的重要性, 结合数学知识可得:n!= (n-1) !*n其中 (n>=1) , 通过分析可得递推的初始值为1, 递推法则即为n!= (n-1) !*n, 递推次数则是由n的取值来决定的。以此为基础条件, 将其转换为相应的语言代码, 设置出一个变量来反映1-10之间的变化, 设定f来表示阶乘结果, f的初始值为1。

3.2 顺推和逆推的应用分析

递推算法有两种算法, 分别为顺推和逆推;前者为从既定的条件出发, 根据相应的法则运算出最终的结果, 后者则是从结果出发, 通过一定的法则推算出起始条件。

首先来说顺推法, 结合斐波那契数列可以更加直观形象地对这一方法进行描述;在数学家斐波那契的《算盘书中》有一个与兔子相关的问题:给出的条件为每对兔子每个月可以繁殖出一对小兔子, 新生的每对兔子从第三个月也可以开始繁殖小兔子;假设最初只有一对兔子, 并且兔子不死亡;在这样的一个规律下生成的一个数列公式为:f (1) =1, f (2) =1, f (n) =f (n-1) +f (n-2) (n>=3) ;提出问题在第20个月的时候, 兔子的总对数为多少?

根据给定的条件和需要求得的答案, 代码编写如下:

#include<stdio.h>

Viod main ()

{long int f1=1, f2=1;//设定初始值为1;

Int n;

For (n=1;n<=9;n++) //n为递推的循环次数;

{f1=f1=f2;//f1表示20个月内单月的兔子对数;

f2=f2=f1;}//f2表示20个月内双月的兔子对数;

Printf (“%d”, f2) ;}//通过程序运行最终可得出结果为6765对。

接下来是逆推法的分析, 经典的逆推法应用问题为“猴子吃桃”, 这一问题的内容为:猴子第一天吃掉当前桃子数量的一半, 然后多吃了一个;第二天吃了剩下桃子的一半, 然后再多吃一个, 以此类推;然而在第十天的时候剩下了一个桃子, 问一开始有多少桃子?

这是一个很经典的知道结果数字, 但没有初始数字的题目, 从而也就是最经典的逆推题型;根据各处的条件内容可以进行以下的假设和类推:最后一天为f (n) =1, 然后倒数第二天的为f (n) =f (n-1) /2-16, 整理可得f (n-1) = (f (n) +1) *2, 从这一等式中可以理解为:前一天桃子的数量为当前加一之后的2倍;在现有的条件下可以对其进行C语言程序编写, 运行后可以得出结果为1534个。

4 结语

经过分析可以更加明确地了解两种算法的特点;其中“穷举”算法要具备一定的测试范围和测试标准, 然后进行循环遍历测试出结果;“递推”算法不管是顺推法还是逆推法, 都是要结合实际情况进行分析后, 找出三个关键条件递推初值、法则和递推次数, 然后再按照推算法则, 求得结果[3]。这两种算法在实际的应用中受控于循环, “穷举”算法的循环遍历和“递推”算法的递推算法被反复执行;在语言程序的编写设计过程中, 注意对结构的循环设置和对执行次数的循环控制, 优化程序运行过程, 提升运算效率。

参考文献

[1]胡枫.《C语言程序设计》的案例式教学的设计[J].青海师范大学学报:自然学科版, 2010, 26 (4) :48-51.

[2]彭旭东.C语言小程序算法的表示[J].天津理工大学学报, 2011, 27 (3) :35-38.

斐波那契数列及其递推思想浅谈 篇6

意大利数学家斐波那契 (Fibonacci, 约1 1 70～1 250) 于公元1 202年完成了一部伟大的论著《算法之书》。在书中, 他提出了一个著名的问题:

假设一对刚出生的小兔一个月后就能长成大兔, 再过一个月便能生下一对小兔, 并且此后每个月都生一对小兔, 一年内没有发生死亡。问一对刚出生的兔子, 一年内繁殖成多少对兔子?

逐月计算, 我们可以得到如下数列:

(1) 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233。

因此, 一对刚出生的小兔, 一年内所能繁殖的兔子的对数为233。

这个数列后来便以斐波那契的名字命名, 叫做“斐波那契数列”。

斐波那契数列在数学, 物理学, 生物学, 化学以及很多其他学科以及艺术都有着广泛的应用, 其递推的思想在解决数学问题时会显得精巧简洁, 所以掌握和运用这种方法就显得十分重要。

1.斐波那契数列递推思想

我们将上面“兔子繁殖问题“用数学语言改动一下:假设一对刚出生的小兔一个月后就能长成大兔, 再过一个月便能生下一对小兔, 并且此后每个月都生一对小兔, 如果将第n个月开始时的兔子总数记作F (n) , 按斐波那契的定义。F (n) 是下面数列的第n项:

(1) 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

我们用数学角度分析斐波那契数列的构造很容易发现斐波那契数列的每项都等于它前两项之和, 我们可以写出它的递推关系式:

2.斐波那契数列的递推思想运用

递推法是组合数学中的一个重要解题方法, 许多问题用递推法来解显得精巧简捷。首先我们观察这样的一道题:

例1用1或2两数字写n位数, 其中任意相邻两个位置不全为1。记能写出n位数的个数为f (n) , 求f (10) 。

分析:我们在考虑这样的题时, 首先要考虑符合例题的条件是什么, 在根据两个相邻位置考虑怎么运用斐波那契数列来给出相临几项的关系式。

解:符合条件的n位数可分为两类:

(Ⅰ) 首位是2, 则以下n-1位数符合条件的个数为f (n-1) ;

(Ⅱ) 首位是1, 则第二位应是2, 以下n-2位的个数为f (n-2) 。于是, f (n) =f (n-1) +f (n-2) , 故{f (n) }为斐波那契数列, 根据斐波那契数列的性质我门可以得到:

∵f (1) =2, f (2) =3, f (3) =f (2) +f (1) =5………

∴f (10) =144。

解本题的关键是对首位进行划分, 再运用斐波那契递推思想列式, 正确的分类, 讨论和运用递推思想是解题的关键。若将上例中2个数字推广成3个数字, 情形就更加的复杂了。

例2用1、2、3三个数字写n位数, 要求数中不出现紧挨着的两个1, 问能构成多少个6位数?

分析:当我们在解决递推与相邻问题时, 运用斐波那契递推思想解题时不一定拘于f (n) =f (n-1) +f (n-2) 式子上, 我们可以根据斐波那契数列递推思想来给出关系式, 将斐波那契数列递推思想提升到一个高度。

解:设符合条件的n位数共有an种, 按首位划分可分成:

Ⅰ.首位是2或3, 则以下n-1位各有an-1个, 共2an-1个;

Ⅱ.首位是1, 第二位只能为2或3, 共有2an-2个,

故an=2an-1+2an-2 (个) .

由初始条件得a1=2an-1+2an-2根据递推方程得a6=448。

从上面两个例题, 我们已经基本掌握了斐波那契数列的递推思想, 我们可以总结成以下的步骤:

先设问题F (n) 是可以按次序n=1, 2, …进行分级研究的, 则:

(1) 先研究解出最初若干问题F (1) , F (2) , F (3) 等。

(2) 再研究第n级F (n) , F (n-1) , F (n-2) 等问题之间的联系。

以上两道例题是以位置划分运用斐波那契数列思想求递推式的, 我们也已经基本掌握斐波那契数列递推的思想, 那么是否能根据元素之间的关系来求递推式呢?下面我们来看这样的两道例题。

例3有排成一行的8个方格, 把红、黄、蓝三种颜色的小球放入其中, 每个空格只能放入一个小球, 要求任何相邻的格中有不同色的小球, 且首尾两格的球也不同色。问有多少种放法?

分析:本题要求任何相邻两位有不同色的小球, 因此例的要求比前面两个例子更强, 若按首位划分, 讨论较为繁琐, 那么我们可按前n-1格首尾关系讨论来看。

解:设共有an种放法, 易见a1=3, a2=6, a3=6, 且当n≥4时, 将n个格子依次编号后, 格1与格 (n-1) 不相邻。

第一种情况:格 (n-1) 的小球与格1的球颜色不同, 此时格n只有一色小球可放, 且前 (n-1) 格满足首尾两格的小球不同色, 故有an-1种放法。

第二种情况:格 (n-1) 的小球与格1的小球颜色相同, 此时格 (n-2) 与格1的小球颜色必然不同, 不然, 格 (n-1) 与 (n-2) 相同, 于是前 (n-2) 格有an-2种放法。因为格n与格1的球不同色, 有两种球放法, 故共有2an-2种放法。

综上, 可得递推方程an=an-1+2an-2 (n≥4) 。

解得a6=228。

我们还可以根据上面的思想解决一类概率题。下面我们来看一道这样的例题:

例4把一枚硬币连掷7次, 在投掷过程中发生接连两次正面向上的概率是多少?

分析:我们在解决这类概率问题时, 要注意样本的变化规律, 我们可以参照例1来解决这道例题, 将硬币的正反面看成例1中的两位数字, 再运用斐波那契数列递推思想来列递推式。

解:以Q (n) 表示n次投掷过程中接连两次正面向上的概率, P (n) 表示不发生接连两次正面向上的概率。显然。若n>2, 则有两种情形:

Ⅰ.如第一次背面向上, 那么其余n-1次投掷中不出现两次正面向上的概率为P (n-1) 。

Ⅱ.如第一次正面向上, 第二次必须投出反面向上, 以免接连两次出现正面向上, 以后n-2次不接连两次出现正面向上的概率为P (n-2) 。

故我们可得递推式

解得2n P (n) =2n-1P (n-1) +2n-2P (n-2) 。

令S (n) =2n P (n) , 则S (n) =S (n-1) +S (n-2) (n>2) 。故{S (n) }为斐波那契数列, 且S (1) =2, S (2) =3, S (7) =34所以而所求概率为

例说递推关系求通项 篇7

类型一an+1=an+f (n) 型, an+1=f (n) an型

例1 (2007北京) 数列{an}中a1=2, an+1=an+cn (n=1, 2, 3, …) (c为常数) , 且a1, a2, a3成公比不为1的等比数列.

(1) 求c; (2) 求{an}的通项公式.

解 (1) 容易求得c=2.

(2) 当n≥2时, a2-a1=c, a3-a2=2c, …, an-an-1= (n-1) c,

∵a1=2, c=2,

∴an=n2-n+2, (n=2, 3, …) .当n=1时, 上式也成立.

∴an=n2-n+2, (n=1, 2, 3…) .

评注等差数列满足的递推关系an+1=an+d实际上是这种类型递推关系的特殊形式, 因此an+1=an+f (n) 可以依照求等差数列通项公式的累加法来求解.等比数列满足的递推关系an+1=qan, an+1=f (n) an类型递推关系的特殊形式, 因此可以依照求等比数列通项公式的累乘法来求解.

类型二an+1=pan+q型

当p=0, 1时, 数列{an}为等差数列;当p≠0, 1, q=0时, 数列{an}为等比数列.下面主要研究p≠0, 1, q≠1的情形.

例2 (2007全国卷1) 已知数列{an}中a1=2, an+1= (槡2-1) (an+2) , (n=1, 2, 3, …) .

(1) 求{an}的通项公式; (2) 略.

评注当p≠0, 1, q≠1时, 此类型的递推关系可以变形为an+1+x=p (an+x) (其中px-x=q) , 这样就构成了以a1+x为首项, p为公比的等比数列{an+x}, 从而原数列就化归为我们熟悉的等比数列来处理.

类型三an+1=pan+f (n) (p≠1) 型

(1) 对任意的实数λ, 证明数列{an}不是等比数列; (2) (3) 略.

∴k=-3, λ=21.

∴{an-3n+21}为等比数列,

∴{an}不是等比数列. (2) (3) 略.

评注此类型的问题一般解法是两边同时除以pn+1, 化归为bn+1=bn+g (n) 的类型, 按照类型一来处理.当f (n) 是形如an (a为常数) 时, 在累加求和时就是等比数列求和;但f (n) 是关于n的一次式时, 可变形为an+1+λ (n+1) +b=p (an+λn+b) , 即将其化归为一个等比数列{an+λn+b}来处理.

(1) 求数列{an}的通项公式; (2) (3) 略.

评注此类型的问题一般是通过等式两边同时取倒数, 从而化归为bn+1=pbn+q的类型, 按照类型三的解法来求解.

类型五an+2=pan+1+qan型

例5 (2008广东文) 设数列{an}满足a1=1, a2=2, (n=3, 4, …) .数列{bn}满足b1=1, bn是非零整数, 且对任意的正整数m和自然数k, 都有-1≤bm+bm+1+…+bm+k≤1.

(1) 求数列{an}和{bn}的通项公式; (2) 略.

解 (1) 不妨令an+2+kan+1=λ (an+1+kan) , (n=1, 2, …) , 即an+2= (λ-k) an+1+kλ·an.

评注形如此类型的递推关系可变形为an+2+kan+1=λ (an+1+kan) , 从而由λ-k=p, kλ=q解出k, λ, 于是数列{an+1+kan}构成了以λ为公比, 以a2+ka1为首项的等比数列, 就化归为等比数列问题.当k, λ无解时数列可能为周期数列, 通过求有限的几项可得到周期, 如数列{an}满足:an+2=an+1-an, a1=1, 通过求前8项会发现此数列为周期是6的周期数列.

类型六 (an+1) r=p (an) s型

下面解法同例5, 得到bn+1=-2bn.

评注递推关系式为 (an+1) r=p (an) s型的正项数列, 可以通过两边取对数, 从而化归为bn+1=pbn+q的类型处理, 但只有正项数列才可以如此解决, 要注意其局限性.

递推数列求通项方法举例 篇8

常见题型和方法有:

1.

an+1=an+f (n) 型, 此类问题可利用公式an=a1+ (a2-a1) + (a3-a2) +…+ (an-an-1) 求其通项

例2已知数列{an}中, a1=3且nan+1= (n+2) an+n, 求an.

解两边同时除以n (n+1) (n+2) , 得

2.

an+1=anf (n) 型, 此类型可利用公式求通项

例3已知数列{an}中, a1=1, 且an+1=2Nan (n≥2) , 求an.

3.an+1=pan+rqn型

例4 在数列{an}中, a1=1, an+1=2an+2n, 求an.

解 ∵an+1=2an+2n,

则数列{bn}为等差数列, 且b1=1, d=1, bn=n,

∴an=n·2n-1.

4.Sn=f (an) 型

例5 已知数列{bn}中, b1=1, Sn为数列{bn}的前n项和, 且满足求bn.

解 由已知, 当n≥2时,

又Sn=b1+b2+b3+…+bn,

又S1=b1=1,

∴数列是以1为首项, 公差为的等差数列.

∴当n≥2时,

5.an+1=can+d型 (c≠0, d≠0, c, d为常数)

例6 已知数列{an}中, 且an+1=3an-1, 求an.

解法1 (阶差法)

(1) - (2) , 得an+1-an=3 (an-an-1) ,

∴{an+1-an}是以a2-a1=2为首项, 3为公比的等比数列.

将 (1) 代入 (3) , 得

解法2 (待定系数法)

由an+1=3an-1, 则有

6.an+2=p1an+1+p2an型

此类型用常规方法解决很难, 可两次应用待定系数法.下面是特征方程法:

如果特征方程x2=p1x+p2有两个不等根α, β, 则an+2=p1an+1+p2an的通项为an=λ1αn+λ2βn, 如果有两个等根α, 则an=λ1αn+λ2nαn, 其中λ1, λ2由已知可求得.

例7已知数列{an}中, a1=1, a2=4, an+2=5an+1-6an, 求an.

解因为特征方程x2=5x-6的根为2和3,

∴an=λ12n+λ23n.

又a1=1, a2=4, 则有

聚焦递推式与新情境的交融 篇9

1. 挖掘递推关系探求概率问题

例1 从原点出发的某粒子M,按向量a=(0,1)移动的概率为23,按向量b=(0,2)移动的概率为13,设粒子M到达点(0,n)的概率为Pn(n∈N*).

(1) 求P1和P2的值;

(2) 求Pn的表达式.

解 (1) 由题意,P1=23,P2=232+13=79.

(2) M到达点(0,n+2)的前一次移动有两种情况:① 从点(0,n+1)出发,按向量a=(0,1)移动,概率为23Pn+1;② 从点(0,n),按向量b=(0,2)移动,概率为13Pn.

故Pn+2=23Pn+1+13Pn,从而Pn+2-Pn+1=-13(Pn+1-Pn),

所以数列{Pn+1-Pn}是以P2-P1=19为首项,-13为公比的等比数列.

所以Pn-1-Pn=19-13n-1=-13n+1,

所以Pn=P1+(P2-P1)+…+(Pn-1-Pn-2)+(Pn-Pn-1)

=23+-132+-133+…+-13n=23+1121--13n-1=34+14-13n(n≥2).

又P1=23=34+14×-13,

故Pn=34+14-13n.

点评 本题是用递推的思想探求概率的问题,既有向量“包装”,又与粒子的运动等知识交汇和渗透, 背景设计新颖,蕴含的数学知识复杂多样.若能充分揭示其内涵,既可使同学们更广泛、深刻地掌握所学知识,又能激发同学们求知的兴趣,开拓视野.

2. 利用递推法解决计数中的错排(或传球)问题

计数问题历来是数学竞赛、高考中必考内容之一,其表现形式多样,处理方法灵活,是学习中的一个难点.其中递推法是处理复杂计数问题的一种重要方法,它比列举法计数简捷,比对应法计数有更强的操作性.

例2 将分别标有数字1,2,3,…,n(n≥2)的n个小球放入分别标有数字1,2,3,…,n的n个盒子里,每个盒子里放一个小球,则小球的标号与所在盒子的标号均不相同的放法有多少种?

解 本题实质上是错位排列问题,即将每个小球都放到与自己标号不同的盒子里,不妨设其放法数为an.

当n=2时,两上小球两个盒子,错放只有一种情况,即a2=1.

当n≥3时,n+1个小球错放数an+1可以分两种情况计算:第一种情况是第n+1个小球放到第k(1≤k≤n)个盒子里,第k(1≤k≤n)个小球放到第n+1个盒子里,这时的错放数为an-1;第二种情况是第n+1个小球放到第k个盒子里,而第k个小球不放入第n+1个盒子里;这样就是将第n+1个小球以外的n个小球错放,放法数为an.又k可以是1,2,3,…n共n种可能,故n+1个小球错放数an +1= n(an-1+an)(n≥2),

所以an=(n-1)(an-1+an-2),

则ann!=an-2n(n-2)!+an-1n(n-2)!,

则nann!=(n-1)an-1(n-1)!+an-2(n-2)!,

则nann!-an-1(n-1)!=-an-1(n-1)!-an-2(n-2)!

则ann!-an-1(n-1)!=-1nan-1(n-1)!-an-2(n-2)!=-1n-1n-1an-2(n-2)!-an-3(n-3)!

=…=(-1)n-22n!a22!-a11!=(-1)nn!(n≥2).

所以ann!=a11!+a22!-a11!+a33!-a22!+…+ann!-an-1(n-1)!=a11!+∑nk=2(-1)k1k!,

所以an=n!•∑nk=2(-1)k1k!=n!12!-13!+14!+…+(-1)n1n!(n≥2).

点评 该题实质是利用递推思想解决计数(排列组合)问题,高考对排列、组合内容的考查一般以实际应用题形式出现,具有一定的灵活性和综合性.其复杂的情形常令人无从下手,若能根据题目特点建立递推关系则问题往往能迎刃而解.如利用此公式可方便地计算下面一道高考题:同室五人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺年卡,则五张贺年卡不同的分配方式有265种.

也可采用类似的方法解决传球问题:m(m≥2)个人相互传球,接球后即传给别人,由某人发球,并把他作为第一次传球,求经过n次传球后,球仍然回到此人手中的传球方式数.

分析 设满足题意的传球方式数为an,则an为以下两类传球方式数之差:第一类:A□□…□□(共n项);第二类: A□□…□A(共n项).第一类传球方式总数为(m-1)n-1,第二类传球方式总数为an-1.所以an=(m-1)n-1-an-1.变形得:an-(m-1)nm=-an-1-(m-1)n-1m,则数列an-(m-1)nm是公比为-1的等比数列,又a2=m-1,易求得an=m-1m(-1)n+(m-1)n-1(n≥2).

3. 利用递推法解决Hanoi塔问题

图1

例3 Hanoi塔由n个大小各不相同的圆盘和三根木柱a,b,c组成.开始时,将这n个圆盘由大到小依次套在a柱上,如图1所示.现在,

要求把a柱上的n个圆盘按下述规则移动到c柱上:

①一次只能移动一个圆盘;

②每次移动后圆盘只能在三个柱上存放;

③在移动过程中,不允许大盘压小盘.

问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次?

解 设bn为n个盘子从a柱移到c柱所需移动的盘次.显然当n=l时,只需把a柱上的盘子直接移动到c柱就可以了,故b1=l.当n=2时,先将a柱上面的小盘子移动到b柱上去;然后将大盘子从a柱移到c柱;最后,将b柱上的小盘子移到C柱上,共记3个盘次,故b2=3.以此类推,当a柱上有n(n≥2)个盘子时,总是先借助C柱把上面的n-1个盘子移动到b柱上,然后把a柱最下面的盘子移动到c柱上;再借助a柱把b柱上的n-1个盘子移动到c柱上;总共移动bn-1+1+bn-1个盘次.

所以bn=2bn-1+1(n≥2),则bn+1=2(bn-1+1),所以数列{bn+1}是公比为2的等比数列,又b1+1 =2,

所以bn+1=2n,即bn=2n-1.

点评 这是一个古老的数学游戏,据说古代印度婆罗门教寺庙内的僧侣们玩着这一称为“汉诺(Hanoi)塔问题(n=64)”的游戏,认为如果这场游戏能玩到结束,就意味着世界末日的来临.由上述计算可得:当n=64时,b64=264-1=184 467 440 737 095 516 15,如果是一个人用手工移动,昼夜不停,一秒移一次,需要580亿年才能完成,也就大可不必担心世界末日的来临.

4. 利用递推法解决分形几何问题

例4 一艘太空飞船飞向地球.第一次观测时,如图(1)发现它是一个正三角形“岛屿”(边长为1),第二次观测时,如图(2)发现它每边的中央13处还有一正三角形“海岬”;第三次观测时,如图(3)发现它每一小边的中央13处又有一向外突出的“海岬”.把这个过程无限地继续下去,就得到了著名的数学模型——“侠客岛”.

图2

(Ⅰ) 求第n次观测到的“岛屿”的海岸线长an;

(Ⅱ) 求第n次观测到的“岛屿”的面积bn.

解 设第n次观测到的“岛屿”的边数为cn,边长为dn.

由题意,后一个“岛屿”的边长是前一个“岛屿”边长的13,后一个“岛屿”的边数是前一个“岛屿”边数的4倍,即cn=4cn-1,dn=13dn-1,

又c1=3,d1=1,

所以cn=3×4n-1,dn=13n-1.

(1) an=cndn=343n-1.

(2) 由题意,bn=bn-1+cn-1×34d2n=bn-1+3×4n-2×34×132n-2(n≥2),

故bn-bn-1=2736449n(n≥2).

由累加法得bn=34+33201-49n-1.

5. 利用递推法求解物理难题

递推法较适合求解物体与物体间发生多次作用(或运动)的情景.该法在近几年物理高考的压轴题的求解中常常用到,具体方法是:先分析某一次作用的情况,得出结论,再根据多次作用的重复性和它们的共同点,建立递推关系从而转化成数学问题求解.

例5 一辆质量为M的平板车,放在光滑的水平轨道上.车上有n个人,每个人的质量均为m.最初车与人均处于静止状态,如果车上的人相继以相对于车的速度v从车尾跳离车,求当n个人全部跳离车后平板车的速度大小.

解 由于每个人跳车后车对地的速度不同,所以各个人跳车时对地的速度也不同.

用vn表示第n个人跳离车后平板车相对于地的速度,因每次跳车时,人和车动量守恒.

则第一个人跳离车时,有[M+(n-1)m]v1=m(v-v1),所以v1=mM+nmv.

第n个人跳离车,有Mvn=(M+m)vn-1+m(v-vn),化简得vn-vn-1=mM+mv(n≥2),

所以vn=v1+(v2-v1)+…+(vn-vn-1)=mM+nm+mM+(n-1)m+…+mM+mv(n=1也适合).

点评 本题是一道物理高考压轴题,该法解题的关键是正确导出相邻两次作用的递推关系.

6. 利用递推法求解化学信息题

例6 一卤代物只有一种的烷烃,其分子结构有“球形”(A)和“椭球形”(B)两类,它们的组成有一定的规律,A类是以甲烷(CH4)分子当起始物,然后当甲烷分子中的所有氢原子用甲基取代得到C(CH3)4,再将C(CH3)4中的所有氢原子用甲基取代就得到C[C(CH3)3]4,如此循坏以至无穷,“球形”分子由小到大形成一个系列;B类是以乙烷(CH3-CH3)分子当起始物,然后将CH3-CH3中的所有氢原子用甲基取代后得到(CH3)3C-C(CH3)3,再将(CH3)3C-C(CH3)3中的所有氢原子用甲基取代就得到[C(CH3)3]3C-C[C(CH3)3]3,如此循坏以至无穷,“椭球”形分子由小到大也形成一个系列.求:A类物质的分子通式为;B类物质的分子通式为.

解 对A类,设碳原子数为an ,氢原子数为bn,则an=an-1+bn-1,bn=3bn-1,

又a1=1,b1=4,所以bn=4×3n-1 ,an-an-1=4×3n-2 ,

则an=a1+(a2-a1)+…+(an-an-1)=1+4×(30+31+32+…+3n-2)=1+4×1-3n-11-3=2×3n-1-1.

所以an=2×3n-1-1,所以A类物质的分子通式为C2×3n-1H4×3n-1.

对B类:设碳原子数为an,氢原子数为bn,同理得a1=2,b1=6, an=an-1+bn-1, bn=3bn-1,

所以bn=6×3n-1 ,an -an-1=6×3n-2 ,累加得:an=3n-1,

所以B类物质的分子通式为C3n-1H2×3n.

评注 本题是化学与递推数列的交汇问题,递推式为两个数列的螺旋式,采用各个击破的方法予以解决.

从以上几类问题可以看出,递推法应用的领域相当广泛, 问题的情境新颖别致.且往往跨章节、跨学科从而有一定的广度和创新度,是一类锻炼思维能力的好题型,应引起足够重视.

巩 固 练 习

1. 已知f(x)是定义在R上的不恒为零的函数,且对任意a,b∈R,都有f(ab)=af(b)+bf(a).

(1) 求f(0)与f(1)的值;

(2) 若f(2)=2,un=f(2-n)n(n∈N*),求数列{un}的前n项和Sn的表达式.

2. 我国西北某县位于沙漠地带,那里的人长期与自然进行着顽强的斗争.已知到1998年底,全县的绿化率已达到30%(成为绿洲).从1999年开始,每年将出现这样的局面:原有沙漠面积的16%被改造成绿洲,而同时原有绿洲面积的4%又被侵蚀成沙漠.问到哪一年(的年底)才能使全县的绿化率超过60%?(取lg2=0.301)

3. 现有流量均为300m3/s的两条河流A,B汇合一某处后,不断混合,它们含沙量分别为2 kg/m3和0.2 kg/m3.假设从汇合处开始,沿岸设有若干观测点,两股水流在流径相邻两个观察点的过程中,其混合效果相当于两肥肉水流在1秒内交换100 m3的水量,即从A股流入B股100 m3水并混合,经混合后,又从B股流入A股100 m3水并混合,问:从第几个观察点开始,两股河水的含沙量为0.01 kg/m3(不考虑泥沙沉淀).

4. A,B两人拿两颗骰子做抛掷游戏,规则如下:一人先掷两骰子,若掷出的点数之和是3的倍数,则由原投掷的人继续掷;若掷出的点数之和不是3的倍数,则由对方接着掷.设第一次由A掷,求第n次由A掷的概率Pn.

“递推法”在编程中的应用 篇10

递推算法在各种程序设计教法中都有介绍，如著名的裴波拉契数列、多项式计算等，另外累加、累乘也属于最简单的递推算法。

一、用递推法实现多重循环

例1：(经典的八皇后问题)在一个国际象棋盘中，如何放置8个皇后，使它们互不攻击?

用计算机解决这一问题的最简单的算法就是用8重循环列举出所有可能的放置方法，然后判断每种放置方法是否符合题意要求。

用多重循环虽然简单，但存在两个缺点：

1. 程序冗长，对于8重循环还好，如果是100重循环，就要用100个for语句。

2. 程序通用性差，如将上述问题改为在10*10的棋盘上放置10个皇后，程序就得修改为10重循环。

用递推法实现多重循环可以克服上述缺点，无论多少重循环，都可以用两重循环来实现(见程序1)。

其基本思路如下：

(1) 用数组元素a (1)到a (8)代替循环变量，赋予值1。

(2) 循环体：对这组值进行判断处理。

(3) 由a (1)到a (8)的当前值，递推出下一组值。

具体递推方法为：用循环在a (1)到a (8)中，倒找第一个未到终值的元素，并将已到终值元素重置为初值1。

(4) 如果找到了第一个未到终值的元素，则使其值加1，转 (2) ;否则结束循环。

二、用递推法解决排列问题

排列问题是一种常见问题，经常在中学信息技术奥赛中出现，解决这一问题的最常见方法是用递归算法。而用递推法解决排列问题，效率更高。

例2：打印出所有用1到8构成的8位数(数字不允许重复使用)。

用递推法解决问题的关键是找出前后项之间的关系，也就是如何从前一项推导出下一项。为此，我们先按顺序列出一些排列结果如下(从小到大排列)：

考察其中的任一排列，如12346875，会发现最后3位875已是倒序排列，改变它们的次序得到的结果(如12346785)肯定比它小，必然已经在前面出现过。所以要得到新的比12346875大的最小数，必须调整875前面的数字6，具体方法就是用875中大于6的最小数字7与6交换位置，再将865颠倒一下顺序，即可得到新的最小值排列。(见程序2)

三、递推法应用举例

例3：将编号为1到10的十个球分给5个人，每人2个，请编程打印出所有分配方案。

本题比较难，既存在排列问题，又涉及到组合问题。如果利用程序2将1到10这十个数进行全排列(其中第1、2两个球分给第1个人，第3、4两个球分给第2个人，以此类推)，然后去除重复的分配方案，即可以比较容易地解决。(程序略)

由于全排列中存在大量重复的分配方案，上述算法运行效率较低，最好还是研究出直接递推的方法。为此我们先按顺序列出一些分配方案，以便找出其中的递推关系。

查看任一方案，如(1, 2) (3, 4) (5, 10) (8, 9) (6, 7)，该方案最后两组数(8, 9) (5, 7)已呈倒序排列，任意交换其中的数据，得到的都是前面出现过的方案。所以要得到新方案必须与前一括号中的数据(6, 10)进行位置交换，具体又分两种情况。

第一种情况是(8, 9) (5, 7)中不存在大于10的数，此时的处理方法是先将6后面的数升级排列得(6, 5) (7, 8) (9, 10)，再用后面第一个比6大数(7)与6交换位置得(7, 5) (6, 8) (9, 10)，最后将下一个比6大的数(8)移到(7)后面即可得到新方案(1, 2) (3, 4) (7, 8) (5, 6) (9, 10)。

另一种情况是存在大于10的数，此时只要将10后面的数升序排列，然后用第一个大于10的数与10交换即可，不需要移动过程。