奉上前端面试题目一道：求斐波纳契数列的第200项。
不假思考，闭眼直接上码：
1 var a = 1, 2 b = 1, 3 c; 4 for (let i = 2; i < 200; i++) { 5 c = a + b; 6 a = b; 7 b = c; 8 } 9 console.log(c);
这基本就凉了。为啥？且看输出：2.8057117299251016e+41，这是个什么鬼？
原因在于这个数太大了，已超出长整数的边界。怎么办呢？
在java中就比较容易，因为在java中提供了BigInteger类。
1 BigInteger a = BigInteger.valueOf(1); 2 BigInteger b = BigInteger.valueOf(1); 3 BigInteger c = null; 4 for (var i = 2; i < 1000; i++) { 5 c = a.add(b); 6 a = b; 7 b = c; 8 } 9 System.out.println(c);
因为BigInteger提供无限精度运算，所以输出第1000项也没问题。
那么在js中怎么实现呢？最简单的一个办法就是将参与运算的两个操作数转换成数组，模拟按位进行加操作即可。如下：
1 function BigInteger(n) { 2 if (Array.isArray(n)) { 3 this.metaArray = n; 4 } else if (typeof(n) == "number") { 5 this.metaArray = toMetaArray(n + ""); 6 } else if (typeof(n) == "string") { 7 this.metaArray = toMetaArray(n); 8 } 9 10 //实现两个BigInteger实例相加，返回值仍是BigInteger 11 this.add = function(another) { 12 var a = this.metaArray; 13 var b = another.metaArray; 14 var i = 0; 15 var c = []; 16 while (true) { 17 var t = (a[i] ? a[i] : 0) + (b[i] ? b[i] : 0); 18 if (c[i]) { 19 t += c[i]; 20 } 21 c[i] = t % 10; 22 if (t / 10 >= 1) { 23 c[i + 1] = parseInt(t / 10); 24 } 25 i++; 26 if (i >= a.length && i >= b.length) { 27 break; 28 } 29 } 30 return new BigInteger(c); 31 }; 32 33 //将BigIneger实例用字符串显示 34 this.toString = function() { 35 return this.metaArray.reverse().join(""); 36 }; 37 38 function toMetaArray(charsequence) { 39 var array = charsequence.split("").reverse(); 40 for (var i = 0; i < array.length; i++) { 41 array[i] = parseInt(array[i]); 42 } 43 return array; 44 } 45 } 46 47 function fib(n) { 48 var a = new BigInteger(1); 49 var b = new BigInteger(1); 50 var c; 51 for (var i = 0; i < n - 2; i++) { 52 c = a.add(b); 53 a = b; 54 b = c; 55 } 56 return c; 57 } 58 59 console.log(fib(1000).toString());
为了计算方便，在转换成数组时，数组逆向存储。
再举一个例子，北京大学poj第一道题目。链接地址：http://poj.org/problem?id=1001，题目如下：
Description
Input
Output
Sample Input
95.123 12 0.4321 20 5.1234 15 6.7592 9 98.999 10 1.0100 12
Sample Output
548815620517731830194541.899025343415715973535967221869852721 .00000005148554641076956121994511276767154838481760200726351203835429763013462401 43992025569.928573701266488041146654993318703707511666295476720493953024 29448126.764121021618164430206909037173276672 90429072743629540498.107596019456651774561044010001 1.126825030131969720661201
本题目同样属于无限精度的大数运算，只不过不是加法运算，而是指数运算。如第一行输入，要计算的就是95.123的12次方。
由于这是一道算法题，且有时间限制，所以以下使用C语言实现：
1 #define ARRAY_SIZE 200 2 3 //函数原型声明 4 //计算整数n的m次方，在本题目中未使用到 5 void resolve1(int n, int m); 6 //计算某数a的m次方，数字a使用数组n表示，len表示数组中有效数字的个数，数字a包括p位小数 7 void resolve2(int n[], int len, int p, int m); 8 9 /* 10 题目编号：poi-1001 11 测试平台：Inter(R) Core i7-6700K 4.5G 4核心8线程，内存32GB，windows 10 64位企业版。 12 本解法未使用任何数据结构，仅数组而已，当然需要一点想象力，本解法未进行任何优化。 13 本解法的缺点是调用了strlen函数及strchr函数，这两个函数对字符数组都是会遍历的。 14 15 author:snow1k 16 version:1.0.0 17 18 */ 19 int main() { 20 //计算n^m，其中0.0 < n < 99.999，0 < m <= 25 21 //例如：int n = 95.123,m=12; 22 23 char s[20];//以字符串形式读入一行数据，即一个实数 24 int n[20];//将对应读入的一个字符串数字转换为整数数组存储，每个数组元素存储一位数字 25 int m;//指数。即读入的每行数字的第2个数字，整数 26 27 //循环获取输入 28 while(scanf("%s %d", s, &m) != EOF) { 29 //若有小数点，去掉小数点的前缀0，去掉小数点的后缀0，去掉小数点，记录小数位数 30 int len = strlen(s);//字符串长度，strlen是通过遍历获取长度 31 //如果s为char[]类型，则要通过strchr(s,‘.‘)-s来获取字符在字符串中的位置 32 int dotIdx = strchr(s, ‘.‘) - s; //小数点位置 33 int lft = 0; //左指针 34 int rgt = len - 1; //右指针 35 36 while(lft < rgt) { //去除前缀0和小数点，左指针向右前进到第一个有效数字 37 if(s[lft] == ‘0‘ || s[lft] == ‘.‘) { 38 lft++; 39 } else { 40 break; 41 } 42 } 43 44 if(dotIdx >= 0) { //如果存在小数点 45 while(rgt > lft) { //去除后缀0和小数点，右指针向左前进到第一个有效数字 46 if(s[rgt] == ‘0‘ ) { 47 rgt--; 48 } else if(s[rgt] == ‘.‘) { 49 rgt--; 50 break; 51 } else { 52 break; 53 } 54 } 55 } 56 57 //小数位数，精度 58 int precision = rgt - dotIdx; 59 if(precision < 0) { 60 precision = 0; 61 } 62 63 //此时，右指针指向右侧第一个有效数字，左指针指向左侧第一个有效数字 64 int ct = 0;//有效数字个数 65 while(rgt >= lft) { 66 if(s[rgt] != ‘.‘) { 67 n[ct++] = s[rgt] - 48; 68 } 69 rgt--; 70 } 71 resolve2(n, ct, precision, m); 72 } 73 return 0; 74 } 75 76 77 //计算n^m，即整数n的m次方 78 void resolve1(int n, int m) { 79 //对于本题目来说，最长6位，此处定义了20位 80 int arr[20]; 81 //乘数有效位数定位索引 82 int idx = 0; 83 84 while(n > 0) { 85 arr[idx++] = n % 10; 86 n /= 10; 87 } 88 89 resolve2(arr, idx, 0, m); 90 } 91 92 93 //len：数组n中有效数字个数，m:指数，p:小数精度，即小数位数 94 void resolve2(int n[], int len, int p, int m) { 95 ////////////////// 96 //被乘数数组。必须是static类型的，如果不是static，则是存放在堆内存中，堆内存容量有限，容易溢出 97 static int arr1[ARRAY_SIZE]; 98 arr1[0] = 1; 99 //被乘数数组有效位数定位索引 100 int arr1_idx = 0; 101 int *p1 = arr1; 102 103 ////////////////// 104 //结果数组 105 static int arr3[ARRAY_SIZE]; 106 //结果数组有效位数定位索引 107 int arr3_idx = -1; 108 int *p3 = arr3; 109 110 //计算n^m 111 for(int i = 0; i < m; i++) { 112 for(int k = 0; k < len; k++) { //乘数，最多6位 113 for(int j = 0; j <= arr1_idx; j++) { //被乘数，位数不定 114 if(arr3_idx < j + k) { 115 arr3_idx++; 116 *(p3 + arr3_idx) = 0; 117 } 118 119 *(p3 + j + k) += *(p1 + j) * n[k]; 120 121 if(*(p3 + j + k) >= 10) { 122 if(arr3_idx < j + k + 1) { 123 arr3_idx++; 124 *(p3 + arr3_idx) = 0; 125 } 126 127 *(p3 + j + k + 1) += *(p3 + j + k) / 10; 128 *(p3 + j + k) = *(p3 + j + k) % 10; 129 } 130 } 131 } 132 133 134 //将被乘数与结果交换 135 int *p = p1; 136 p1 = p3; 137 p3 = p; 138 139 arr1_idx = arr3_idx; 140 arr3_idx = -1; 141 142 } 143 144 //显示最终结果 145 if(arr1_idx < p * m) {//如果结果为小于0的小数，则补小数点和0 146 printf("."); 147 for(int i = 0; i < p * m - arr1_idx - 1; i++) { 148 printf("0"); 149 } 150 } 151 152 153 for(int i = arr1_idx; i >= 0; i--) { 154 if(i == p * m - 1) { 155 printf("."); 156 } 157 printf("%d", *(p1 + i)); 158 } 159 160 printf("\n"); 161 }
若有其它建议，欢迎在下留言。
-----完------
原文：https://www.cnblogs.com/viogel4/p/14633825.html