处理大数斐波那契序列的问题

大数斐波那契问题

该斐波那契题：有一串序列叫做斐波那契序列，在这序列中前两项均为1，并且从第三项起每一项都等于前两项之和。例如这个序列是F_1 = F_2 = 1并且对于n \geq 3有F_n = F_{n-1} + F_{n-2}即序列呈现为1, 1, 2, 3, 5, 8,... 现在的问题是要求找出第n项的值是多少

算法思路：最基本的方式是通过递归实现两个数的求和。然而，在使用整型变量存储结果时会遇到一个问题：即数值溢出。即使我们选用长整型变量同样会遭遇溢出问题——因为当n达到110时生成的结果已经非常庞大（此时生成的结果已经非常庞大），达到了43566776258854844738105这一规模（根本无法存储在一个基本数据类型中）。因此，在这种情况下我们可以采用大数运算的方法：将数值分解为单个数字进行处理（虽然这种方法节省空间有限）。我们可以将每一位单独存储在数组中的一个元素中（虽然这种方法节省空间有限），同时利用数组特性使得计算过程能够顺利进行——通过这种方式我们就能有效地解决数值溢出的问题。

  #include <iostream>

    
 using namespace std;
    
  
    
 #define N 200      //最多位数，数值溢出时更改值
    
  
    
 int F