斐波那契数列算法分析报告

斐波那契数列算法分析

背景：假定你有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始交配，在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖时每月都产下一对兔子，假定没有兔子死亡，在一年后总共会有多少对兔子？

在一月底，最初的一对兔子交配，但是还只有1对兔子；在二月底，雌兔产下一对兔子，共有2对兔子；在三月底，最老的雌兔产下第二对兔子，共有3对兔子；在四月底，最老的雌兔产下第三对兔子，两个月前生的雌兔产下一对兔子，共有5对兔子；……如此这般计算下去，兔子对数分别是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...看出规律了吗？从第3个数目开始，每个数目都是前面两个数目之和。这就是著名的斐波那契（Fibonacci）数列。

有趣问题：

1，有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

答：这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种方法……所以，1，2，3，5，8，13……登上十级，有89种。

2，数列中相邻两项的前项比后项的极限是多少，就是问，当n趋于无穷大时，F(n)/F(n+1)的极限是多少？

答：这个可由它的通项公式直接得到，极限是(-1+√5)/2，这个就是所谓的黄金分割点，也是代表大自然的和谐的一个数字。

数学表示：

Fibonacci数列的数学表达式就是：

F(n) = F(n-1) + F(n-2)

F(1) = 1

F(2) = 1

递归程序1：

Fibonacci数列可以用很直观的二叉递归程序来写，用C++语言的描述如下：

long fib1(int n)

{

if (n <= 2)

{

return 1;

}

else

{

return fib1(n-1) + fib1(n-2);

}

}

看上去程序的递归使用很恰当，可是在用VC2005的环境下测试n=37的时候用了大约3s，而n=45的时候基本下楼打完饭也看不到结果……显然这种递归的效率太低了！！

递归效率分析：

例如，用下面一个测试函数：

long fib1(int n, int* arr)

{

arr[n]++;

if (n <= 2)

{

return 1;

}

else

{

return fib1(n-1, arr) + fib1(n-2, arr);

}

}

这时，可以得到每个fib(i)被计算的次数：

fib(10) = 1 fib(9) = 1 fib(8) = 2 fib(7) = 3

fib(6) = 5 fib(5) = 8 fib(4) = 13 fib(3) = 21

fib(2) = 34 fib(1) = 55 fib(0) = 34

可见，计算次数呈反向的Fibonacci数列，这显然造成了大量重复计算。

我们令T(N)为函数fib(n)的运行时间，当N>=2的时候我们分析可知：

T(N) = T(N-1) + T(N-2) + 2

而fib(n) = fib(n-1) + fib(n-2)，所以有T(N) >= fib(n)，归纳法证明可得：

fib(N) < (5/3)^N

当N>4时，fib（N）>= (3/2)^N

标准写法：

显然这个O（(3/2)^N）是以指数增长的算法，基本上是最坏的情况。

其实，这违反了递归的一个规则：合成效益法则。

合成效益法则（Compound interest rule）：在求解一个问题的同一实例的时候，切勿在不同的递归调用中做重复性的工作。

所以在上面的代码中调用fib(N-1)的时候实际上同时计算了fib(N-2)。这种小的重复计算在递归过程中就会产生巨大的运行时间。

递归程序2：

用一叉递归程序就可以得到近似线性的效率，用C++语言的描述如下：

long fib(int n, long a, long b, int count)

{

if (count == n)

return b;

return fib(n, b, a+b, ++count);

}

long fib2(int n)

{

return fib(n, 0, 1, 1);

}

这种方法虽然是递归了，但是并不直观，而且效率上相比下面的迭代循环并没有优势。

迭代解法：

Fibonacci数列用迭代程序来写也很容易，用C++语言的描述如下：

//也可以用数组将每次计算的f(n)存储下来，用来下次计算用（空间换时间）

long fib3 (int n)

{

long x = 0, y = 1;

for (int j = 1; j < n; j++)

{

y = x + y;

x = y - x;

}

return y;

}

这时程序的效率显然为O（N），N = 45的时候<1s就能得到结果。

矩阵乘法：

我们将数列写成：

Fibonacci[0] = 0，Fibonacci[1] = 1

Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2] (n >= 2)

可以将它写成矩阵乘法形式：

将右边连续的展开就得到：

下面就是要用O(log(n))的算法计算：

显然用二分法来求，结合一些面向对象的概念，C++代码如下：

class Matrix

{

public:

long matr[2][2];

Matrix(const Matrix&rhs);

Matrix(long a, long b, long c, long d);

Matrix& operator=(const Matrix&);

friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)

{

Matrix ret(0,0,0,0);

ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1] [0];

ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1] [1];

ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1] [0];

ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1] [1];

return ret;

}

};

Matrix::Matrix(long a, long b, long c, long d)

{

this->matr[0][0] = a;

this->matr[0][1] = b;

this->matr[1][0] = c;

this->matr[1][1] = d;

}

Matrix::Matrix(const Matrix &rhs)

{

this->matr[0][0] = rhs.matr[0][0];

this->matr[0][1] = rhs.matr[0][1];

this->matr[1][0] = rhs.matr[1][0];

this->matr[1][1] = rhs.matr[1][1];

}

Matrix& Matrix::operator =(const Matrix &rhs) {

this->matr[0][0] = rhs.matr[0][0];

this->matr[0][1] = rhs.matr[0][1];

this->matr[1][0] = rhs.matr[1][0];

this->matr[1][1] = rhs.matr[1][1];

return *this;

}

