下载文档原格式
斐波那契数列、黄金分割以及它们在C++语言中的应用一、概述1.1 斐波那契数列的定义与性质斐波那契数列是古典数学中最为常见的数列之一，它的定义如下： F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)，其中n为正整数。
斐波那契数列具有许多有趣的性质，例如任意两个相邻的斐波那契数都是互质的等等。
1.2 黄金分割的概念黄金分割是指一条线段在“分割”时，分割成两部分的比例恰好等于整体与较大部分的比例相同。
这个比例通常用希腊字母φ（phi）表示，其值约为1.618。
1.3 C++语言在数学计算中的应用C++作为一种广泛应用的编程语言，其在数学计算领域也有着重要的应用。
通过C++语言，我们可以实现对斐波那契数列和黄金分割的计算和应用。
二、斐波那契数列在C++中的实现2.1 递归方法在C++中，可以利用递归的方法来实现斐波那契数列的计算。
递归的代码如下所示：```cppint fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n - 1) + fibonacci(n - 2);}```2.2 迭代方法除了递归方法外，我们还可以使用迭代的方法来计算斐波那契数列。
迭代的代码如下所示：```cppint fibonacci(int n) {int a = 0, b = 1, c;if (n == 0) {return a;}for (int i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return b;}```三、黄金分割在C++中的应用3.1 黄金分割比例的计算在C++中，可以编写函数来计算黄金分割的比例。
下面是一个简单的示例代码：```cppdouble golden_ratio() {return (1 + sqrt(5)) / 2;}```3.2 黄金分割点的求解除了计算黄金分割的比例外，我们还可以通过黄金分割的比例来实现对线段的黄金分割点的求解。
斐波那契-黄⾦分割斐波那契数列普通递推F0=0,F1=1,F n=F n−1+F n−2快速倍增递推F2n=F n(2F n+1−F n)F2n=F n(F n+1+F n−1)F2n+1=F2n+1+F2n 矩阵递推1 1 1 0F n−1F n−2=F nF n−1通项公式及其推导令ϕ=1+√52,ˆϕ=1−√52∵F_n = \dfrac{1}{\sqrt{5}}(\phi^n-\hat\phi^n)=\lfloor \dfrac{\phi^i}{\sqrt{5}} + \dfrac{1}{2} \rfloor所以、斐波那契以指数形式增长1.母函数法$ \digamma(x)=\sum\limits_{\infin} F_nx n\ \digamma(x)=x2\digamma(x)+x\digamma(x)+x\ \digamma(x)=\dfrac{1-x-x2} $母函数进⾏展开，⾸先我们要知道⽜顿⼆项式定理、⽜顿⼴义⼆项式定理、⼆项式定理的推⼴⽜顿⼆项式定理(n \in N^{+})(x+y)^n = \sum\limits_{i=0}^{n} C_{n}^{i} x^{n-i}y^{i}**⼆项式定理推⼴⾄(n \in N) **(1+x)^n=\sum\limits_{i=0}^{\infin} C_{n}^{i} x^i~~~~(n>0)(1+x)^{-n} = \sum\limits_{i=0}^{\infin} C_{-n}^{i} x^i=\sum\limits_{i=0}^{\infin}(-1)^i C_{n+i-1}^{i} x^i⽜顿⼴义⼆项式定理(\alpha \in R)(x+y)^{\alpha}=\sum\limits_{i=0}^{\infin}\tbinom{\alpha}{i} x^{\alpha-i}y^k其中\tbinom{\alpha}{i}类似组合数\tbinom{\alpha}{i}=\dfrac{\alpha(\alpha-1)\cdots(\alpha-i+1)}{i!}特殊形式(1+x)^n = (1-x)^{-n} = \sum\limits_{i=0}^{\infin} C_{n}^{i}x^i推导开始：设~\digamma(x)=\frac{x}{1-x-x^2}=\frac{A}{1-\alpha x}+\frac{B}{1-\beta x} \\=\frac{A+B-x(A\beta+B\alpha)}{1-(\alpha+\beta)x+\alpha\beta x^2}\\ \left\{ \begin{matrix} A+B=0\\A\beta+B\alpha=-1\\ \alpha+\beta=1\\ \alpha\beta=-1 \end{matrix} \right. \Rightarrow \left\{ \begin{matrix} A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ \alpha=\phi\\ \beta=\hat\phi\end{matrix} \right.\\ \therefore \digamma(x)=\frac{1}{\sqrt{5}}(\frac{1}{1-\phi x}-\frac{1}{1-\hat\phi x})\\ \because\frac{1}{1-x}=\sum\limits_{n=0}^{\infin}x^n\\ \digamma(x)=\frac{1}{\sqrt{5}}\sum\limits_{n=0}^{\infin}(\phi^n-\hat\phi^n) x^n2.数列待定系数法类似于求解a_n = pa_{n-1}+q性质1.卡西尼性质F_{n-1}F_{n+1}-F_n^2=(-1)^n证：F_{n-1}F_{n+1}-F_n^2\\ =det \left( \left[ \begin{matrix} F_{n+1}~~F_{n}\\ F_{n}~~F_{n-1} \end{matrix} \right] \right) =det \left( \left[ \begin{matrix} 1~~~~1\\ 1~~~~0 \end{matrix} \right] \right)^n = \left( det \left( \left[ \begin{matrix} 1~~~~1\\ 1~~~~0 \end{matrix} \right] \right) \right)^n=(-1)^n2.附加性质F_{n+m}=F_m F_{n+1}+F_{m-1}F_{n}证：\because \left[ \begin{matrix} F_{n}~~~F_{n-1}\\ F_{n-1}~~~F_{n-2} \end{matrix} \right] = \left[ \begin{matrix} 1~~~~1\\ 1~~~~0 \end{matrix} \right]^{n-1}\\ \therefore \left[ \begin{matrix} F_{n+m}~~~F_{n+m-1}\\ F_{n+m-1}~~~F_{n+m-2} \end{matrix} \right] = \left[ \begin{matrix} 1~~~~1\\ 1~~~~0 \end{matrix} \right]^{n+m-1}=\left[ \begin{matrix} 1~~~~1\\ 1~~~~0\end{matrix} \right]^{n} \left[ \begin{matrix} 1~~~~1\\ 1~~~~0 \end{matrix} \right]^{m-1}= \left[ \begin{matrix} F_{n+1}~~~F_{n}\\ F_{n}~~~F_{n-1} \end{matrix} \right] \left[ \begin{matrix} F_{m}~~~F_{m-1}\\ F_{m-1}~~~F_{m-2} \end{matrix} \right]\\ \therefore F_{n+m}=F_{n+1}F_{m}+F_nF_{m-1}变形：F_{2n} = F_n(F_{n+1}+F_{n-1}) .3.整除与GCD性质\forall a,b \in N,F_a|F_b\Leftrightarrow a|b[][][](F_n,F_m) = F_{(n,m)}证：设~n>m~~则~(F_n,F_m)=(F_{n-km},F_m)\\ 设~r=n-km~,r<m~则~(F_r,F_m)=(F_r,F_{m-kr})\\ 这就类似于欧⼏⾥德算法的过程\\ \therefore~(F_n,F_m)=F_{(n,m)}4.求和公式奇数项：\sum\limits_{i=1}^{2n-1}[2\nmid i] F_{i}= F_{2n}偶数项：\sum\limits_{i=2}^{2n}[2\mid i] F_{i}= F_{2n+1}-1平⽅项：\sum\limits_{i=1}^{n}F_i^2=F_n F_{n+1}证：画图推⼴1.⼴义斐波那契数列当n<0时F_n=F_{n+2}-F_{n+1}F_{-n}=(-1)^{n-1}F_n2 .类斐波那契数列⼜称斐波那契—卢卡斯数列对于数列G,若G_0=a,G_1=b,且数列满⾜递推关系式，则称G是类斐波那契数列G_n =a F_{n-1} + b F_{n}⽤矩阵可证类斐波那契数列也有部分斐波那契数列的性质任意两个或两个以上斐波那契—卢卡斯数列之和或差仍然是斐波那契—卢卡斯数列3. Lucas数列与Fibonacci数列Lucas数列为a=2,b=1的类斐波那契数列，记为LL_n = (\dfrac{1+\sqrt{5}}{2})^n+(\dfrac{1-\sqrt{5}}{2})^n~~~~(n\ge 2)Lucas数列能够辅助写出看似很困难的等式2L_{n+m}=5 F_n F_m+L_n L_m\\ 2F_{n+m}=5 F_n L_m+L_n F_m\\ L_{2n}=L_n^2-2(-1)^n\\ F_{2n}=F_n L_n\\ L_n=F_{n+1}+F_{n-1}4.编码(齐肯多夫定理)齐肯多夫表述法表⽰任何正整数都可以表⽰成若⼲个不连续的斐波那契数之和证：若~m~为斐波那契数,成⽴\\ 否则考虑最⼤~n1~满⾜~F_{n1}< m<F_{n1+1}\\ 继续考虑最⼤~n2~满⾜~F_{n2} < m-F_{n1}<F_{n2+1}\\ 反证：\\ 若~F_{n1}~和~F_{n2}~为连续斐波那契数\\ 则~F_{n1+1}<m~与~F_{n1+1}>m~⽭盾模意义下的循环对于任意整数n , 数列为F_i~(mod~n)周期数列. ⽪萨诺周期\pi(n)记为该数列的周期.例如，模3的斐波那契数列前若⼲项为:0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0\cdots\therefore \pi(3) = 8.性质：1.~~\pi(n)\le 6 n且只有满⾜n=2*5^k的形式时才取得到等号2.~~\forall a,b\in N~且~(a,b)=1，\pi(a)\pi(b)=\pi(ab)Loading [MathJax]/jax/element/mml/optable/MathOperators.js。
斐波那契数列的黄金分割比稿子一嘿，朋友们！今天咱们来聊聊那个超神奇的斐波那契数列的黄金分割比！你知道吗？斐波那契数列就像是一串藏着无数秘密的数字密码。
从 0、1 开始，后面每个数都是前两个数的和，像 0、1、1、2、3、5、8、13……一直这样下去。
而这个数列里还藏着一个超级迷人的黄金分割比。
当你用数列里后面的数除以前面的数，比如2÷1、3÷2、5÷3、8÷5……你会发现，算出来的结果越来越接近一个神奇的数字，大约是 1.618 。
这 1.618 可不得了，它就像大自然的魔法数字一样。
花朵的花瓣数量、鹦鹉螺的壳、人体的比例，好多好多地方都能看到它的影子。
比如说，一朵漂亮的玫瑰花，它的花瓣数量可能就遵循着斐波那契数列的规律。
还有啊，我们觉得一个人长得好看，身材比例协调，说不定也是因为接近了这个黄金分割比呢。
是不是觉得很神奇？就好像大自然有一双看不见的巧手，按照这个比例来创造出美丽和和谐。
反正我每次想到这个，都觉得世界真是太奇妙啦，一个简单的数列居然藏着这么大的秘密！好啦，今天关于斐波那契数列的黄金分割比就先聊到这儿，咱们下次再见咯！稿子二哈喽呀，亲爱的小伙伴们！今天咱们要一起走进斐波那契数列的黄金分割比这个神秘又有趣的世界！斐波那契数列，听起来是不是有点高大上？但其实理解起来也不难啦。
就像搭积木一样，从 0 和 1 开始，后面的数字都是前面两个数字相加。
然后呢，在这个数列里就出现了黄金分割比这个神奇的家伙。
咱们不停地用后面的数字去除以前面的数字，你就会发现，越往后，得数越接近 1.618 。
这个 1.618 可不简单哟！它好像是宇宙的美学密码。
你看那些艺术作品，很多构图都暗合着这个比例，让人看着就觉得特别舒服、特别美。
还有建筑呢，有些著名的建筑的比例也和黄金分割比有关系，站在那里，就是一种视觉的享受。
而且哦，在投资理财里，也有人用这个黄金分割比来找买卖的时机。
斐波那契数列斐波那契数列斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1960年代起出版了《斐波纳契数列》季刊，专门刊载这方面的研究成果。
定义斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34……这个数列从第三项开始，每一项都等于前两项之和。
斐波那契数列的发明者，是意大利数学家列昂纳多〃斐波那契（Leonardo Fibonacci），自然中的斐波那契数列生于公元1170年，卒于1240年，籍贯是比萨。
他被人称作“比萨的列昂纳多”。
1202年，他撰写了《珠算原理》（Liber Abacci）一书。
他是第一个研究了印度和阿拉伯数学理论的欧洲人。
他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。
他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。
通项公式递推公式斐波那契数列：1、1、2、3、5、8、13、21、……如果设F(n）为该数列的第n项（n∈N+）。
那么这句话可以写成如下形式：F(1) = 1，F(2)=1，F(n)=F(n-1)+F(n-2) (n≥3)，显然这是一个线性递推数列。
通项公式斐波那契数列通项公式（见上图）（又叫“比内公式”，是用无理数表示有理数的一个范例。
）注：此时a1=1，a2=1，an=a(n-1)+a(n-2)（n>=3,n∈N*）通项公式的推导方法一：利用特征方程（线性代数解法）线性递推数列的特征方程为：X^2=X+1解得X1=(1+√5)/2,，X2=(1-√5)/2。
则F(n)=C1*X1^n + C2*X2^n。
第八讲 黄金分割与斐波那契数列一、 黄金分割1. 黄金分割的概念把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。
其比值是（√5-1）：2，取其小数点后三位的近似值是0.618。
由于按此比例设计的造型十分美丽柔和，因此称为黄金分割，也称为中外比。
这是一个十分有趣的数字。
德国天文学家开普勒（J.Kepler ）曾说“几何学有两大宝藏，其一为毕氏定理，其二为将一线段分成外内比。
前者如黄金，后者如珍珠。
”所谓将一线段分成“中外比（或称中末比或外内比）”，这是欧几里得在《几何原本》（公元前三世纪前后）里的说法：A straight line is said to have been cut in extreme and mean radio when, as the whole line is to the greater segment, so is the greater to the less.分一线段为二线段，当整体线段比大线段等于大线段比小线段时，则称此线段被分为中外比。
关于黄金分割的历史，可以追溯到公元前6世纪古希腊的毕达哥拉斯学派，他们已经研究过正五边形和正十边形的作图，因此现代数学家们推断当时毕达哥拉斯学派已经触及甚至掌握了黄金分割。
公元前4世纪，古希腊数学家欧多克索斯第一个系统研究了这一问题，并建立起比例理论。
而《几何原本》是吸收了欧多克索斯的研究成果，进一步系统论述了黄金分割，成为最早的有关黄金分割的论著。
中世纪后，黄金分割被披上神秘的外衣，意大利数学帕乔利称之为神圣比例，并专门为此著书立说。
德国天文学家开普勒称之为神圣分割。
当时，人们都还是称之为“中外比”，直到19世纪初，黄金分割这个名称才出现。
黄金分割在文艺复兴前后，经过阿拉伯人传入欧洲，受到了欧洲人的欢迎，他们称之为“金法”，17世纪欧洲的一位数学家，甚至称它为“各种算法中最可宝贵的算法”。
这种算法在印度称之为“三率法”或“三数法则”，也就是我们常说的比例方法。
