数学之美|斐波那契数列与黄金分割

系列文章目录

趣味算法（第二版）读书笔记： day1: 序章|学习的方法和目标. day2:算法之美|打开算法之门与算法复杂性 day3.算法之美|指数型函数对算法的影响实际应用 day4.数学之美|斐波那契数列与黄金分割 day5.算法实践|贪心算法基础 day6.算法实践|最优装载 day7.算法实践|背包问题

文章目录

• 系列文章目录
• 课程导学
• 一、斐波那契的兔子
  • 1.1 自然中的数列
  • 1.2 经典的兔子问题
    • 1.2.1 问题的展开：
    • 1.2.1 问题的推导过程：
    • 1.2.3 问题转化为数学模型求解
    • 1.2.4 算法设计及优化
• 二、自然界中的斐波那契数列。
• 三、黄金分割在设计中的运用
• 总结

课程导学

自己的笔记里增加了一部分设计思维需要用到的黄金分割，以及对应的数学扩展读物：

1. 从斐波那契的兔子开始引入，讲解递归算法的优化以及与黄金分割的关联。
2. 自然界中的斐波那契数列。
3. 黄金分割在艺术与设计中的应用。

在这里插入图片描述

tips：练拳不练功,到老一场空。算法的基础是数学，兴趣是最好的老师。

一、斐波那契的兔子

建议扩展阅读：

在这里插入图片描述

1.1 自然中的数列

比萨的莱昂纳多出生于1170年左右，恰好在1173年——著名的斜塔开始建造之前。人们习惯喊他斐波那契，这是斐那乌斯·波那契（Filius Bonacci，意为“波那契的儿子”）的简称。他的父亲不仅从商，还是一位海关官员。斐波那契年轻时曾与父亲在地中海周边旅行，其间学到了来自印度的“阿拉伯数字”（参阅此处），还从遇到的商人那里了解到了各种形式的算术。 1202年，他的重要著作《计算之书》问世，正是这本书将“阿拉伯数字”引入了欧洲。不仅如此，该书还讲述了一个兔子的故事，这个故事普及了一串非常有意思的数列。

1.2 经典的兔子问题

tips:现实往往比题目更复杂，这里没有展开兔子的生命周期，以及天敌捕杀，疾病等外部干预系数，而且默认兔子是一公一母，没有其他分支条件判断，用理想化的假设进行数学推导，很多有趣的发现和突破就是从一个有趣的问题开始：

在这里插入图片描述

1.2.1 问题的展开：

假设田野里有一对小兔子。第一个月，它们还太小，不能生育，但到第二个月末，它们长大了，并生出了一对小兔子。它们的后代在两个月后继续繁衍。每对刚出生的小兔子都要成长两个月，才能生育下一代，在这之后每个月都能生一对小兔子。因此，这个兔子部落逐渐壮大起来。斐波那契的问题如下：这样生下去，每个月初有几对兔子？

在这里插入图片描述

1.2.1 问题的推导过程：

依次类推，可以列出下表：

在这里插入图片描述

由上表可知，从养一对小兔子开始，一年以后最多可以繁殖233对兔子。在商人眼里，养一对小兔子一年以后最多可以繁殖出466只兔子。但在老子等哲人眼里，兔子的生育必定是阴阳成对的；而在意大利数学家斐波那契眼里，成年兔子的对数则形成了一个完整的“兔子”数列：

在这里插入图片描述

这是斐波那契于1202年发现的一个神奇数列，又称斐波那契数列。这个“兔子”数列被斐波纳契以递归的方法加以定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。其主要特征至少有四：

一、是从数列的第2项开始，每项数值都是前两项之和。

在这里插入图片描述

二、是从数列的第9项开始，相邻两项之比接近黄金分割数，并且互为倒数，尤其是从第11项开始，前后相邻两项比值的小数部分均为0.6180……无限接近于黄金分割无理数。

在这里插入图片描述

三、是偶数项的平方比前后两项的乘积少1，而奇数项的平方比前后两项的乘积多1。比如，第4项3的平方比2和5的乘积少1，第5项5的平方比3和8的乘积多1。

在这里插入图片描述

四、是数列第5n项和第12n项（n均为正整数）的值与本项序列号具有相似性，即可以整除，比如第5项5÷5=1，第25项75025÷25=3001，第12项144÷12=12，余数均为零。

在这里插入图片描述

假定我们以递归的方法重新定义“兔子”数列的前两项：F0=2，F1=5。这个问题就变成了：兔子在出生两个月后，就有繁殖能力，一对成年而有繁殖力的兔子每个月能生出一对小兔子来。假设一年以后所有兔子都不死，那么5对小兔子和2对成年兔子一年以后可以繁殖多少对兔子？

依次类推，可知5对小兔子和2对成年兔子一年以后可以繁殖1631对兔子。

在这里插入图片描述

从上表三个“兔子”数列可以发现：无论前两项取什么值，只要从数列的第2项开始，每项数值都是前两项之和；那么，从数列的第9项开始，相邻两项之比接近黄金分割数，并且互为倒数。

1.2.3 问题转化为数学模型求解

递归树：

在这里插入图片描述

通项式：

在这里插入图片描述

1.2.4 算法设计及优化

