当前位置: 首页 > news >正文

win7+网站建设扬州自适应网站建设

win7+网站建设,扬州自适应网站建设,鄂州网站建设网络公司,生成图片的网站算法之矩阵计算斐波那契数列 本节内容 斐波那契介绍普通方式求解斐波那契矩阵概念矩阵求幂矩阵求解斐波那契1.斐波那契介绍 斐波那契数列有关十分明显的特点#xff0c;那是#xff1a;前面相邻两项之和#xff0c;构成了后一项。即f(n)f(n-1)f(n-2),f(0)0,f(1)f(2)1,推导下… 算法之矩阵计算斐波那契数列 本节内容 斐波那契介绍普通方式求解斐波那契矩阵概念矩阵求幂矩阵求解斐波那契1.斐波那契介绍 斐波那契数列有关十分明显的特点那是前面相邻两项之和构成了后一项。即f(n)f(n-1)f(n-2),f(0)0,f(1)f(2)1,推导下去f(3)2,f(4)3,f(5)5。。。。。。 2.普通方式求解斐波那契 按照上面提供的推导公式普通方式求解斐波那契数列代码如下 1 def normal(n): 2 a,b,c0,1,1 3 while n: 4 a,b,cb,c,bc 5 n-1 6 return a   使用上面的方式求解第n项斐波那契数列的时间复杂度为O(n),也就是说时间复杂度随着n的增长而线性增长。 3.矩阵概念 开始先来介绍一下矩阵的概念在数学中矩阵Matrix是一个按照长方阵列排列的复数或实数集合最早来自于方程组的系数及常数所构成的方阵。 这里不介绍矩阵的各方面知识了如果那样的话。。。就是一篇数学笔记了。。。这里只讲解矩阵相乘的概念。 矩阵相乘矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数column和第二个矩阵的行数row相同时才有意义。一般单指矩阵乘积时指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起所以有时候可以简便地表示一些复杂的模型。 设A为m*p的矩阵B为p*n的矩阵那么称m*n的矩阵C为矩阵A与B的乘积记作CAB 4.矩阵求幂 上面已经介绍过了矩阵相乘的概念了那么斐波那契该怎么由矩阵标示呢 从第三项开始每一项都是前两项之和。 F(n)F(n−1)F(n−2), n⩾3 把斐波那契数列中 相邻的两项F(n)和F(n−1)写成一个2×1的矩阵。 斐波那契数列用矩阵推导如下 求F(n)等于求二阶矩阵的n - 1次方结果取矩阵第一行第一列的元素。 问题转换为二阶矩阵的n次幂。 而计算二阶矩阵的N次幂运算由于二阶矩阵乘法满足结合律这样可以快速计算二阶矩阵的n次幂运算。 假设A为一个二阶矩阵则A的幂运算满足下面的条件 A**6A**3∗A**3 A**7A**3∗A**3∗A**1A**4*A**2*A**1 在这里我们可以类似地把A看做是二进制中的22**72**4*2**2*2**1也就是说可以把矩阵的幂转换成二进制来表示。从而可以将n次幂拆解成长度为logn的二进制数来表示7111(二进制)。 这就是快速求二阶矩阵的核心方法。 5. 矩阵求解斐波那契 前戏做足了下面就该秀代码了。 1 def multi(a,b): # 计算二阶矩阵的相乘2 c[[0,0],[0,0]] # 定义一个空的二阶矩阵3 for i in range(2):4 for j in range(2):5 for k in range(2): # 新二阶矩阵的值计算6 c[i][j]c[i][j]a[i][k]*b[k][j]7 return c8 9 10 def matrix(n): 11 base[[1,1],[1,0]] # 元矩阵这里可以把元矩阵看做是2**01 12 ans[[1,0],[0,1]] # 结果矩阵 最开始的结果矩阵也可以看做是1因为这个矩阵和任意二阶A矩阵相乘结果都是A 13 while n: 14 if n1: # 取n的二进制的最后一位和1做与运算如果最后一位是1则进入if体内部 15 ansmulti(ans,base) # 如果在该位置n的二进制为1则计算ans和base矩阵 16 basemulti(base,base) # base矩阵相乘相当于初始base矩阵的幂*2 17 n1 # n的二进制往右移一位 18 return ans[0][1] # 最后获取到的二阶矩阵的[0][1]即f(n)的值   最后把例子的完整代码贴出来 1 import time2 3 4 def multi(a,b):5 c[[0,0],[0,0]]6 for i in range(2):7 for j in range(2):8 for k in range(2):9 c[i][j]c[i][j]a[i][k]*b[k][j] 10 return c 11 12 13 def matrix(n): 14 base[[1,1],[1,0]] 15 ans[[1,0],[0,1]] 16 while n: 17 if n1: 18 ansmulti(ans,base) 19 basemulti(base,base) 20 n1 21 # for i in range(2): 22 # print(ans[i]) 23 return ans[0][1] 24 25 def normal(n): 26 a,b,c0,1,1 27 while n: 28 a,b,cb,c,bc 29 n-1 30 return a 31 32 nint(input()) 33 starttime.time() 34 print(Normal:,normal(n)) 35 print(use:,time.time()-start) 36 starttime.time() 37 print(Matrix:,matrix(n)) 38 print(use:,time.time()-start) 39 #计算结果 40 65536 41 Normal: 731992144602...... 42 use: 0.07219505310058594 43 Matrix: 731992144602...... 44 use: 0.023076772689819336   可以看出来当n的值越来越大的时候两种方式计算出结果的时间差距将越来越大正常的计算时间复杂度是O(n),矩阵求值的时间复杂度是O(logn)。 后记 由此可以看出使用推导式f(n)f(n-1)f(n-2)求斐波那契的第n项的算法复杂度极限为O(n)这是一维世界下的极限。将其从一维上升到二维用二阶矩阵推导斐波那契数列时计算的算法复杂度为O(logn)也就是说使用升维的手段将一维空间进行扭曲从而将距离缩短可以更快的计算出结果。 由此推导出如果人来要突破光速的极限需要将现有的三维空间升级到四维空间扭曲空间从而缩短距离达到突破光速的目的。 转载于:https://www.cnblogs.com/huxianglin/p/5995649.html
http://www.sadfv.cn/news/64611/

