输入n,用最快的方法求Fibonacci 数列的第n 项_输入 n,用最快的方法求该数列的第 n 项。-程序员宅基地

技术标签: 面试算法  


题目:定义Fibonacci 数列如下:
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
输入n,用最快的方法求该数列的第n 项。
分析:在很多C 语言教科书中讲到递归函数的时候,都会用Fibonacci 作为例子。
因此很多程序员对这道题的递归解法非常熟悉,但....呵呵,你知道的。。
ANSWER:
This is the traditional problem of application of mathematics...
let A=
{1 1}
{1 0}
f(n) = A^(n-1)[0,0]
this gives a O(log n) solution.
int f(int n) {
  int A[4] = {1,1,1,0};
  int result[4];
  power(A, n, result);
  return result[0];
}

void multiply(int[] A, int[] B, int _r) {
  _r[0] = A[0]*B[0] + A[1]*B[2];
  _r[1] = A[0]*B[1] + A[1]*B[3];
  _r[2] = A[2]*B[0] + A[3]*B[2];
  _r[3] = A[2]*B[1] + A[3]*B[3];
}

void power(int[] A, int n, int _r) {
  if (n==1) { memcpy(A, _r, 4*sizeof(int)); return; }
  int tmp[4];
  power(A, n>>1, _r);
  multiply(_r, _r, tmp);
  if (n & 1 == 1) {
    multiply(tmp, A, _r);
  } else {
    memcpy(_r, tmp, 4*sizeof(int));
  }

}


所谓的O(logn)的算法实现。




版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Vast_Sea/article/details/8166774

智能推荐

POJ Test for Job(DAG上拓扑排序)_dag用两条路径覆盖的方案数 拓扑序do-程序员宅基地

文章浏览阅读174次。 题目链接:http://poj.org/problem?id=3249 题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。 题目中说了这是一个DAG图(有向无环图),跑最长路的话会超时(spfa反向建边好像可以过),根据有向无环图的性质我们可以用拓扑排序来写,根据每条边的度数来选择边..._dag用两条路径覆盖的方案数 拓扑序do

Masonry实现view高度自适应_masory 高度自适应-程序员宅基地

文章浏览阅读1.2w次。- (void)viewDidLoad { [super viewDidLoad]; self.view.backgroundColor = [UIColor whiteColor]; UIView *container = [UIView new]; [self.view addSubview:container]; container.backgro..._masory 高度自适应

电子阅读器 e-book reader _e book read-程序员宅基地

文章浏览阅读1.6k次。电子阅读器 e-book reader 收藏 电脑的普及带来了人们阅读习惯的改变,从习惯每天看报纸到习惯每天浏览网页,电子产品逐渐取代纸质书本进入了人们的日常生活,如今电子阅读器也越来越受欢迎。请看《中国日报》的报道:Chinese hi-tech firm Hanwang Technology said it expected shipments of its e-book reader_e book read

如何快速优化手游性能问题?从UGUI优化说起-程序员宅基地

文章浏览阅读1.5k次,点赞2次,收藏27次。WeTest 导读本文作者从自身多年的Unity项目UI开发及优化的经验出发,从UGUI,CPU,GPU以及unity特有资源等几个维度,介绍了unity手游性能优化的一些方法。在之前的文章《手游内存占用过高?如何快速定位手游内存问题》中提到,Mono内存和native内存是PSS内存主要的组成部分,mono内存更多的起到内存调用的功能,因此常常成为了开发人员优化内存的起点;而在游戏的其他的进程中..._canvas.sendwillrendercanvases

细致分析及解决:STM32CUBEMX报错 xxx but MDK-ARM V5.27 project generation have a problem以及keil的device not found_but mdk-arm v5.27project generation have a problem-程序员宅基地

文章浏览阅读4.9k次,点赞7次,收藏16次。细致分析及解决:STM32CUBEMX报错 xxx but MDK-ARM V5.27 project generation have a problem以及keil的device not found_but mdk-arm v5.27project generation have a problem

Deepdive 只能在linux下运行_deepspeed是不是只能在linux-程序员宅基地

文章浏览阅读509次。Deepdive 只能在linux下运行_deepspeed是不是只能在linux

随便推点

zoj3908Number Game_easy number game csdn-程序员宅基地

文章浏览阅读591次。F - Number GameTime Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %lluSubmit Status Practice ZOJ 3908DescriptionThe bored Bob is playing a number game. In the be_easy number game csdn

springmvc拦截器对请求参数解密_通过拦截器Interceptor实现Spring MVC中Controller接口访问信息的记录...-程序员宅基地

文章浏览阅读675次。java web工程项目使用了Spring+Spring MVC+Hibernate的结构,在Controller中的方法都是用于处理前端的访问信息,Controller通过调用Service进行业务处理后给前端返回ModelAndView对象或者只返回Json格式数据。如果能够获得Http请求在后端程序中处理的相关信息,对于开发和调试时十分方便的。工程中使用了Spring MVC的Interce..._java 拦截器接收参数解密

OSG开发笔记(二十):OSG使用HUD显示文字_osg hud文本颜色不一致-程序员宅基地

文章浏览阅读3.5w次。若该文为原创文章,未经允许不得转载原博主博客地址:https://blog.csdn.net/qq21497936本文章博客地址:https://blog.csdn.net/qq21497936/article/details/97382348目录前言目标效果HUD(抬头显示)HUD设置渲染顺序HUD坐标系解释代码Demo运行效果入坑入坑二:位置(0,0..._osg hud文本颜色不一致

支付宝小程序、百度小程序、微信小程序、今日头条小程序技术分析_头条小程序和微信小程序登录的区别-程序员宅基地

文章浏览阅读6.8k次,点赞4次,收藏33次。支付宝小程序、百度小程序、微信小程序、今日头条小程序四大小程序对比分析,BAT小程序技术分析_头条小程序和微信小程序登录的区别

python之os模块详解_python os模块详解-程序员宅基地

文章浏览阅读8k次,点赞9次,收藏63次。os模块详解在看大神们的代码时经常能看到os模块的身影,然后就想着做一下总结,方便以后查看下图是参考CSDN博主“数据分析与统计学之美”,非常感谢博主的图片下面我们针对每一个详细的介绍一下其用法:(1)os.getcwd() 获取当前的工作路径;>>> import os>>> os.getcwd()'C:\\Users\\cc'(2)os.listdir(path) 显示当前文件夹下所有文件和目录组成的列表;>>> pat_python os模块详解

关于torch.gather(input, dim, index)_torch.gather(input,dim,index)-程序员宅基地

文章浏览阅读254次。torch.gather()函数可以理解为根据索引和维度来求张量中对应的数,最后得到的是一个shape和index相同的张量即“以A = B.gather(dim=0, index=torch.tensor([[2, 1, 2]]))为例,(index维度可以是任意的维度,不要受限于B),即A的维度为(1,3);其次dim=0代表按列索引,那么index第一个元素“2”的含义为在B中其所在列(即第0列)的第2个元素。同理,index第二个元素“1”的含义为在B中其所在列(即第1列)的第1个元素;_torch.gather(input,dim,index)

推荐文章

热门文章

相关标签