用 typescript 类型来推算斐波那契

更新日期: 2022-08-10阅读: 731标签: 算法
作者:东东么么哒

写在前面 本文执行环境typescript,版本4.5.4

不使用typescript的计算能力,而通过类型来推算斐波那契数列

斐波那契

虽然大家都熟悉斐波那契了,还是简单的说说吧,一个知名的数学数列,地推方式如下

  • Fib(0) = 0
  • Fib(1) = 1
  • Fib(n) = Fib(n-1) + Fib(n-2)

最后得出来的数列就是

0 1 1 2 3 5 8 13 21 34 55 89 ...

实现逻辑

介绍完斐波那契后,再来看看 typescript 类型推算要解决核心点

  • 第 0 和第 1 个数返回自身
  • 某个数等于前两个数相加
  • 推算一个数需要循环或者递归得到前两个值
  • 输入的只能是数字,且不能是负数

分析完我们再来看看 typescript 能够提供哪些,缺少哪些?

第一个问题:第 0 和第 1 个数返回自身

这个满足,可以通过 extends 来实现

type GetSelf<T> = T extends 0 | 1 ? T : never; // 测试
type Test0 = GetSelf<0>; // 0
type Test1 = GetSelf<1>; // 1
type Test2 = GetSelf<2>; // never

第二个问题:某个数等于前两个数相加

这个就开始麻烦了,因为 typesript 中是没有加法运算的,也就是说 1 + 2 = 的结果 typescript 并不知道,所以列一个 todo

  • 需要实现完整的加法

第三个问题:推算一个数需要循环或者递归得到前两个值

看看 typescript 中模拟递归的写法呢,是有的,比如实现一个链表,这个类型它将会一直递归下去,因为没有结束循环

type Node<T> = {
  val: T;
  next: Node<T>;
};

不过怎么跳出循环,另外我们需要的是一个值,而不是返回一个对象,再列一个 todo

  • 需要实现完整的递归

第四个问题:非负数

输入的只能是数字,且不能是负数

限定数字很好做,extends number 就可以判断了,判断负数呢?

负数和正数有啥区别呢?

负数多个符号显示,那改造成字符串后的长度和正数不等是吧,尝试

type len1 = "123"["length"]; // number
type len2 = number[]["length"]; // number;
type len3 = [1, 2, 3]["length"]; // 3
type len4 = [number, string, string]["length"]; // 3

字符串和未定义的数组的长度竟然无法推算,看起来只有元组是可以的。

负数比 0 小,可是 typescript 中没有比较大小的操作,再列一个 todo:

  • 需要实现非负数判断

结论

我们可以解决第一个问题,同时得知可以通过 length 来获取元组长度。

todo 如下:

  • 如何实现加法运算
  • 如何实现循环或者递归计算,并有跳出条件
  • 如何判断非负数

解决 todo

+1 操作

虽然上一轮大部分功能没有推算出来,但是得到一个有用的结论,元组是可以得到 length 的值。

那 +1 操作 是不是可以理解成 PUSH 操作 后拿出 length 了?尝试

type Push<T extends Array<number>, P extends number> = [...T, P];

type arr1 = [1, 2];
type arr2 = Push<arr1, 3>; // [1, 2, 3]
type len1 = arr1["length"]; // 2
type len2 = arr2["length"]; // 3

确实实现了 +1 操作 ,加法应该是可以解决了,+n 就是循环 n 次,结束条件就是结果为 n。

所以加法运算最后可以转成元组后计算长度,类似 JavaScript的Array(n).fill(0) ,第一步实现 数字转 array


递归实现数字转 array

类似递归的方式实现


需要循环自身,需要记录循环后的值,最后再条件达成后返回这个值,同理 fib(n) = fib(n-1) + fib(n-2) 也需要类似的递归实现。

我们用 loop 来存递归操作,用result来存返回值,循环结束的条件是 数组的长度等于传入的值 ,而泛型返回的是一个对象,可以通过 key 去获取对应的 value

type ArrOf<T extends number, P extends Array<0> = []> = {
  ["loop"]: ArrOf<T, [...P, 0]>;
  ["result"]: P;
}[P["length"] extends T ? "result" : "loop"];

type arrof1 = ArrOf<5>; // [0, 0, 0, 0, 0]

