面试官:怎么求斐波那契数列的第 9292 项?

大数相加算法题

Posted by MurphyChen on April 4, 2022

模拟一道面试题。

面试官:怎么求斐波那契数列的第 9292 项?

初看题目,求斐波那契数列啊,这谁不会?但是要求的是第 9292 项,你心里想了一下,这个数肯定很大,结果会溢出的。但这在面试,总不能不写吧,不然让面试官以为你不会写。毕竟只要不写递归,都能算出来,求 9292 项,也就迭代计算几千次。于是你写出了以下代码:

1
2
3
4
5
6
7
8
9
10
function Fib(n) {
  if (n < 2) return n
  let fib = [0, 1]
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2]
  }
  return fib[n]
}

console.log(Fib(9292))

结果一跑,不出所料,输出结果是 Infinity。JS 中整数超过其最大可表示的数字(Number.MAX_VALUE)之后,就会变为 Infinity

继续思考,面试官绝不会想要这样的结果。你心中一想,有没有可能是要求取模之后的值,很多算法题中都要求结果 mod(1e9+7),有了,每次计算和的时候都对结果去取一次模!

1
2
3
4
5
6
7
8
9
10
function Fib(n) {
  if (n < 2) return n
  let fib = [0, 1]
  for (let i = 2; i <= n; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % (1e9 + 7)
  }
  return fib[n]
}

console.log(Fib(9292))

运行和,上述代码输出了 295902189,好,这下稳了。你自信的把代码和运行结果交给面试官看。

面试官:你能不取模吗?直接得到完整的结果。

什么?不取模,那整数不是溢出了吗?又想了一会,你想到了 ES2020 中新增的数据类型 BigInt,把运算全部转为 BigInt 之间的运算,不就不会溢出了。一顿操作,你写出了以下代码。

1
2
3
4
5
6
7
8
9
function Fib(n) {
  let fib = [0n, 1n]
  for (let i = 2; i <= n; i++) {
    fib[i] = BigInt(fib[i - 1]) + BigInt(fib[i - 2])
  }
  return fib[n].toString()
}

console.log(Fib(9292))

这次成功输出了完整的结果,即 366...579(中间的数字就不列出了)。肯定考知不知道 BigInt 这个新特性,你满怀信心的交给面试官看。

面试官:结果对了,那你能不能不使用 BigInt 呢?

啊?这次彻底懵了,不允许用 BigInt,那不就是要求手写一个 BigInt。面试进展到这里,你终于懂了,原来面试官要你写的是 BigInt 的原理实现。

不过,我们到不需要实现 BigInt 的所有运算和特性,仅仅限于这题中,我们只要写出 大数加法 即可。让斐波那契数列求和的过程中,结果不溢出。

大数加法的思想也不难,其实就是十进制加法法则: 十进制整数相加,逢 10 进 1

我们用total 来表示 两个对应位置的数的和再加上来自低位的进位

1
let total = carry + +num1[i] + +num2[i]

一个 carray 表示进位,将参与下次一计算。

1
carry = (total / 10) >>> 0 // 右移取整

相加结果的本位 就是 (total % 10)

整个过程进行循环,循环周期是较长数字字符串(这里用字符串模拟了,也可以用数组模拟)的长度。最终代码和详细注释如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 模拟大数加法
var addBigNumber = function (num1, num2) {
  //哪个小拼接哪个,从而保证两者长度相同
  if (num1.length > num2.length) [num1, num2] = [num2, num1]
  let m = num2.length - num1.length
  for (let i = 0; i < m; i++) {
    num1 = '0' + num1
  }
  let ans = '' // 记录相加结果
  let carry = 0 // 代表进位,初始值 0
  // 从后往前遍历,低位到高位,逢 10 进 1
  for (let i = num2.length - 1; i >= 0; i--) {
    // 总和:没算进位的两字符串对应位置数字与进位相加后的和
    // 这里的 + 是正,字符转数字,作用同 Number()
    let total = carry + +num1[i] + +num2[i]
    // 本位 = 总和 % 10
    ans = (total % 10) + ans
    // 进位 = (总和 / 10) 向下取整,参与下一次运算
    carry = (total / 10) >>> 0
  }
  // 判断最高位是否有进位,有进位则在前面加进位
  if (carry >= 1) {
    ans = carry + ans
  }
  return ans
}

function Fib(n) {
  if (n < 2) return n
  let fib = ['0', '1'] // 全都变为数字字符串
  for (let i = 2; i <= n; i++) {
    // 这里的加法要用大数加法实现
    fib[i] = addBigNumber(fib[i - 1], fib[i - 2])
  }
  return fib[n]
}

console.log(Fib(9292))

以上代码没有使用 BigInt,运行的完整结果是:

image.png

最后,你和面试官都欣慰的笑了。原来这题考察的就是 大数加法,也就是模拟 BigInt!现在你也可以试着模拟一下乘法、除法等等。