c++高精度+递归求斐波拉契第n项怎么写

小启洋同学

c++高精度+递归求斐波拉契第n项怎么写

FishC

要实现高精度的斐波那契数列，可以使用字符串来存储每一项的值。首先，需要明确的是斐波那契数列的第0项为0，第1项为1。

接下来，我们可以使用递归的方法来计算斐波那契数列的第n项。递归的思想是，第n项的值等于第n-1项的值加上第n-2项的值。

下面是用C++编写的示例代码：

1. #include <iostream>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. string addStrings(string num1, string num2) {
   
6.     if (num1.length() < num2.length()) {
   
7.         swap(num1, num2);
   
8.     }
   
9.     int carry = 0;
   
10.     int i = num1.length() - 1;
    
11.     int j = num2.length() - 1;
    
12.     string result = "";
    
13.     while (i >= 0 || j >= 0 || carry) {
    
14.         int x = i >= 0 ? num1[i--] - '0' : 0;
    
15.         int y = j >= 0 ? num2[j--] - '0' : 0;
    
16.         int sum = x + y + carry;
    
17.         carry = sum / 10;
    
18.         result = to_string(sum % 10) + result;
    
19.     }
    
20.     return result;
    
21. }
    
22. 
    
23. string fib(int n) {
    
24.     if (n <= 1) {
    
25.         return to_string(n);
    
26.     }
    
27.     string a = "0";
    
28.     string b = "1";
    
29.     for (int i = 2; i <= n; ++i) {
    
30.         string temp = b;
    
31.         b = addStrings(a, b);
    
32.         a = temp;
    
33.     }
    
34.     return b;
    
35. }
    
36. 
    
37. int main() {
    
38.     int n;
    
39.     cout << "请输入要计算的斐波那契数列的项数：";
    
40.     cin >> n;
    
41.     string result = fib(n);
    
42.     cout << "第" << n << "项的值为：" << result << endl;
    
43.     return 0;
    
44. }

复制代码

在上面的代码中，addStrings函数用于实现两个字符串数字的相加操作，fib函数利用递归思想实现了斐波那契数列的计算，main函数用于接收用户输入并输出结果。

注意，这种方法会占用较多的内存空间，因为每一项都需要使用字符串来存储。当计算较大的斐波那契数列时，可能会导致程序运行缓慢或内存溢出。如果需要更高效的实现方式，可以考虑使用迭代或矩阵快速幂等方法。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

人造人

1. #include <iostream>
   
2. #include <boost/multiprecision/cpp_int.hpp>
   
3. 
   
4. using boost::multiprecision::cpp_int;
   
5. using std::cout, std::endl;
   
6. 
   
7. cpp_int fibonacci(cpp_int n) {
   
8.     if(n == 0) return 0;
   
9.     if(n == 1) return 1;
   
10.     return fibonacci(n - 1) + fibonacci(n - 2);
    
11. }
    
12. 
    
13. int main() {
    
14.     cout << fibonacci(10) << endl;
    
15.     return 0;
    
16. }
    

复制代码