Matrix power(const Matrix& m, int n)

{

if (n == 1)

return m;

if (n%2 == 0)

return power(m*m, n/2);

else

return power(m*m, n/2) * m;

}

long fib4 (int n)

{

Matrix matrix0(1, 1, 1, 0);

matrix0 = power(matrix0, n-1);

return matrix0.matr[0][0];

}

这时程序的效率为O（log(N)）。

公式解法：

在O（1）的时间就能求得到F(n)了：

注意：其中[x]表示取距离x最近的整数。

用C++写的代码如下：

long fib5(int n)

{

double z = sqrt(5.0);

double x = (1 + z)/2;

double y = (1 - z)/2;

return (pow(x, n) - pow(y, n))/z + 0.5;

}

这个与数学库实现开方和乘方本身效率有关的，我想应该还是在O(log(n))的效率。

总结：

上面给出了5中求解斐波那契数列的方法，用测试程序主函数如下：

int main()

{

cout << fib1(45) << endl;

cout << fib2(45) << endl;

cout << fib3(45) << endl;

cout << fib4(45) << endl;

cout << fib5(45) << endl;

return 0;

}

函数fib1会等待好久，其它的都能很快得出结果，并且相同为：1134903170。

而后面两种只有在n = 1000000000的时候会显示出优势。由于我的程序都没有涉及到高精度，所以要是求大数据的话，可以通过取模来获得结果的后4位来测试效率与正确性。

另外斐波那契数列在实际工作中应该用的很少，尤其是当数据n很大的时候（例如：10000 00000），所以综合考虑基本普通的非递归O(n)方法就很好了，没有必要用矩阵乘法。

1、N皇后问题算法设计

ALGORITHM

procedure PLACE(k)

//如果一个皇后能放在第k行的X(k)列，则返

回true；否则返回false。X是一个全程数

组，进入此过程时已置了k个值。//

global X(1：k)； integer i，k

i←1

while i

if X (i)＝X(k) //在同一列有两个皇后//

or ABS(X(i)－X(k))＝ABS(i－k)

//在同——条斜角线上//

then return(false)

endif

i←i+1

repeat

return(true) //满足约束//

end PLACE

procedure NQUEENS(n)

//此过程使用回溯法求出在一个n*n棋盘上放置n个皇后，使其能互相攻击的所有可能位置//

X(1)←0；k←1 //k是当前行；X(k)是当前列//

While k>0 do //对所有的行执行以下语句//

{ X(k)←X(k)+1 //移到下一列//

While X(k)≤n and not PLACE(k) do

{X(k)←X(k)十l;} // 如果第k个皇后的列X(k)不合理，就看下一列// if X(k)≤n //找到一个位置//

then if k=n //是一个完整的解吗//

then print(X) //是，打印这个数组//

else {k←k+1；X(k)←0；}

endif //扩展，搜索下一个皇后//

else k←k－1 //回溯//

endif

}

end NQUEENS

Program :

#include

#include

int k=0,a[20],j=1,flag,n,c=0;//k为解的个数,n为皇后的个数,flag标记有没有放置皇后

void lycQueen(){//递归求解函数

int i,h;//i为行号,h为列号

for(h=1;h<=n;h++){

a[j]=h;

for(i=1;i

if(a[i]==a[j]||abs(a[j]-a[i])==abs(j-i)) {flag=0;break;}//两个皇后在同一行或者同一对角线上,冲突

else flag=1;//没冲突,放置一个皇后

}//for

if(flag==0&&a[j]!=n) continue;//没试探完,继续试探

if(flag==1&&j==n){//放置完n个皇后,得到一个解

k=k+1;c=1;//解的个数加1

for(i=1;i<=n;i++)

printf("%d ",a[i]);//输出第i个皇后放置的行号

printf("\n");

if(a[j] == n)

flag = 0;

}//if

if(flag==1&&j!=n){j++;lycQueen();}//递归调用

if(flag==0&&a[j]==n){j--;}//回溯,退回去重新试探

}//for

}//lycQueen

void main(){

int i;

printf("请输入皇后的个数:");

scanf("%d",&n);//输入皇后的个数n

j=1;

for(i=1;i<=n;i++){

a[j]=i;

j=j+1;

lycQueen();//调用lycQueen函数

if(c==1) j=1;

}//for

printf("解的个数为%d个\n",k);

}//main

斐波那契数列资料

斐波那契数列