因为我们需要递归后再跳出条件,最后返回值,所以可以构造一个对象后获取 key,而 key 就是跳出循环的关键,跳出循环的判断就是 元组的长度等于输入的数

加法运算

基于以上,我们可以得到 add 的完整实现了

type ADD<A extends number, B extends number> = [
  ...ArrOf<A>,
  ...ArrOf<B>
]["length"];

type add1 = ADD<3, 4>; // 7

虽然可以推算出结果,但是报了一个 warning

A rest element type must be an array type.

可能他推算不出来返回的是 array,所以需要我们声明 ArrOf 返回的数都是 array,类似 Array.from

type ArrFrom<T> = T extends Array<T> ? T : T;

type ADD<A extends number, B extends number> = [
  ...ArrFrom<ArrOf<A>>,
  ...ArrFrom<ArrOf<B>>
]["length"];

加法和递归都被搞定了,接下来看看非负数的问题

非负数判断

再重新看看之前的分析,负数有什么特殊的地方, 负数多个符号显示,且符号固定是第一位

type str11 = "abcde";
type str12 = str11[0]; // string

看来并不能通过下标来取巧,那我们只能获取第一位判断是否为 "-"号,这时候就需要用上 infer 占位来赋值变量并获取

type getFirst<T extends string> = T extends `${infer P}${string}` ? P : T;

type str11 = 'abcde';
type str12 = getFirst<str11>; // a

所以我们可以把数字转换字符串后求得符号,然后得出负数的判断,这里需要提前把传入的数字转成字符串,可以通过 模板字符串 来实现

type FirstStr<T extends number> = `${T}` extends `${infer P}${string}` ? P : T;

type isFu<T extends number> = FirstStr<T> extends '-' ? true : false;

type isFu1 = isFu<0>; // false
type isFu2 = isFu<12>; // false
type isFu3 = isFu<-6>; // true
type isFu4 = isFu<-0>; // true

实现斐波那契

再次回顾前面提到的核心点

  • 第 0 和第 1 个数返回自身
  • 某个数等于前两个数相加
  • 推算一个数需要循环或者递归得到前两个值
  • 输入的只能是数字,且不能是负数

所有的部分都就绪了,实现一下完整的斐波那契!

实现加法

  • 通过递归实现数字转元组
  • 两个元组合并到一个元组
  • 通过length求长度
type ArrOf<T extends number, P extends Array<0> = []> = {
    ['loop']: ArrOf<T, [...P, 0]>;
    ['result']: P;
}[P['length'] extends T ? 'result' : 'loop'];

type ArrFrom<T> = T extends Array<T> ? T : T;

type ADD<A extends number, B extends number> = [
    ...ArrFrom<ArrOf<A>>,
    ...ArrFrom<ArrOf<B>>
]['length'];

type NumberFrom<T> = T extends number ? T : T & number;

type ADD2<A extends number,
    B extends number
> = NumberFrom<ADD<A, B>>;

实现非负数判断

  • 将输入的数字转字符串
  • 获取首位符号,判断是否等于符号 "-"
type FirstStr<T extends number> = `${T}` extends `${infer P}${string}` ? P : T; // 添加负数判断
type isFu<T extends number> = FirstStr<T> extends '-' ? true : false;

实现斐波那契函数

  • 第 0 和第 1 个数返回自身
  • 通过递归实现 Fib(n) = Fib(n-1) + Fib(n-2)
type FIB<T extends number,
    A extends number = 0,
    B extends number = 1,
    N extends number = 0
> = isFu<T> extends true
    ? never
    : T extends 0 | 1
? T
: {
    ['loop']: FIB<T, B, ADD2<A, B>, ADD2<N, 1>>;
    ['result']: B;
}[T extends ADD2<N, 1> ? 'result' : 'loop'];

测试

type FIFU1 = FIB<-6> // never
type FI0 = FIB<0> // 0
type FI1 = FIB<1>; // 1
type FI2 = FIB<2>; // 1
type FI3 = FIB<3>; // 2
type FI4 = FIB<4>; // 3
type FI5 = FIB<5>; // 5
type FI6 = FIB<6>; // 8
type FI7 = FIB<7>; // 13
type FI8 = FIB<8>; // 21
type FI9 = FIB<9>; // 34


链接: https://fly63.com/article/detial/11993

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!