高精度处理斐波那契序列(C语言)

  1 #include<stdio.h>
  2 #include<string.h>
  3 //memset,strcpy,strlen函数头文件 
  4 int main(void)
  5 {
  6 char sum[1000000];//用来保存产生的下一个斐波那契数，当然了，是字符串形式 
  7 long long m,i,max,s = 0;//max用来存放数位较长的个数 
  8 char s1[100000],s2[100000]; //用来存储斐波那契数列的相邻两个数，并以字符串形式进行存储 
  9 int a[100000],b[100000];//转存到int数组中 
 10 long long n;
 11 scanf("%lld",&n);//输入你想要输出的菲波那切数列的第多少位 
 12 
 13 strcpy(s1,"1"); //初始第一项为"1"; 
 14 strcpy(s2,"1");//初始第二项为"1";
 15 
 16 for(m=2;m<n;m++)//大循环 
 17 {
 18 //每一次都需要将a,b数组所有字节置0 
 19 memset(a,0,sizeof(int)*5000);
 20 memset(b,0,sizeof(int)*5000);
 21 
 22 //a[0]用来保存每一次第一个菲波那切数就是s1的长度 ，并将菲波那切数以逆向方式存储到a数组中 
 23 a[0] = strlen(s1);
 24 for(i=1;i<=a[0];i++)
 25 {
 26 a[i] = s1[a[0] - i] - ‘0‘;//a[0]-i便是倒序 
 27 }
 28 
 29 //b[0]用来保存每一次第二个菲波那切数就是s2的长度 ，并将菲波那切数以逆向方式存储到b数组中
 30 b[0] = strlen(s2);
 31 for(i=1; i<=b[0]; i++)
 32 {
 33 b[i] = s2[b[0] - i] - ‘0‘;//b[0]-i便是倒序 
 34 }
 35 
 36 //max存放数位较大的 
 37 //因为相加是倒序相加，因此需要找到位数长的，并记录个数 
 38 max =( a[0]>b[0]?a[0]:b[0] ); 
 39 
 40 for(i=1;i<=max;i++)
 41 {
 42 //将a[i]和b[i]的值赋给a[i],a[i]可能大于10，或者小于10；
 43 //大于10则要进一位;
 44 //自身变成a[i]%10; 
 45 a[i]+=b[i];//此时a[i]可能大于10 
 46 a[i+1]+=a[i]/10;//无论a[i]是不是大于10，都除以10，发给下一位，也就是所谓的进一位
 47 a[i]%=10;//无论a[i]是不是大于10，求余10，发给a[i] 
 48 }
 49 
 50 //可能进位导致较长位数+1； 
 51 max++;
 52 
 53 //进位导致0的出现 ，出现多余有效数字 
 54 while(a[max] == 0 && max > 1)
 55 {
 56 max--;
 57 } 
 58 
 59 //将获得的新的斐波那契数以字符串形式发送给一个数组，在通过strcpy函数复制给s2, 
 60 for (i = max,s = 0;i>=1;i--,s++)
 61 {
 62 sum[s] = a[i]+‘0‘;//再将数字转化为字符 
 63 } 
 64 
 65 strcpy(s1,s2);//将s2复制给s1 
 66 strcpy(s2,sum);//将sum数组里面的字符串复制给s2 
 67 } 
 68 printf("%s",s2);
 69 return 0;
 70 }————————————————————
 71 第一次写高精度吧，还是被老师逼得
 72 无fuck说
 73 ————————————————————
 74 #include<stdio.h>
 75 #include<string.h>
 76 //memset,strcpy,strlen函数头文件 
 77 int main(void)
 78 {
 79 char sum[1000000];//用来保存产生的下一个斐波那契数，当然了，是字符串形式 
 80 long long m,i,max,s = 0;//max用来存放数位较长的个数 
 81 char s1[100000],s2[100000]; //用来存储斐波那契数列的相邻两个数，并以字符串形式进行存储 
 82 int a[100000],b[100000];//转存到int数组中 
 83 long long n;
 84 scanf("%lld",&n);//输入你想要输出的菲波那切数列的第多少位 
 85 
 86 strcpy(s1,"1"); //初始第一项为"1"; 
 87 strcpy(s2,"1");//初始第二项为"1";
 88 
 89 for(m=2;m<n;m++)//大循环 
 90 {
 91 //每一次都需要将a,b数组所有字节置0 
 92 memset(a,0,sizeof(int)*5000);
 93 memset(b,0,sizeof(int)*5000);
 94 
 95 //a[0]用来保存每一次第一个菲波那切数就是s1的长度 ，并将菲波那切数以逆向方式存储到a数组中 
 96 a[0] = strlen(s1);
 97 for(i=1;i<=a[0];i++)
 98 {
 99 a[i] = s1[a[0] - i] - ‘0‘;//a[0]-i便是倒序 
100 }
101 
102 //b[0]用来保存每一次第二个菲波那切数就是s2的长度 ，并将菲波那切数以逆向方式存储到b数组中
103 b[0] = strlen(s2);
104 for(i=1; i<=b[0]; i++)
105 {
106 b[i] = s2[b[0] - i] - ‘0‘;//b[0]-i便是倒序 
107 }
108 
109 //max存放数位较大的 
110 //因为相加是倒序相加，因此需要找到位数长的，并记录个数 
111 max =( a[0]>b[0]?a[0]:b[0] ); 
112 
113 for(i=1;i<=max;i++)
114 {
115 //将a[i]和b[i]的值赋给a[i],a[i]可能大于10，或者小于10；
116 //大于10则要进一位;
117 //自身变成a[i]%10; 
118 a[i]+=b[i];//此时a[i]可能大于10 
119 a[i+1]+=a[i]/10;//无论a[i]是不是大于10，都除以10，发给下一位，也就是所谓的进一位
120 a[i]%=10;//无论a[i]是不是大于10，求余10，发给a[i] 
121 }
122 
123 //可能进位导致较长位数+1； 
124 max++;
125 
126 //进位导致0的出现 ，出现多余有效数字 
127 while(a[max] == 0 && max > 1)
128 {
129 max--;
130 } 
131 
132 //将获得的新的斐波那契数以字符串形式发送给一个数组，在通过strcpy函数复制给s2, 
133 for (i = max,s = 0;i>=1;i--,s++)
134 {
135 sum[s] = a[i]+‘0‘;//再将数字转化为字符 
136 } 
137 
138 strcpy(s1,s2);//将s2复制给s1 
139 strcpy(s2,sum);//将sum数组里面的字符串复制给s2 
140 } 
141 printf("%s",s2);
142 return 0;
143 }