斐波那契数列 一、简介 斐波那契数列（Fibonacci），又称黄金分割数列，由数学家斐波那契最早以“兔子繁殖问题”引入，推动了数学的发展。故斐波那契数列又称“兔子数列”。 斐波那契数列指这样的数列：1,1,2,3,5,8,13,……，前两个数的和等于后面一个数字。这样我们可以得到一个递推式，记斐波那契数列的第i项为F i，则F i=F i-1+F i-2. 兔子繁殖问题指设有一对新生的兔子，从第三个月开始他们每个月都生一对兔子，新生的兔子从第三个月开始又每个月生一对兔子。按此规律，并假定兔子没有死亡，10个月后共有多少个兔子？ 这道题目通过找规律发现答案就是斐波那契数列，第n个月兔子的数量是斐波那契数列的第n项。 二、性质 如果要了解斐波那契数列的性质，必然要先知道它的通项公式才能更简单的推导出一些定理。那么下面我们就通过初等代数的待定系数法计算出通项公式。 令常数p,q满足F n-pF n-1=q(F n-1-pF n-2)。则可得： F n-pF n-1=q(F n-1-pF n-2) =q2(F n-2-pF n-3) =…=q n-2(F2-pF1) 又∵F n-pF n-1=q(F n-1-pF n-2) ∴F n-pF n-1=qF n-1-pqF n-2 F n-1+F n-2-pF n-1-qF n-1+pqF n-2=0 (1-p-q)F n-1+(1+pq)F n-2=0 ∴p+q=1,pq=-1是其中的一种方程组 ∴F n-pF n-1= q n-2(F2-pF1)=q n-2(1-p)=q n-1 F n=q n-1+pF n-1=q n-1+p(q n-2+p(q n-3+…))=q n-1+pq n-2+p2q n-3+…+p n-1 不难看出，上式是一个以p/q为公比的等比数列。将它用求和公式求和可以得到： 而上面出现了方程组p+q=1,pq=-1，可以得到p(1-p)=-1,p2-p-1=0，这样就得到了一个标准的一元二次方程，配方得p2-p+0.25=1.25,(p-0.5)2=1.25,p=±√1.25+0.5。随意取出一组解即可： 这就是著名的斐波那契数列通项公式。有了它，斐波那契数列的一些性质 也不难得出了。比如斐波那契数列相邻两项的比值趋向于黄金分割比，即：

数列通项公式方法大全很经典精品

【关键字】方法、关键、关系、满足 1，数列通项公式的十种求法： （1）公式法（构造公式法） 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则113222 n n n n a a ++-= ，故数列{}2n n a 是以122 2 a 1 1==为首项，以23为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31 ()222 n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 113 222 n n n n a a ++-=，说明数列{}2n n a 是等差数列，再直接利用等差数列的通项公式求出31(1)22n n a n =+-，进而求出数列{}n a 的通项公式。 （2）累加法 例2 已知数列{}n a 满足1121 1n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 所以数列{}n a 的通项公式为2 n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-+ +-+-+，即得数列{}n a 的通项公式。 变式：已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。 （3）累乘法 例3已知数列{}n a 满足112(1)53n n n a n a a +=+?=，，求数列{}n a 的通项公式。 解：因为112(1)53n n n a n a a +=+?=，，所以0n a ≠，则 1 2(1)5n n n a n a +=+，故

斐波那契数列教学设计

《斐波那契数列》教学设计 杨遇春 教学背景： 《斐波那契数列》是江苏教育出版社《普通高中课程标准实验教科书·数学·必修5》第59页的阅读材料，是学生在学习完数列（主要是等差数列和等比数列）后安排的一节课外学习内容。考虑到本节内容学生自学有一定难度，同时本节课对培养学生学习数学的兴趣，提高自己对数列的认识和后续学习都很有帮助，而且本课所强调的自主探索、合作交流的学习能力在我们的学生中还有待进一步提高，因此我决定用一节课引导学生学习本节内容。 多媒体技术是现代课堂教学的重要手段，它为我们提供大量的信息和课程内容，是提高课堂效率、丰富课堂内容的有效途径。在本节课我主要借助PowerPoint演示加网络搜索的方法教学，用PowerPoint来向学生展示本节的主要学习思路和大纲，然后问题引导学生用网络搜索引擎查找问题答案展开学习。 教学目标： 1．使学生了解了斐波那契数列； 2．向学生展示生活中的数学，感受数学美和数学思想； 3．指导学生在现代技术条件下如何从网络上选择知识和学习知识进而解决问题。 教学重点： 认识斐波那契数列 教学过程： 1、斐波那契数列的由来（创设情景，引入主题） 先用PowerPoint让学生看一个有趣的问题：有一个人第一月底时在一间房子里放了一对刚出生的小兔，小兔一个月后能长成大兔，再过一个月便能生下一对小兔，次后每个月生一对小兔。如果不发生死亡，那么到年底这个人有多少对兔子？ 先由学生自己思考，我不急于公布答案，而是与同学们共同做如下研： 我们用◎表示一对大兔，用○表示一对小兔，逐月统计兔子的对数（用PowerPoint逐月显示，加以讲解，务必要学生理解递推的本质） 第1月底○ 第2月底◎ 第3月底◎○ 第4月底◎○◎ 第5月底◎○◎◎○ 第6月底◎○◎◎○◎

数列通项公式方法大全很经典

1，数列通项公式的十种求法： （1）公式法（构造公式法） 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则113222 n n n n a a ++-= ，故数列{}2n n a 是以1 2 22a 11==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31 ()222 n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 113222 n n n n a a ++-=，说明数列{}2n n a 是等差数列，再直接利用等差数列的通项公式求出3 1(1) 22 n n a n =+-，进而求出数列{}n a 的通项公式。 （2）累加法 例2 已知数列{}n a 满足11211n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 所以数列{}n a 的通项公式为2n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为121n n a a n +-=+，进而求出 11232211()()()()n n n n a a a a a a a a a ----+-+ +-+-+，即得数列{}n a 的通项公式。 变式：已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。 （3）累乘法 例3已知数列{}n a 满足112(1)53n n n a n a a +=+?=，，求数列{}n a 的通项公式。

(完整版)已知数列递推公式求通项公式的几种方法

