go语言斐波那契数列 go语言实现斐波那契

go语言 使用递归与循环两种方式计算斐波那契数列

给定一个正整数n计算出对应斐波那契数列对应的值

说明:

用mackbookpro i7 2.7GHZ笔记本进行测试，结果如下:

备注: 当n=80时，由于测试等待时间过长，强制中断了执行。

从测试结果看出，当n逐渐增大，递归方式计算斐波拉契数列的时间复杂性急剧增加。当n值较大时可以考虑用循环方式代替。

类似的方式也可以用于，求阶乘、遍历目录、汉诺塔等问题的解决。在后期的文章中，我将这些内容进行补充，敬请期待，谢谢。

相关问答

Q1: 用汇编语言编写斐多纳契数列的前n项和，至少加100位，

仅供参考吧

ASSUME CS:CODE,DS:DATA

DATA SEGMENT

BUFF DB 10

DB ?

DB 10 DUP(?)

RESULT DW ?

RESULT_SHOW DB 10 DUP(?)

DATA ENDS

CODE SEGMENT

START:

MOV AX,DATA

MOV DS,AX

LEA DX,BUFF

MOV AH,0AH

INT 21H

MOV DI,0

L0: ;统计一共有多少个数字组成

CMP BYTE PTR DS:[DI+2],0DH

JZ GO

INC DI

JMP L0

GO: ;计算第n个斐波那契数,把数字字符串转换为十进制数

MOV BL,10

MOV AX,1

MOV SI,DI ;为后面判断输入的是不是只输入一个数有用

MOV CX,DI

L2: PUSH AX

SUB BYTE PTR DS:[DI+1],30H

MUL BYTE PTR DS:[DI+1]

ADD RESULT,AX

POP AX

MUL BL

DEC DI

LOOP L2

;分两种情况：1.输入的是1；2.输入的不是1

CMP SI,1

JNZ L7

CMP BYTE PTR RESULT,1

JNZ L7

MOV AX,RESULT

JZ L4

L7: MOV AX,1

MOV BX,0

MOV CX,RESULT

DEC CX

L3: ;第n个斐波那契数存放到AX中

PUSH AX

ADD AX,BX

POP BX

LOOP L3

L4:

;显示这个斐波那契数

MOV DX,0

LEA SI,RESULT_SHOW

MOV DI,0 ;利用DI来累计一共有多少个数字

L5:

MOV CX,10

CALL DIVDW

ADD CL,30H

MOV DS:[SI],CL

CMP AX,0

JZ L6

INC SI

INC DI

JMP L5

L6:

MOV DL,DS:[SI]

MOV AH,2

INT 21H

CMP DI,0

JZ OK

DEC SI

DEC DI

JMP L6

OK:

MOV AX,4C00H

INT 21H

;参数： (AX)=DWORD型低16位数据

; (DX)=DWORD型高16位数据

; (CX)=除数

;返回： (DX)=结果的高16位，(AX)=结果的低16位

; (CX)=余数

;32位除16位，可以防止溢出！

DIVDW: ;子程序定义开始,功能是分离各个数字出来

PUSH AX

MOV AX,DX

MOV DX,0

DIV CX

MOV BX,AX

POP AX

DIV CX

MOV CX,DX

MOV DX,BX

RET ;子程序定义结束

CODE ENDS

END START

Q2: Fibonacci数列高效解法大全及时间复杂度分析　连载【5】

……续上回 Fibonacci数列高效解法大全及时间复杂度分析　连载【4】

来看profile的记录分析，看时间具体用在哪个部分了

一看，绝大部分时间耗在两句results上了

看来主要都用来大整数运算了

下面来试一下

把这程序里两句“results = ”后面的大数运算注释掉，换成1。也就是两句都成“results = 1”

再运行计时看看

Total time: 0.000753秒

很惊人，去掉大数运算后，运行时间缩短成了原用时的1%。也就是99%时间消耗在Python内置的大数运算上了

下面试下用号称地球上最好的大数运算库替换掉Python内置的大数运算

9.  应用GMP库

全称是GNU Multiple Precision Arithmetic Library，即GNU高精度算术运算库，这是一个C写成的高效大数运算库

gmpy2是Python下对GMP库的封装

安装很简单，在操作系统下打命令pip install gmpy2，就安装好了

应用到程序也很简单

把上面的二分迭代解法程序开头添加一行

再把程序里

改成

就可以了

运行看一下用时

Total time: 0.00689297秒

是原用Python内置大数运算用时的9%

效果显著。可见Python内置大数运算效率确实不怎么样

