C++ 阶乘和斐波那契 Factorial Fibonacci
2023-03-07 09:13:38 时间
数据结构、算法与应用 第一张练习 19,20
阶乘 n! Factorial
阶乘是非常常见的数学计算以及算法入门问题。 其中 0,1,2,6,24,120... fn = n ( n<=1 ) fn = n * fn(n-1) (n>1) 使用递归实现是非常直观和简单的:
递归版本
int factorial( int n ){
return n>1 ? n*factorial(n-1) : n;
}
迭代版本
int factorial( int n ){
int res = n;
while( n>1 ){
res *= --n;
}
return res;
}
斐波那契 Fibonacci
1.斐波那契数
斐波那契数列是算法里最基础的概念了。
其中 0,1,1,2,3,5,8... fn = n ( n<=1 ) fn = fn(n-2) + fn(n-1) ( n>1 )
同样递归版本是简单而直观的:
递归版:
int fabonacci( int n ){
return n>1 ? fabonacci( n-1 ) + fabonacci( n-2 ) : n;
}
递归版的Fibonacci效率是有严重缺陷的,主要是由于在合并两次之和时,两边进行了重复的计算,而每次重复计算也都是包含了更多迭代版本中更多的重复。这里由于递归而造成的重复计算复杂度为 O( 2∧n )
迭代版:
/*
* n>0 当n<=0时,默认不考虑
* 使用双指针缓存本次和上次结果,并进一步迭代
*/
int fabonacci( int n ){
int l = 1;
int r = 1;
for( int i = 2; i <= n; i ++ ){
r = l + r;
l = r - l;
}
return r;
}
迭代版的斐波那契数的复杂度仅为O(n)
2.Fibonacci数列
/*
* 返回数组首元素,数组长度为n n>0
*/
#include <iostream>
#include <cstdlib>
int * fabonacci( int n ){
int * a = new int[n];
a[0] = 1;
if( n<2 ) return a;
a[1] = 1;
for( int i = 2; i < n; i++ ){
a[i] = a[i-1] + a[i-2];
a[i-1] = a[i] - a[i-2];
}
return a;
}
int main()
{
int n = 8;
int * b = fabonacci(n);
for( int i = 0; i<n; i++ ){
std::cout << b[i] << std::endl;
}
}
这段代码会输出:
1
1
2
3
5
8
13
21
相关文章
- 降低AWS Lambda 冷启动时间的4种方案
- 欢迎参加 2021 年 AWS 存储日
- 新增功能 – Amazon FSx for NetApp ONTAP
- 新增功能 — Amazon EFS 智能分层通过优化不断变化的访问模式优化工作负载成本
- Python Twisted介绍
- 用机器学习解码媒体的社交影响
- 一文看懂 Amazon EKS 中的网络规划
- AppSync调试方法
- Amazon Managed Grafana 现已全面推出,并具有许多新功能
- AWS CloudFormation 的新功能 – 从故障点快速重试堆栈操作
- 使用更具体的 Amazon VPC 路由检查子网到子网的流量
- Amazon Textract 更新:8 个亚马逊云科技区域的价格降幅达 32%,异步任务处理时间缩短近 50%
- Announcing the latest AWS Heroes – August 2021
- 云原生编排数据分析管道初探
- 使用托管节点组结合启动模板简化EKS升级与运维
- 如何将您的自定义容器镜像导入Amazon SageMaker Studio notebooks
- 如何注册成为亚马逊云科技 Marketplace海外区卖家
- 如何使用数据网格创建现代包装消费品 (CPG)行业数据架构
- 预处理日志以便在 Amazon ES 中进行异常检测
- java deque_java 集合框架(十五)Deque