求数列通项公式的方法 一、公式法 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则113222n n n n a a ++-=，故数列{}2 n n a 是以1222 a 1 1==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31()222 n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 11 3 222 n n n n a a ++-=，说明数列{}2n n a 是等差数列，再直接利用等差数列的通项公式求出31(1)22 n n a n =+-，进而求出数列{}n a 的通项公式。 二、累加法 例2 已知数列{}n a 满足1121 1n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 11232211 2 ()()()()[2(1)1][2(2)1](221)(211)1 2[(1)(2)21](1)1 (1)2(1)1 2 (1)(1)1n n n n n a a a a a a a a a a n n n n n n n n n n n ---=-+-++-+-+=-++-+++?++?++=-+-++++-+-=+-+=-++=L L L 所以数列{}n a 的通项公式为2 n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-++-+-+L ，即得数列{}n a 的通项公式。

数列通项公式方法大全

数列通项公式的十种求法： （1）公式法（构造公式法） 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则113222n n n n a a ++-=，故数列{}2n n a 是 以1222 a 1 1==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31()222 n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 113 222 n n n n a a ++-=，说明数列{}2n n a 是等差数列，再直接利用等差数列的通项公式求出31(1)22 n n a n =+-，进而求出数列{}n a 的通项公式。 （2）累加法 例2 已知数列{}n a 满足11211n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 11232211 2 ()()()()[2(1)1][2(2)1](221)(211)1 2[(1)(2)21](1)1 (1)2(1)1 2 (1)(1)1n n n n n a a a a a a a a a a n n n n n n n n n n n ---=-+-++-+-+=-++-+++?++?++=-+-++++-+-=+-+=-++=L L L 所以数列{}n a 的通项公式为2 n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-++-+-+L ，即得数列{}n a 的通项公式。 变式：已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。 （3）累乘法

数学-斐波那契数列01

内蒙古自治区中小学教师教育技术水平（初级）试卷（试卷科目：中学数学）01 第一部分：基本知识题（本部分共8个题，每题2.5分，满分20分） 第1题 (单选题)根据您对教育技术及相关基础知识的理解，下例选项不正确的一项是（ C）。 (2.5分) A．教育技术就是为了促进学习，对有关的学习过程和资源进行设计、开发、利用、管理和评价的理论与实践 B．教学设计是运用系统方法分析教学问题和确定教学目标，建立解决教学问题的策略方案、试行解决方案、评价试行结果和对方案进行修改的过程C．教育技术与信息技术的涵义是一样的，只是用不同的名词来表述而已D．教育信息化是指在教育教学的各个领域中，积极开发充分应用信息技术和信息资源，以促进教育现代化，培养满足社会需求人才的过程 第2题 (单选题)在美国，教育技术作为一个新兴的实践和研究领域而出现始于下列选项内容的是（ A）。 (2.5分) A．视听运动 B．计算机辅助教育 C．程序教学法 D．网络技术应用 第3题 (单选题)"教师不应一味以传统集体传授教学的方式进行教学，而应使用能够让学生进行操作或进行社会活动的方式来学习"，这反映的是（ A ）的学习观。 (2.5分) A．建构主义 B．人本主义 C．行为主义 D．认知主义 第4题 (单选题)在视听教学运动背景下，对教育技术基本内涵表述不恰当的是（ C）。 (2.5分) A．在教学过程中所应用的媒体技术手段和技术方法 B．在教学过程中所应用的媒体技术和系统技术 C．在教学过程中所应用的媒体技术 D．在教学过程中所应用的媒体开发和教学设计 第5题 (单选题)关于教学方法的选择，下列选项中说法正确的是（ C ）。 (2.5分) A．教学方法的选择不涉及学习者特征方面因素

(完整版)数列的递推公式教案

数列的递推公式教案 普兰店市第六中学陈娜 一、教学目标 1、知识与技能：了解数列递推公式定义，能根据数列递推公式求项，通过数列递推公式求数列的通项公式。 2、过程与方法：通过实例“观察、分析、类比、试验、归纳”得出递推公式概念，体会数列递推公式与通项公式的不同，探索研究过程中培养学生的观察归纳、猜想等能力。 3、情感态度与价值观：培养学生积极参与，大胆探索精神，体验探究乐趣，感受成功快乐，增强学习数学的兴趣，培养学生一切从实际出发，认识并感受数学的应用价值。 二、教学重点、难点和关键点 重点：数列的递推定义以及应用数列的递推公式求出通项公式。 难点：数列的递推公式求通项公式。 关键：同本节难点。 三、教学方法 通过创设问题的情境，在熟悉与未知的认知冲突中激发学生的探索欲望；引导学生通过自主探究和合作交流相结合的方式进行研究；引导学生积极思考，运用观察、试验、联想、类比、归纳、猜想等方法不断地提出问题、解决问题，再提出问题，解决问题……经历知识的发生和发展过程，并注意总结规律和知识的巩固与深化。 四、教学过程 环节1：新课引入 一老汉为感激梁山好汉除暴安良，带了些千里马要送给梁山好汉，见过宋江以后，宋江吧老汉带来的马匹的一半和另外一匹马作为回礼送给了他，老汉又去见卢俊义，把

