4182-实现斐波那契序列

题目描述

Implement a generic Fibonacci<T> takes an number T and returns it's corresponding Fibonacci number (opens new window).

The sequence starts: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

For example

type Result1 = Fibonacci<3>; // 2
type Result2 = Fibonacci<8>; // 21

分析

这题也是，绝了。

由于 ts 本身不支持加减乘除这些运算，所以想要实现斐波那契，本质还是实现加法后进行递归，即可得到结果。

在 ts 中如何做加法？其实也蛮简单的，构造两个指定长度的元组，将其合并，其长度就是加法的结果。

type ArrWithLength<Length extends number, Arr extends any[] = []> =
  // 元组长度等于目标长度时
  Arr['length'] extends Length
    ? // 返回元组
      Arr
    : // 否则，向 Arr 中增加一个元素，并递归处理新数组
      ArrWithLength<Length, [...Arr, any]>;

// 两者合并得到的元组的长度，就是加法的结果
type Add<A extends number, B extends number> = [
  ...ArrWithLength<A>,
  ...ArrWithLength<B>,
]['length'];

对于斐波那契，js 的实现如下：

function fcc(d) {
  if (d === 1 || d === 2) {
    return 1;
  }
  return fcc(d - 1) + fcc(d - 2);
}

对于 ts 来讲，就是不断构建长度为 d-1 和 d-2 的元组，其和就是要求的斐波那契值。

// 构建长度为 Length 的元组
type ArrWithLength<Length extends number, Arr extends any[] = []> =
  // 元组长度等于目标长度时
  Arr['length'] extends Length
    ? // 返回元组
      Arr
    : // 否则，向 Arr 中增加一个元素，并递归处理新数组
      ArrWithLength<Length, [...Arr, any]>;

// 题目2257-实现减一的实现
type MinusOne<T extends number, Arr extends any[] = []> =
  // 如果 Arr 加上一个元素的长度等于目标长度
  [...Arr, 1]['length'] extends T
    ? // 那么此时 Arr 的长度就是要求的减一
      Arr['length']
    : // 否则继续增加 Arr 长度
      MinusOne<T, [...Arr, 1]>;

// 构造斐波那契的 Arr
type FibonacciArr<T extends number> =
  // 加 [] 包裹的原因同 3376 实现中序遍历的一样，防止 ts 报无穷的递归
  [T] extends [1 | 2]
    ? ArrWithLength<1>
    : [...FibonacciArr<MinusOne<T>>, ...FibonacciArr<MinusOne<MinusOne<T>>>];

type Fibonacci = FibonacciArr['length'];

以上就是 ts 完全复刻 js 实现的一种解法。整体来讲相对直观一点。

也可以换一种更适合 ts 的解法，自底向上计算：

先计算 f(3)，再计算 f(4)，不断往上计算，直到计算到目标值。

题解

type Fibonacci<
  T extends number,
  // 存放当前计算到第几了，默认 1
  Arr extends number[] = [1],
  // 存放当前的结果
  Cur extends number[] = [1],
  // 存放下一个值
  Next extends number[] = [1],
> = Arr['length'] extends T
  ? Cur['length']
  : Fibonacci<T, [...Arr, 1], Next, [...Cur, ...Next]>;

这种方式从递归的层数上，会一定程度上少于上面完全复刻 js 的方案，就是中间参数比较多，理解起来略有困难。

知识点

1. 就还挺离谱的