描述
斐波那契数列：数列的第一个值和第二个值都为1，接下来每个数都等于前两个数的和。求第n个数是多少？
输入描述
一个整数n,表示要求的第n位。（1<n<90）
输出描述
一个整数，第n位的数字。
用例输入 1
20
用例输出 1
6765
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+2];
a[1]=1;
a[2]=1;
for(int i=3;i<=n;i++) a[i]=a[i-1]+a[i-2];
cout<<a[n]<<endl;
}
要开 long long 和记忆化，不然会出错。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int Fib[103];
int fib(int num){
if(Fib[num]) return Fib[num];
if(num == 1){
return 1;
}
if(num == 2){
return 1;
}
return Fib[num] = fib(num - 1) + fib(num - 2);
}
int n;
signed main(){
cin >> n;
cout << fib(n) << endl;;
return 0;
}
#include <iostream>
using namespace std;
long long getFibonacciNumber(int n) {
if (n <= 0 || n >= 90) {
throw invalid_argument("n必须在1和89之间。");
}
long long first = 1;
long long second = 1;
for (int i = 3; i <= n; ++i) {
long long next = first + second;
first = second;
second = next;
}
return second;
}
int main() {
int n;
cout << "请输入n的值（1 < n < 90）: ";
cin >> n;
try {
long long result = getFibonacciNumber(n);
cout << "第" << n << "个斐波那契数列的值为：" << result << endl;
} catch (const exception& ex) {
cout << "错误: " << ex.what() << endl;
}
return 0;
}
解决方案如下：
首先，我们可以使用递归方法来实现斐波那契数列。递归方法的思路是，第n位的数等于第n-1位和n-2位的数之和。
下面是用Python语言实现递归方法的代码：
def fibonacci(n):
if n <= 0:
return ValueError("n must be a positive integer")
if n == 1 or n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
n = int(input("请输入要求的第n位："))
result = fibonacci(n)
print(f"第{n}位的数是：{result}")
这个方法的时间复杂度是O(2^n)，效率比较低。所以我们可以采用动态规划的方法，使用一个数组来保存已经计算过的数值，以避免重复计算。
下面是用Python语言实现动态规划方法的代码：
def fibonacci(n):
if n <= 0:
return ValueError("n must be a positive integer")
if n == 1 or n == 2:
return 1
else:
dp = [0] * n
dp[0] = 1
dp[1] = 1
for i in range(2, n):
dp[i] = dp[i-1] + dp[i-2]
return dp[n-1]
n = int(input("请输入要求的第n位："))
result = fibonacci(n)
print(f"第{n}位的数是：{result}")
这个方法的时间复杂度是O(n)，比递归方法效率要高。
如果n比较大（大于90），斐波那契数的计算可能会溢出整数范围。这时可以使用浮点数或者使用Python的大整数库来存储数值。大整数库可以使用int类型的bit_length()方法来判断整数的位数，进而判断是否会溢出。
以上是我给出的解决方案，请测试并查看是否满足需求。