现有的马匹全送给了他，卢俊义也把老汉送来的马匹的一半和另外一匹马作为回礼送给了老汉……… 一直送到108名好汉的最后一名段景住都是这样的，老汉下山回家时还剩下两匹马，问老汉上山时一共带了多少匹千里马？ 通过这个小故事让学生感受到数学来源于生活同时又为生活所服务。同时也能引起学生的兴趣和好奇心。 环节2：引例探究 (1）1 2 4 8 16……… (2) 1 ()1cos ()1cos cos ()]1cos cos[cos ……. (3)0 1 4 7 10 13 ……. 通过设置问题的情境，让学生分析找出这些数列从第二项（或后几项）后一项与前一项的关系，从而引出数列的递推公式的定义，便于学生对于数列递推公式的理解、记忆和应用。 递推公式定义： 如果已知数列的第1项（或前几项），且从第二项（或某一项）开始的任意一项a n 与它的前一项a n-1（或前几项）间的关系可以用一个公式来表示，那么这个公式就叫做这个数列的递推公式。递推公式是数列一种的表示法，它包含两个部分，一是递推关系，一是初始条件，二者缺一不可． 环节3：应用举例及练习 例1：已知数列｛a n ｝的第1项是1，以后的各项由公式 (n ≥2)给出，写出这个给出，写出这个数列的前5项. 解：据题意可知：a 1=1, 1 11n n a a -=+2111112,1a a =+=+=3211311,22a a =+=+=4312511,33a a =+=+=5413811.55a a =+ =+=

斐波那契数列的通项公式推导解析

斐波那契数列的通项公式推导 山西省原平市原平一中任所怀 做了这些年的数学题，我时常有这样的感受。一个新的数学题初次接触时，会觉得这个题的解题技巧很妙，甚至有点非夷所思，但如果把同类型问题多做几个，你就会发现原来所谓的技巧，其实是一种再正常不过的想法，是一种由已知到未知的必然之路。这样我们就由解题的技巧而转化到了通解通法，进一步就会形成解题的思想，所以我对于数学爱好者建议，做题时要把同类型题多种总结和分析，这样你的数学才会有长足的进步。 下面我们就由递推推导通项的问题，进行对比分析。 例1在数列中，，求数列的通项。（普通高中课程标准实验教科书人教A版必修5第69页6题） 分析：此题可分两步来进行，首先由构造一个等比数列，其中 ，并写出的通项；然后利用，两边同除以得 ，由累加法，就可求出数列的通项。 解：（ 设，则（）所以数列为等比数列，且首项为 ，公比为3。所以。 于是有，两边都除以得 设，则有 由累加法可得

因为所以（） 于是有。 总结：上面的求解过程实质，求是一个把已知条件逐步化简的过程，由相邻三项的递推关系化为相邻两项的递推关系，进一步求出通项公式。 下面我们来研究一下著名的斐波那契数列的通项。 已知数列，其中，，求数列的通项。 解：首先我们要构造一个等比数列，于是设 则有。（1） 则由已知得（2） 对照（1）（2）两式得解得或。 我们取前一解，就会有。 设，则有 所以数列为等比数列，首项为，公比为

所以。即（3） 再次构造等比数列，设 则有 对照（3）式，可得所以 x=. 于是有 设，则有数列为等比数列，首项为，公比为，于是= 所以有。

求数列通项公式方法大全

求数列通项公式的常用方法 类型1、()n n S f a = 解法：利用???≥???????-=????????????????=-)2() 1(11n S S n S a n n n 与)()(11---=-=n n n n n a f a f S S a 消去 n S )2(≥n 或与)(1--=n n n S S f S )2(≥n 消去n a 进行求解。 例 1 已知无穷数列{}n a 的前n 项和为n S ，并且*1()n n a S n N +=∈，求{}n a 的通项公式？ 1n n S a =-，∴ 111n n n n n a S S a a +++=-=-，∴ 112n n a a +=，又112a =，12n n a ??= ??? . 变式 1. 已知数列{}n a 中，3 1 1= a ，前n 项和n S 与n a 的关系是 n n a n n S )12(-= ，求n a 变式2. 已知数列}{n a 的前n 项和为n S ，且满足322-=+n a S n n )(*N n ∈． 求数列}{n a 的通项公式 变式3. 已知数列{}a n 的前n 项和S n b n n =+()1，其中{}b n 是首项为1，公差为2的等差数列. 求数列{}a n 的通项公式； 变式4. 数列{}n a 的前n 项和为n S ，11a =，*12()n n a S n +=∈N ．求数列{}n a 的通项n a 变式5. 已知数列}{n a 的前n 项和为n S ，且满足322-=+n a S n n )(*N n ∈． 求数列}{n a 的通项公式； 变式6. 已知在正整数数列}{n a 中，前n 项和n S 满足2 )2(81+=n n a S （1）求证：}{n a 是等差数列 （2）若n b 3021 -=n a ，求}{n b 的前n 项 和的最小值

斐波那契数列的启示

Xxxxxxxxxxx大学 课程论文（2013-2014学年春季学期） 论文题目： 课程名称： 任课教师： 班级： 学号： 姓名：

浅谈斐波那契数列 摘要： 斐波那契数列，又称作黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21……这个数列从第三项开始，每一项都等于前两项之和。斐波那契数列的发明者，是意大利数学家列昂纳多?斐波那契（Leonardo Fibonacci）。本文主要就斐波那契数列的提出与特征进行简要分析，通过举例重点说明斐波那契数列在实际生活当中的表现与应用，进而得到启示。 关键词： 斐波那契数列; 特征; 应用 Research on Fibonacci sequence (Institute of Technology, China Agricultural University, FENG-Wei) Abstract: Fibonacci sequence, also known as the golden series, referring to such a sequence: 1,1,2,3,5,8,13,21…… this sequence beginning from the third term, each of which equal to the sum of the first two terms. The inventor of Fibonacci series was an Italian mathematician——Leonardo Fibonacci. This tractate focuses on the characteristics of Fibonacci sequence and has a brief analysis, as well as giving examples to analyze the performance and application of Fibonacci sequence in real life, and then get inspirations. Key words: Fibonacci sequence; Characteristics; Application

九类常见递推数列求通项公式方法

递推数列通项求解方法 类型一：1n n a pa q += +（1p ≠） 思路1（递推法）：()123()n n n n a pa q p pa q q p p pa q q q ---??=+=++=+++=?? ......121(1n p a q p p -=++++ (2) 1 1)11n n q q p a p p p --??+=+?+ ? --?? 。 思路2（构造法）：设()1n n a p a μμ++=+，即()1p q μ-=得1 q p μ= -，数列 {}n a μ+是以1a μ+为首项、p 为公比的等比数列，则1 111n n q q a a p p p -??+ =+ ?--??，即1111n n q q a a p p p -??=++ ? --?? 。 例1 已知数列{}n a 满足123n n a a -=+且11a =，求数列{}n a 的通项公式。 解：方法1（递推法）： ()123232(23)3222333n n n n a a a a ---??=+=++=+++=?? (1) 22 3(122n -=++++ (2) 11 332 )12232112n n n --+??+=+?+=- ? --? ?。 方法2（构造法）：设()12n n a a μμ++=+，即3μ=，∴数列{}3n a +是以134 a +=为首项、2为公比的等比数列，则113422n n n a -++=?=，即1 23n n a +=-。

1n n +思路1（递推法）： 123(1)(2)(1)(3)(2)(1)n n n n a a f n a f n f n a f n f n f n ---=+-=+-+-=+-+-+-= …1 11 ()n i a f n -==+∑。 思路2（叠加法）：1(1)n n a a f n --=-，依次类推有：12(2)n n a a f n ---=-、 23(3)n n a a f n ---=-、…、21(1)a a f -=，将各式叠加并整理得1 11 ()n n i a a f n -=-= ∑ ，即 1 11 ()n n i a a f n -==+ ∑ 。 例2 已知11a =，1n n a a n -=+，求n a 。 解：方法1（递推法）：123(1)(2)(1)n n n n a a n a n n a n n n ---=+=+-+=+-+-+= ......1[23a =+++ (1) (1)(2)(1)]2 n i n n n n n n =++-+-+= = ∑ 。 方法2（叠加法）：1n n a a n --=，依次类推有：121n n a a n ---=-、232n n a a n ---=-、…、 212a a -=，将各式叠加并整理得12 n n i a a n =-= ∑ ，12 1 (1)2 n n n i i n n a a n n ==+=+ = = ∑ ∑ 。

史上最全的数列通项公式的求法13种

最全的数列通项公式的求法 数列是高考中的重点内容之一，每年的高考题都会考察到，小题一般较易，大题一般较难。而作为给出数列的一种形式——通项公式，在求数列问题中尤其重要。本文给出了求数列通项公式的常用方法。 一、直接法 根据数列的特征，使用作差法等直接写出通项公式。 二、公式法 ①利用等差数列或等比数列的定义求通项 ②若已知数列的前n 项和n S 与n a 的关系，求数列{}n a 的通项n a 可用公式 ?? ?≥???????-=????????????????=-2 1 11n S S n S a n n n 求解. (注意：求完后一定要考虑合并通项) 例2．①已知数列{}n a 的前n 项和n S 满足1,)1(2≥-+=n a S n n n ．求数列{}n a 的通项公式. ②已知数列{}n a 的前n 项和n S 满足2 1n S n n =+-，求数列{}n a 的通项公式. ③ 已知等比数列{}n a 的首项11=a ，公比10<

高三数学 教案 斐波那契数列通项公式推导过程

斐波那契数列 斐波那契数列，又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。 定义 斐波那契数列指的是这样一个数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........ 自然中的斐波那契数列 这个数列从第3项开始，每一项都等于前两项之和。 斐波那契数列的定义者，是意大利数学家列昂纳多·斐波那契，生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点于阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。 通项公式 递推公式 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2) 显然这是一个线性递推数列。 通项公式