相关文章:

  • 百度商桥怎样绑定网站群英云服务器
  • 上海哪家做公司网站网站建设背景是什么
  • 广州越秀建网站的公司怎么使用dw做一个网站
  • 如何做网站优化并快速提高权重做网站的图片要求大小
  • 装修网站模板下载网站目录结构图
  • 国外网站国内备案最新行业动态
  • 湛江做网站seo的iis网站开发教程
  • 网站平台免费中国企业网聚焦中原
  • 支付网站开发怎么做账沈阳网站制作机构
  • 哪些大学网站做的比较好织梦 电影网站 模板
  • 网站导航栏代码网贷之家网站建设
  • 任县企业做网站建设旅游网站数据库设计
  • 网站开发 外文文献网站建设与维护 唐清安
  • 网站名字重复如何在已建设好的网站做修改
  • 电子商务网站规划 分析 设计阿里云主机安装wordpress
  • 网站是否备案怎么查询贵阳官网seo诊断
  • 深圳网站建设选哪家关于国家对网站建设
  • 糟糕的网站设计济南有做五合一网站公司
  • 汕头教育学会网站建设涿州网站建设推广
  • 山西 网站制作百度做网站要多久
  • 绵阳网站关键词佛山网站外包
  • app推广代理去哪里找安阳seo公司
  • 盐城网站建设要多少钱岳阳商城网站建设
  • 湖南天辰建设责任公司网站音乐介绍网站怎么做
  • 网站建设和seo的工作好不好网站的建设有什么好处
  • 网站备案公告久久建筑网资料全吗
  • 诚信网站认证必需做吗北京建筑设计公司排行榜
  • 免费网站建设推广服务wordpress read more
  • 网站评价公司网址怎么注册
  • 亳州蒙城网站建设免费小程序制作网站