相关大整数乘法高效算法的介绍可参见这篇《 【算法】大数乘法问题及其高效算法 》

极大整数乘法的时间复杂度低至近似O(n*log n)

前面二分解法本身时间复杂度是O(log n)

现在把大数因素考虑进去。大数时间复杂度的n可以用二进制位数表示

第n项斐波那契数的二进制位数k跟n是线性关系，n*10，那位数k也是*10

现在把极大整数乘法时间复杂度代入，O(n*log n)*O(log n)=O(n*(log n)^2)

也就是在大数情况下二分解法的时间复杂度为O(n*(log n)^2)

可以看这篇《 为什么算法渐进复杂度中对数的底数总为2 》解释

10.  矩阵解法

斐波那契数列和矩阵的关系推导我看到GoCalf Blog里写的一段非常清晰，特在此引用

这解法就是求矩阵的n-1次幂。矩阵幂运算也能根据下面公式迭代二分加速

就是所谓的矩阵快速幂

Python里库很丰富，大名鼎鼎的numpy就是一个有关矩阵的库。这库是有优化的，算矩阵幂就不用个人再写什么矩阵快速幂函数了

用numpy库就能很简单的写出来

因为numpy没有大数支持，大数运算还是要用GMP库

同上测用时

Total time: 0.042466秒

这幂运算是二分加速的，时间复杂度为O(log n)

对于固定阶矩阵相乘，乘的次数是个常数，也就是O(1)。虽然这个常数比较大^_*

代入大数时间复杂度，总体复杂度也是O(n*(log n)^2)

这儿来解释下为何矩阵快速幂比二分递归解法时间常数大

我们再来仔细看看斐波那契数列的矩阵形式：

会发现 z 和 y 必然相等，z 没必要再计算一遍。

t = x - y，因此 t 也没必要再计算一遍。

只需要计算矩阵第一列的那两个元素即可：

矩阵快速幂中两个矩阵相乘实际可分解为8次两个大整数乘法，而二分递归中只需要3次两个大整数乘法。所以二分递归时间常数小。

未完待续……

Fibonacci数列高效解法大全及时间复杂度分析　连载【6】

Q3: 有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法.

这个问题本质上是斐波那契数列，假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级,f(2)=2。如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-1级台阶，有f(n-1)种跳法，假如第一次条2级台阶，剩下n-2级台阶，有f(n-2)种跳法。这就表示f(n)=f(n-1)+f(n-2)