几类常见递推数列的解题方法

叠加、 叠乘、迭代递推、代数转化 ——几类常见递推数列的教学随笔 已知数列的递推关系式求数列的通项公式的方法大约分为两类：一类是根据前几项的特点归纳猜想出a n 的表达式，然后用数学归纳法证明；另一类是将已知递推关系，用代数法、迭代法、换元法，或是转化为基本数列（等差或等比）的方法求通项．第一类方法要求学生有一定的观察能力以及足够的结构经验，才能顺利完成，对学生要求高．第二类方法有一定的规律性，只需遵循其特有规律方可顺利求解．在教学中，我针对一些数列特有的规律总结了一些求递推数列的通项公式的解题方法． 一、叠加相消． 类型一：形如a 1+n ＝a n + f (n )， 其中f (n ) 为关于n 的多项式或指数形式（a n ）或可裂项成差的分式形式．——可移项后叠加相消． 例1：已知数列｛a n ｝,a 1＝0,n ∈N +，a 1+n ＝a n ＋（2n －1），求通项公式a n ． 解：∵a 1+n =a n ＋（2n －1） ∴a 1+n =a n ＋（2n －1） ∴a 2－a 1 =1 、a 3－a 2=3 、…… a n －a 1-n =2n －3 ∴a n = a 1＋(a 2－a 1)＋(a 3－a 2)＋…＋(a n －a 1-n )=0＋1＋3＋5＋…＋(2n －3) = 2 1 [1＋(2n －3)]( n －1)=( n －1)2 n ∈N + 练习1：⑴.已知数列｛a n ｝,a 1=1, n ∈N +，a 1+n =a n ＋3 n ， 求通项公式a n ． ⑵.已知数列｛a n ｝满足a 1＝3，)1(2 1 +=-+n n a a n n ，n ∈N +，求a n ． 二、叠乘相约． 类型二：形如)(1n f a a n n =+.其中f (n ) =p p c mn b mn )()(++ （p ≠0，m ≠0,b –c = km ,k ∈Z ）或 n n a a 1+=kn （k ≠0）或n n a a 1+= km n ( k ≠ 0, 0＜m 且m ≠ 1)． 例2：已知数列｛a n ｝, a 1=1，a n ＞0,( n ＋1) a 1+n 2 －n a n 2＋a 1+n a n =0，求a n ． 解：∵( n ＋1) a 1+n 2 －n a n 2＋a 1+n a n =0 ∴ [(n ＋1) a 1+n －na n ](a 1+n ＋a n )= 0 ∵ a n ＞0 ∴ a 1+n ＋a n ＞0 ∴ (n ＋1) a 1+n －na n =0 ∴1 1+=+n n a a n n ∴n n n n n n n a a a a a a a a a a n n n n n n n 112 12 31 2111 23 22 11 =???--?--?-=?????=----- 练习2：⑴已知数列｛a n ｝满足S n = 2 n a n ( n ∈N * ), S n 是{ a n }的前n 项和,a 2=1,求a n ．

详解由递推公式求斐波那契数列的通项公式

详解由递推公式求斐波那契数列的通项公式 武汉市黄陂区第四中学 蔡从江 斐波那契数列的递推公式是121==a a ，11-++=n n n a a a （2≥n 且N n ∈），那么它的通项公式是怎样的呢？不少同学经常问到这个问题。 下面详细解答用待定系数法构造过渡数列求其通项公式。 由递推公式11-++=n n n a a a ，可设)(11-++=+n n n n a a a a λμλ，比较得1=-λμ且1=μλ，即012=-+λλ，解得251±-= λ。若251+-=λ，则251+=μ；若251--=λ，则2 51-=μ。 先以2 51+-=λ，251+=μ求解， 此时)2)(2 15(21521511≥-++=-+-+n a a a a n n n n ， 所以)2()215()215()215(2151211≥+=-++=-+ -+n a a a a n n n n ， 即)2()2 15(2511≥++-=+n a a n n n ， 再另)2]()215([251)215( 11≥+--=+-++n x a x a n n n n 即n n n x x )2 15()215(215)215(1+=+-+++， 所以12 15215=-++x x 即55=x ， 所以 ])215(55[251)215(5511n n n n a a +--=+-++， )2]()2 15(551[)251()215(552111≥+--=+--++n a n n n ，

所以)2]()2 15(551[)251()215(552111≥+--=+--++n a n n n ， )2]()251()251[(5 1])215(551[)251()215(55112111≥--+=+--++=++-++n a n n n n n 所以)3]()251()251[(5 1≥--+=n a n n n ， 又121==a a 适合上式，故 *)]()251()251[(51N n a n n n ∈--+=， 同理可得251--=λ，2 51-=μ时，*)]()251()251[(51N n a n n n ∈--+=， 因此斐波那契数列的通项公式是 *)]()251()251[(51N n a n n n ∈--+=

数列通项公式求法大全(配练习及答案)

数列通项公式的几种求法 注：一道题中往往会同时用到几种方法求解，要学会灵活运用。 一、公式法 二、累加法 三、累乘法 四、构造法 五、倒数法 六、递推公式为n S 与n a 的关系式(或()n n S f a = （七）、对数变换法 （当通项公式中含幂指数时适用） （八）、迭代法 （九）、数学归纳法 已知数列的类型 一、公式法 *11(1)()n a a n d dn a d n N =+-=+-∈ 1 *11()n n n a a a q q n N q -== ?∈ 已知递推公式 二、累加法 )(1n f a a n n +=+ （1）()f n d = （2）()f n n = （3）()2n f n =

例 1 已知数列{} n a 满足1121 1n n a a n a +=++=，，求数列{}n a 的通项公式。 2n a n = 例 2 已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。（3 1.n n a n =+-） 三、累乘法 n n a n f a )(1=+ （1）()f n d = （2）()f n n =， 1 n n +，2n 例3 已知数列{}n a 满足112(1)53n n n a n a a +=+?=，，求数列{}n a 的通项公式。 （(1)1 2 32 5 !.n n n n a n --=???） 评注：本题解题的关键是把递推关系12(1)5n n n a n a +=+?转化为 1 2(1)5n n n a n a +=+，进而求出 13211221 n n n n a a a a a a a a a ---?????L ，即得数列{}n a 的通项公式。 例4 （20XX 年全国I 第15题，原题是填空题） 已知数列{}n a 满足112311 23(1)(2)n n a a a a a n a n -==++++-≥L ，，求{}n a 的通项公式。（! .2 n n a = ） 评注：本题解题的关键是把递推关系式1(1)(2)n n a n a n +=+≥转化为 1 1(2)n n a n n a +=+≥，进而求出 132122 n n n n a a a a a a a ---????L ，从而可得当2n n a ≥时，的表达式，最后再求出数列{}n a 的通项公式。

中学数学-1(斐波那契数列)

内蒙古自治区中小学教师教育技术水平（初级）试卷 （试卷科目：中学数学） 第一部分：基本知识题（本部分共8个题，每题2.5分，满分20分） 第1题 (单选题)教育技术的本质特征是（ C ）。 (2.5分) A．运用技术手段去优化教育、教学过程，以提高教育、教学的效果、效率和效益的教学实践B．本题答案中所给出的其它3个选项都不对 C．运用技术手段去优化教育、教学过程，以提高教育、教学的效果、效率和效益的理论和实践D．运用技术手段去优化教育、教学过程，以提高教育、教学的效果、效率和效益的理论研究 第2题 (单选题)关于教学评价中收集数据的工具与方法，下列说法中不正确的是（ D ）。 (2.5分) A．形成性练习是教学评价中经常使用的方法 B．结构化观察是教学评价中经常使用的方法 C．总结性测验是教学评价中经常使用的方法 D．在教学评价中无需使用态度量表 第3题 (单选题)课程结束时进行期末考试，考试依据课程标准来确定试题范围，采用纸笔测验试卷评分的方式。就这一评价（考试）的类型，以下选项中不准确的一项是（ B ）。 (2.5分) A．它是一种定量评价 B．它是诊断性评价 C．它是总结性评价 D．它是一种绝对评价 第4题 (单选题)将认知领域的教学目标分为了解（识记）、理解、运用、分析、综合、评价六个层次的美国心理学家是（ C ）。 (2.5分) A．加涅 B．布鲁纳 C．布卢姆 D．奥苏贝尔 第5题 (单选题)"知识积累的关键因素是刺激、反应以及两者之间的联系"，持这一观点的学习理论流派是（ D ）。 (2.5分) A．建构主义 B．认知主义 C．人本主义 D．行为主义 第6题 (单选题)根据您对教育技术及相关基础知识的理解，下例选项不正确的一项是（ B ）。 (2.5分) A．教学设计是运用系统方法分析教学问题和确定教学目标，建立解决教学问题的策略方案、试行解决方案、评价试行结果和对方案进行修改的过程 B．教育技术与信息技术的涵义是一样的，只是用不同的名词来表述而已 C．教育信息化是指在教育教学的各个领域中，积极开发充分应用信息技术和信息资源，以促进教育现代化，培养满足社会需求人才的过程 D．教育技术就是为了促进学习，对有关的学习过程和资源进行设计、开发、利用、管理和评价的理论与实践

数列递推公式的九种方法

求递推数列的通项公式的九种方法 利用递推数列求通项公式，在理论上和实践中均有较高的价值.自从二十世纪八十年代以来，这一直是全国高考和高中数学联赛的热点之一. 一、作差求和法 例1 在数列{}中，31 =a , ) 1(11++ =+n n a a n n ，求通项公式. 解：原递推式可化为：1 111 +- + =+n n a a n n 则, 2 11112 -+=a a 3 12123-+ =a a 4 13134-+ =a a ，……，n n a a n n 1111--+ =-逐项相加得：n a a n 111- +=. 故n a n 14- =. 二、作商求和法 例 2 设数列{}是首项为1的正项数列，且 0)1(12 2 1 =+-+++n n n n a a na a n （n=1,2,3…） ，则它的通项公式是=▁▁▁（2000年高考15题） 解：原递推式可化为： ) ]()1[(11n n n n a a na a n +-+++=0 ∵ n n a a ++1＞0， 1 1+=+n n a a n n 则 ,4 3,32,21342312===a a a a a a ……，n n a a n n 11 -= - 逐项相乘得： n a a n 1 1=，即=n 1. 三、换元法 例3 已知数列{}，其中9 13,3421 == a a ，且当n ≥3时， ) (3 1 211----=-n n n n a a a a ，求通项公式（1986年高考文科第八

题改编）. 解：设1 1 ---=n n n a a b ，原递推式可化为： } {,3 1 21n n n b b b --=是一个等比数列，9 1 3491312 1 =-= -=a a b ，公比为3 1.故n n n n b b )3 1 ()31(91)31(2211 ==?=---.故n n n a a )3 1 (1=--.由逐差法可得： n n a )3 1(2123-= . 例4已知数列{}，其中2,12 1 ==a a ，且当n ≥3时，122 1 =+---n n n a a a ，求通项公式。解 由122 1 =+---n n n a a a 得：1)()(2 1 1 =------n n n n a a a a ，令1 1 ---=n n n a a b ，则上式为12 1 =---n n b b ，因此是一个等差数列，1121=-=a a b ，公差为1.故n b n =.。 由于112312121-=-++-+-=+++--n n n n a a a a a a a b b b ΛΛ 又2 )1(12 1 -= +++-n n b b b n Λ 所以)1(2 1 1-= -n n a n ，即)2(2 12 +-= n n a n 四、积差相消法 例5设正数列，，…，，…满足2 -n n a a 2 1---n n a a = ) 2(≥n 且11 ==a a ，求的通项公式. 解 将递推式两边同除以2 1--n n a a 整理得：122 1 1=----n n n n a a a a 设= 1 -n n a a ，则0 11 a a b = =1，1 21=--n n b b ，故有 1 212=-b b ⑴122 3 =-b b ⑵ … … … …