第十九题(最快的方法求Fibonacci数列)

2024-08-29 17:58

本文主要是介绍第十九题(最快的方法求Fibonacci数列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:定义Fibonacci 数列如下:
        /          0                      n=0
f(n)=            1                      n=1
        \    f(n-1)+f(n-2)          n=2

输入n,用最快的方法求该数列的第n 项。


1.采用递归求解,函数的调用过程中,每个函数都都分裂成两个函数,计算的结果没有保存,出现了大量重复计算,算法复杂度O(2^n)

2.采用从下往上的循环结构,时间复杂度O(n)

3.采用矩阵求解,数列中的第n项是矩阵

11

10

n-1次方后所得矩阵的最左上角元素。

因此可以通过矩阵的乘方求解,为了追求更优的时间效率,不采用普通的循环n次乘方的方法,而是采用分治的思想,把n次方换成n/2的平方,以此类推,最终可以达到log(n)的复杂度。

代码:

#include<iostream>
using namespace std;
namespace MS100P_19
{//采用递归的方法,复杂度O(2^n)int Fibonacci_Recursive(int n){if (n == 0)	return 0;if (n == 1)	return 1;else  return Fibonacci_Recursive(n - 1) + Fibonacci_Recursive(n - 2);}//非递归1,时间复杂度 O(n)int Fibonacci_1(int n){long smaller = 0;long bigger = 1;long sum=0;if (n == 0)	return 0;if (n == 1)	return 1;for (int i = 2; i <=n; i++){sum = smaller + bigger;smaller = bigger;bigger = sum;}return bigger;}//非递归,时间复杂度O(logN)struct matrix{long long m00, m01;long long m10, m11;matrix(long long parM00, long long parM01, long long parM10, long long parM11)\:m00(parM00), m01(parM01), m10(parM10), m11(parM11){}matrix() :m00(1), m01(1), m10(1), m11(0){}};matrix matrixMultiply(const matrix& mtx1, const matrix& mtx2){return matrix(mtx1.m00*mtx2.m00 + mtx1.m01*mtx2.m10, mtx1.m00*mtx2.m01 + mtx1.m01*mtx2.m11, \mtx1.m10*mtx2.m00 + mtx1.m11*mtx2.m10, mtx1.m10*mtx2.m01 + mtx1.m11*mtx2.m11);}matrix matrixPower(int power)		//n为指数{matrix temp;if (power == 1)	return temp;if (power % 2 == 0){temp = matrixPower(power / 2);return matrixMultiply(temp, temp);}else{temp = matrixPower(power / 2);temp = matrixMultiply(temp, temp);return matrixMultiply(temp,matrix());}}long long Fibonacci_2(int n){if (n == 0)	return 0;if (n == 1)	return 1;else return matrixPower(n - 1).m00;}void test(){cout << Fibonacci_Recursive(1) << endl;cout << Fibonacci_1(1) << endl;cout << Fibonacci_2(1) << endl;cout << Fibonacci_Recursive(10) << endl;cout << Fibonacci_1(10) << endl;cout << Fibonacci_2(10) << endl;}
}int _tmain(int argc, _TCHAR* argv[])
{MS100P_19::test();return 0;
}



这篇关于第十九题(最快的方法求Fibonacci数列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1118571

相关文章

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Nginx安全防护的多种方法

《Nginx安全防护的多种方法》在生产环境中,需要隐藏Nginx的版本号,以避免泄漏Nginx的版本,使攻击者不能针对特定版本进行攻击,下面就来介绍一下Nginx安全防护的方法,感兴趣的可以了解一下... 目录核心安全配置1.编译安装 Nginx2.隐藏版本号3.限制危险请求方法4.请求限制(CC攻击防御)

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

JAVA中安装多个JDK的方法

《JAVA中安装多个JDK的方法》文章介绍了在Windows系统上安装多个JDK版本的方法,包括下载、安装路径修改、环境变量配置(JAVA_HOME和Path),并说明如何通过调整JAVA_HOME在... 首先去oracle官网下载好两个版本不同的jdk(需要登录Oracle账号,没有可以免费注册)下载完

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构

SQL中如何添加数据(常见方法及示例)

《SQL中如何添加数据(常见方法及示例)》SQL全称为StructuredQueryLanguage,是一种用于管理关系数据库的标准编程语言,下面给大家介绍SQL中如何添加数据,感兴趣的朋友一起看看吧... 目录在mysql中,有多种方法可以添加数据。以下是一些常见的方法及其示例。1. 使用INSERT I

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函