public class Nstep {

public static int go(int n) {

}

Q4: go的错误码处理

目录结构: 都在src的目录下

主要是web.go 和http.go 的交互，fbn.go做了一个简单的斐波那契数列

先看web.go：

```

package main //入口

import (

    "exdefer/filelistenserver/fileting"

    "log"

    "net/http"

    "os"

)

type appHandler func(writer http.ResponseWriter, request *http.Request) error   //定义一个实现错误的方法

func errW(handler appHandler) func(writer http.ResponseWriter, request *http.Request) { //实现上面的方法

    return func(writer http.ResponseWriter, request *http.Request) {

        err := handler(writer, request) //http 的response 和request   设置一个错误的返回值

        if err != nil { // 判断一下

            log.Print("Print array ", err.Error(), "\n") //打印log

            code := http.StatusOK //code 默认设置成200

            switch { //switch选择

            case os.IsNotExist(err): //如果输入的这个文件不存在

                code = http.StatusNotFound //404

            case os.IsPermission(err): //如果权限不够

                code = http.StatusForbidden //403

            default: //否则的话

                code = http.StatusInternalServerError //500

            }

            http.Error(writer, http.StatusText(code), code) //输出 第一个参数 是response,第二个是 错误描述，返回的状态码 在swoole里面是$response-end("") /状态码是$response-status("");大同小异

        }

    }

}

func main() {

//第一个值是你要走的url目录 swoole里面通过document_root 进行设置

    http.HandleFunc("/list/", errW(fileting.Handlist)) //调用的http.go的包

    err := http.ListenAndServe(":8888", nil) //监听的端口 第二个值一般给nil

    if err != nil {

        panic(err)

    }

}

```

http.go

```

package fileting //声明包

import (

    "io/ioutil"

    "net/http"

    "os"

)

func Handlist(writer http.ResponseWriter, request *http.Request) error { //方法 返回一个error

    path := request.URL.Path[len("/list/"):] //切片 path访问为localhost:8888/list/xxx.txt 中的xxx.txt

    file, err := os.Open(path) //分开写了，两个返回值

    if err != nil {

        //http.Error(writer, err.Error(), http.StatusInternalServerError)

        return err //直接return err

    }

    defer file.Close() //defer 一下  open完要记得

    all, err := ioutil.ReadAll(file) //对文件的读取

    if err != nil {

        //panic(err)

        return err

    }

    writer.Write(all) //reponse 里面的write 类似swoole $response-end()

    return nil //如果没有错误返回nil

}

```

演示一下:

今日的学习，结束

Q5: 斐波那契数列

下面有相关解答:

其实,人们对数学与音乐之间联系的研究和认识可以说源远流长. 这最早可以追溯到公元前六世纪,当时毕达哥拉斯学派用比率将数学与音乐联系起来[1]. 他们不仅认识到所拨琴弦产生的声音与琴弦的长度有着密切的关系,从而发现了和声与整数之间的关系,而且还发现谐声是由长度成整数比的同样绷紧的弦发出的. 于是,毕达哥拉斯音阶(thePythagorean Scale) 和调音理论诞生了 , 而且在西方音乐界占据了统治地位. 虽然托勒密(C. Ptolemy ,约100 —165 年) 对毕达哥拉斯音阶的缺点进行了改造 ,得出了较为理想的纯律音阶(the Just Scale) 及相应的调音理论 ,但是毕达哥拉斯音阶和调音理论的这种统治地位直到十二平均律音阶(the temperedScale) 及相应的调音理论出现才被彻底动摇. 在我国,最早产生的完备的律学理论是三分损益律, 时间大约在春秋中期《管子.地员篇》和《吕氏春秋.音律篇》中分别有述;明代朱载 (1536 - 1610) 在其音乐著作《律学新说》对十二平均律的计算方法作了概述,在《律吕精义 ?内篇》中对十二平均律理论作了论述,并把十二平均律计算的十分精确, 与当今的十二平均律完全相同, 这在世界上属于首次.由此可见,在古代,音乐的发展就与数学紧密地联系在了一起. 从那时起到现在, 随着数学和音乐的不断发展,人们对它们之间关系的理解和认识也在不断地加深.感觉的音乐中处处闪现着理性的数学.乐谱的书写离不开数学.

看一下乐器之王 ———钢琴的键盘吧,其上也恰好与斐波那契数列有关. 我们知道在钢琴的键盘上,从一个 C 键到下一个 C 键就是音乐中的一个八度音程(如图1) . 其中共包括13 个键,有8 个白键和5 个黑键 ,而 5 个黑键分成 2 组 ,一组有 2 个黑键 ,一组有 3 个黑键.2、3、5、8、13 恰好就是著名的斐波那契数列中的前几个数.

如果说斐波那契数在钢琴键上的出现是一种巧合, 那么等比数列在音乐中的出现就决非偶然了: 1、2、3、4、5、6、7、i等音阶就是利用等比数列规定的. 再来看图1,显然这个八度音程被黑键和白键分成了12个半音,并且我们知道下一个 C键发出乐音的振动次数(即频率) 是第一个 C 键振动次数的 2倍,因为用2 来分割,所以这个划分是按照等比数列而作出的. 我们容易求出分割比 x ,显然 x 满足 x12= 2 ,解这个方程可得 x 是个无理数 , 大约是 1106.于是我们说某个半音的音高是那个音的音高的1106 倍 ,而全音的音高是那个音的音高 11062 倍. 实际上,在吉它中也存在着同样的等比数列[3].

音乐中的数学变换.

数学中存在着平移变换,音乐中是否也存在着平移变换呢 ?我们可以通过两个音乐小节[2]来寻找答案. 显然可以把第一个小节中的音符平移到第二个小节中去,就出现了音乐中的平移, 这实际上就是音乐中的反复. 把两个音节移到直角坐标系中,那么就表现为图 3. 显然,这正是数学中的平移. 我们知道作曲者创作音乐作品的目的在于想淋漓尽致地抒发自己内心情感,可是内心情感的抒发是通过整个乐曲来表达的,并在主题处得到升华,而音乐的主题有时正是以某种形式的反复出现的. 比如, 图 4 就是西方乐曲 When the Saints GoMarching In 的主题[2] ,显然 ,这首乐曲的主题就可以看作是通过平移得到的.

如果我们把五线谱中的一条适当的横线作为时间轴(横轴 x) ,与时间轴垂直的直线作为音高轴(纵轴y) ,那么我们就在五线谱中建立了时间 - 音高的平面直角坐标系. 于是, 图 4 中一系列的反复或者平移,就可以用函数近似地表示出来[2] , 如图 5 所示,其中 x 是时间, y 是音高. 当然我们也可以在时间音高的平面直角坐标系中用函数把图2中的两个音节近似地表示出来.

在这里我们需要提及十九世纪的一位著名的数学家,他就是约瑟夫.傅里叶 (Joseph Fourier) ,正是他的努力使人们对乐声性质的认识达到了顶峰. 他证明了所有的乐声, 不管是器乐还是声乐, 都可以用数学式来表达和描述,而且证明了这些数学式是简单的周期正弦函数的和[1].

音乐中不仅仅只出现平移变换,可能会出现其他的变换及其组合,比如反射变换等等. 图6 的两个音节就是音乐中的反射变换[2]. 如果我们仍从数学的角度来考虑,把这些音符放进坐标系中, 那么它在数学中的表现就是我们常见的反射变换,如图 7所示. 同样我们也可以在时间 - 音高直角坐标系中把这两个音节用函数近似地表示出来.

通过以上分析可知,一首乐曲就有可能是对一些基本曲段进行各种数学变换的结果.

大自然音乐中的数学.

大自然中的音乐与数学的联系更加神奇,通常不为大家所知. 例如[2] , 蟋蟀鸣叫可以说是大自然之音乐,殊不知蟋蟀鸣叫的频率与气温有着很大的关系,我们可以用一个一次函数来表示:C = 4 t – 160。其中 C代表蟋蟀每分钟叫的次数, t 代表温度.按照这一公式,我们只要知道蟋蟀每分钟叫的次数,不用温度计就可以知道天气的温度了!

理性的数学中也存在着感性的音乐.

由一段三角函数图像出发,我们只要对它进行适当的分段,形成适当的小节, 并在曲线上选取适当的点作为音符的位置所在,那么就可以作出一节节的乐曲. 由此可见,我们不仅能像匈牙利作曲家贝拉 .巴托克那样利用黄金分割来作曲,而且也可以从纯粹的函数图像出发来作曲. 这正是数学家约瑟夫.傅里叶的后继工作,也是其工作的逆过程. 其中最典型的代表人物就是20 世纪20 年代的哥伦比亚大学的数学和音乐教授约瑟夫 .希林格(JosephSchillinger) ,他曾经把纽约时报的一条起伏不定的商务曲线描述在坐标纸上,然后把这条曲线的各个基本段按照适当的、和谐的比例和间隔转变为乐曲,最后在乐器上进行演奏, 结果发现这竟然是一首曲调优美、与巴赫的音乐作品极为相似的乐曲[2] !这位教授甚至认为,根据一套准则,所有的音乐杰作都可以转变为数学公式. 他的学生乔治 .格什温(George Gershwin) 更是推陈出新, 创建了一套用数学作曲的系统, 据说著名歌剧《波吉与贝丝》(Porgy and Bess) 就是他使用这样的一套系统创作的.

因而我们说, 音乐中出现数学、数学中存在音乐并不是一种偶然,而是数学和音乐融和贯通于一体的一种体现. 我们知道音乐通过演奏出一串串音符而把人的喜怒哀乐或对大自然、人生的态度等表现出来,即音乐抒发人们的情感, 是对人们自己内心世界的反映和对客观世界的感触,因而它是用来描述客观世界的,只不过是以一种感性的或者说是更具有个人主体色彩的方式来进行. 而数学是以一种理性的、抽象的方式来描述世界,使人类对世界有一个客观的、科学的理解和认识, 并通过一些简洁、优美、和谐的公式来表现大自然. 因此可以说数学和音乐都是用来描述世界的,只是描述方式有所不同,但最终目的都是为人类更好地生存和发展服务,于是它们之间存在着内在的联系应该是一件自然而然的事.

既然数学与音乐有如此美妙的联系,为何不让我们沉浸在《梁祝》优美动听的旋律中或置身于昆虫啁啾鸣叫的田野里静下心来思考数学与音乐的内在联系呢 ?为何不让我们在铮铮琵琶声中或令人激动的交响曲中充满信心地对它们的内在联系继续探索呢 ?

上面,我们提供了一些数学与音乐联系的素材,如何将这些素材“加工”成为“数学教育”的内容呢?我们提出几个问题仅供教材编写者和在一线工作的教师思考.

1) 如何将这样的素材经过加工渗透到数学教学和数学教材中 ?

2) 能否把这些素材编写成为“科普报告”, 在课外活动中,向音乐和数学爱好者报告,调查,了解,思考这样的报告对学生的影响以及学生对这样的报告的反映.

go语言斐波那契数列的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于go语言实现斐波那契、go语言斐波那契数列的信息别忘了在本站进行查找喔。