题解 | 斐波那契数列#
解题思路
斐波那契数列的计算有多种方法，这里使用最简单的迭代方法：
- 特判
或
的情况，直接返回
- 使用两个变量
和
分别记录前两个数
- 迭代
次，每次计算下一个斐波那契数
- 最终
个斐波那契数
代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if(n <= 2) {
cout << 1 << endl;
return 0;
}
int a = 1, b = 1;
for(int i = 3; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
cout << b << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if(n <= 2) {
System.out.println(1);
return;
}
int a = 1, b = 1;
for(int i = 3; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
System.out.println(b);
}
}
n = int(input())
if n <= 2:
print(1)
else:
a, b = 1, 1
for i in range(3, n + 1):
a, b = b, a + b
print(b)
算法及复杂度
- 算法：迭代法
- 时间复杂度：
- 需要迭代
- 空间复杂度：
- 只使用了常数个变量
投递58到家等公司8个岗位