斐波那契数列中的每一项（开头的两项除外）是前两项之和，如果记录前两项的值，则只需要一次加法运算就可以得到当前项的值，时间复杂度会不会更低一些呢？不妨用数组试试看，见算法1-9。

//算法1-9 
int Fib2(int n){  
    int *F=new int[n+1];//定义一个长度为n+1的数组，空间尚未使用
    F[1]=1；
    F[2]=1;
    for(int i=3;i<=n;i++)
        F[i]=F[i-1]+F[i-2];
    return F[n];
}

书中的最优算法，使用了几个辅助变量进行迭代，时间复杂度为О(n)，但空间复杂度降到了О(1)。

/算法1-10 
int Fib3(int n){
    if(n==1||n==2)   
         return 1;
    int s1=1; //用s1和s2记录前面的两项
    int s2=1;
    for(int i=3;i<=n;i++){
         int tmp=s1+s2;
         s1=s2;
         s2=tmp;
    }
    return s2;
}

参考文献： 作者：MiaLing007 《2018-04-15 斐波那契数列（兔子繁殖数列》 来源：简书 作者：齐斯·德福林 (Keith Devlin) 《斐波那契的兔子》 来源：豆瓣

在这里插入图片描述

二、自然界中的斐波那契数列。

我们的星系——银河系，是一种棒旋星系，它属于螺旋星系。银河系包含四条主旋臂，每条旋臂分开大约12度。银河系的形状和黄金螺旋完全一样，我们很容易在宇宙中任何螺旋星系上画出黄金矩形。 台风就像螺旋星系和一些动物外壳一样，台风往往完美地诠释了黄金螺旋。 这种模式一直延伸到植物的叶脉和动物的静脉、晶体以及其他化合物中。令人困惑的是，大自然都是用同样的数字来创造出这些东西，但它带来的问题远远多于它所能回答的问题。 为什么这么多的东西按照黄金比例组合在一起？这能表明宇宙是被设计的吗？其中一些可能确实是巧合的结果，但其他事件太过精确，或许不是巧合，宇宙中可能有更加深刻的规律有待我们发现。

在这里插入图片描述

现在工程技术很多都来源于仿生学，神奇的自然在演化的过程中将斐波那契数列于黄金分割隐藏在了神奇的造物中，数学就是解开这个谜底的重要的钥匙，下面是设计模式中对黄金分割的应用。

三、黄金分割在设计中的运用

tips：作为一名以用户为中心的产品，必须了解，用户的主体是人，而人是一种视觉动物，好的具有美感的设计能够帮你走入客户的内心世界。

在这里插入图片描述

数学计算可能看起来很枯燥而费时，因此，如果值得付出努力，可能会出现一个问题。让我们看看黄金分割率可以为设计带来什么。

在这里插入图片描述

均衡的内容

设计师经常面临这样的情况：一个产品需要包含大量的各种内容，而其中的每一部分都是至关重要的，并且不能被替换。为了将所有成分结合在一个令人愉快的成分中，可以应用黄金比例。使用1:1.618的比例将布局划分为不同的部分，并根据其重要性将内容放在各个部分中。这样的内容组合足以让用户感知，并且有助于组织所有组件。

在这里插入图片描述

有效的视觉层次

说到内容组织，我们不能忘记视觉层次结构。正如我们在之前的文章中提到的，它是一种有效构建内容组件的技术。结合这两种技术的原理，设计师可以最大限度地构建强大的设计组合。

强大的排版水平

为了创建高效的排版，设计师需要将复制内容划分为不同的级别。它们通常包括各种副本，包括标题、副标题、正文副本等。应用黄金分割率的专业人士可以快速定义印刷级别之间的适当比例，例如，您可以为标题选择一定的大小，然后除以它1.618。结果将显示最适合子标题的大小。

在这里插入图片描述

令人满意的第一印象

当用户第一次尝试使用产品时，他们会扫描用户界面以了解他们是否喜欢。被称为内脏反应的心理学原则表明，人们在几秒钟内看到某些东西时，决定他们是否喜欢某事。这种反应比我们的意识更快，所以我们甚至都没有意识到。这就是为什么确保产品的第一印象令人满意的重要性。使用黄金比例创建的设计对用户的思维和视觉感知产生积极影响，并且从产品的第一眼看就起作用。 tips：心理学中的首因效用，就像我看到俄剧《叶卡捷琳娜》的女演员时的感觉，给用户一种震撼的惊艳的效果。

在这里插入图片描述

适当的空白区域

白色空间是设计构成中元素之间的区域。设计师总是需要关心UI中的空白量，因为组合的统一性高度依赖于它。黄金比例可以使间距过程更容易，更快捷。应用黄金比例，您将能够定义适合设计的正确空白区域。

在这里插入图片描述

设计呈现组件的自然平衡不容忽视，结构良好的布局是功能强大的UI的核心部分之一。黄金比例将和谐融入设计中，使产品为用户带来愉悦。不要害怕数学公式，它看起来并没有那么困难。更重要的是，黄金分割率可以帮助创建用户友好的数字产品，将实用性和美学结合起来。

总结

提示：今天主要是对书中的数学例子进行拓展。

下一篇：day5.算法实践|贪心算法基础