教你用typescript类型来推算斐波那契

目录
  • 写在前面
  • 斐波那契
  • 实现逻辑
    • 第一个问题:第0和第1个数返回自身
    • 第二个问题:某个数等于前两个数相加
    • 第三个问题:推算一个数需要循环或者递归得到前两个值
    • 第四个问题
    • 结论
  • 解决todo
    • +1操作
    • 数字转array
    • 非负数判断
  • 实现斐波那契
  • 总结

写在前面

本文执行环境typescript,版本4.5.4

斐波那契

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

  • 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>; // 2

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

这个就开始麻烦了,因为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]['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

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

实现斐波那契

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

type ArrOf<T extends number, P extends Array<0> = []> = {
    ['loop']: ArrOf<T, [...P, 0]>;
    ['result']: P;
}[P['length'] extends T ? 'result' : 'loop'];
// 第8行提示结果可能不是array
type ArrFrom<T> = T extends Array<T> ? T : T;

type ADD<A extends number, B extends number> = [...ArrFrom<ArrOf<A>>, ...ArrFrom<ArrOf<B>>]['length'];
// 第23行提示结果可能不是number
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;

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

总结

到此这篇关于用typescript类型来推算斐波那契的文章就介绍到这了,更多相关typescript推算斐波那契内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 一起来学习TypeScript的类型

    目录 前言 一.类型声明 二.类型 1.number 2.string 3.boolean 4.字面量 5.联合类型 6.any 7.unknown 8.void 9.never 10.object 11.array 12.tuple 13.枚举enum 14.其他 总结 前言 TypeScript学习笔记第一部分,关于TS的类型声明以及基本类型. 一.类型声明 类型声明 类型声明是TS非常重要的一个特点 通过类型声明可以指定TS中变量(参数.形参)的类型 指定类型后,当为变量赋值时,TS编译器

  • TypeScript基础类型介绍

    目录 1.基础类型 2.对象类型 2.1数组 2.2元组 2.3对象 3.类型推断 3.1类型联合中的类型推断 3.2上下文类型 4.类型断言 TS 的静态类型可以人为的分为两类: 基础类型:像布尔值(boolean).数字(number).字符串(string).Any(任意类型).Void(无类型).Null. Undefined.Never(无值类型) 对象类型:像数组.函数.对象.枚举.元组. 1.基础类型 TS的类型定义主要通过以下示例代码中演示的方式进行定义: ;(function

  • TypeScript枚举类型

    目录 1.概述 2.数字枚举 2.1反向映射 3.字符串枚举 4.const枚举 5.总结 1.概述 所谓的枚举类型就是为一组数值赋予名字. enum类型在C++.Java语言中比较常见,TypeScript在JavaScript原有的类型基础上也增加了enum类型. 比如我们需要定义一组角色,需要使用数字表示,就可以使用如下代码定位: enum role{ STUDENT, TEACHER, ADMIN } 上面代码中我们定义了role为一个枚举类型,这个里面有是三个值,TypeScript会

  • TypeScript 映射类型详情

    目录 1.映射类型(Mapped Types) 2.映射修饰符(Mapping Modifiers) 3.通过 as 实现键名重新映射(Key Remapping via as) 4.深入探索(Further Exploration) 前言: TypeScript 的官方文档早已更新,但我能找到的中文文档都还停留在比较老的版本.所以对其中新增以及修订较多的一些章节进行了翻译整理. 本篇翻译整理自 TypeScript Handbook 中 「Mapped Types」 章节. 本文并不严格按照原

  • 详解TypeScript的基础类型

    目录 布尔类型 数字类型 字符串类型 字符串和数字进行拼接 undefined和 null 数组类型 元组类型 枚举类型 any类型 void类型 联合类型 总结 布尔类型 // 布尔类型--->boolean // let 变量名:数据类型 = 值 let flag: boolean = true; console.log(flag) 数字类型 // 数字类型--->number let a1: number = 10 // 十进制 let a2: number = 0b1010 // 二进

  • TypeScript常见类型及应用示例讲解

    目录 常见类型(Everyday Types) 原始类型: 数组(Array) any noImplicitAny 变量上的类型注解(Type Annotations on Variables) 函数(Function) 参数类型注解(Parameter Type Annotations) 返回值类型注解(Return Type Annotations) 匿名函数(Anonymous Functions) 对象类型(Object Types) 可选属性(Optional Properties)

  • 教你用typescript类型来推算斐波那契

    目录 写在前面 斐波那契 实现逻辑 第一个问题:第0和第1个数返回自身 第二个问题:某个数等于前两个数相加 第三个问题:推算一个数需要循环或者递归得到前两个值 第四个问题 结论 解决todo +1操作 数字转array 非负数判断 实现斐波那契 总结 写在前面 本文执行环境typescript,版本4.5.4 斐波那契 虽然大家都熟悉斐波那契了,还是简单的说说吧,一个知名的数学数列,地推方式如下 Fib(0) = 0 Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2)

  • 基于使用递归推算指定位数的斐波那契数列值的解决方法

    昨天面试遇到这样的一道题目:1,1,2,3,5,8,13,21...,请问第30位的值是多少? 代码实现如下: 复制代码 代码如下: //1,1,2,3,5,8,13,21.......第30个是多少?     //使用递归计算指定位数的斐波那契数列值     //Fn=F(n-1)+F(n-2)     public static int GetFibonacciNumber(int index)     {         if(index<0||index==0)throw new Exc

  • C#实现斐波那契数列的几种方法整理

    什么是斐波那契数列?经典数学问题之一:斐波那契数列,又称黄金分割数列,指的是这样一个数列:1.1.2.3.5.8.13.21.--想必看到这个数列大家很容易的就推算出来后面好几项的值,那么到底有什么规律,简单说,就是前两项的和是第三项的值,用递归算法计第50位多少. 这个数列从第3项开始,每一项都等于前两项之和. 斐波那契数列:{1,1,2,3,5,8,13,21...} 递归算法,耗时最长的算法,效率很低. public static long CalcA(int n) { if (n <=

  • C语言数据结构递归之斐波那契数列

    C语言数据结构递归之斐波那契数列 因为自己对递归还是不太熟练,于是做POJ1753的时候就很吃力,就是翻棋子直到棋盘上所有棋子的颜色一样为止,求最少翻多少次,方法是枚举递归.然后就打算先做另一道递归的题(从数组中取出n个元素的组合),但是同样在递归的问题上不太理解.好吧,于是复习CPP,在第229页的时候,看到了斐波那契数列,回想起之前做过的一道题目,发现可以用递归的方法来做.于是决定优化一下之前的代码. 以下这段摘自<C primer plus> 斐波那契数列的定义如下:第一个和第二个数字都

  • C语言求Fibonacci斐波那契数列通项问题的解法总结

    一:递归实现   使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1. 二:数组实现   空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快. 三:vector<int>实现   时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源. 四:queue<int>实现   当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int&g

  • 求斐波那契(Fibonacci)数列通项的七种实现方法

    一:递归实现使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1.二:数组实现空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快.三:vector<int>实现时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源.四:queue<int>实现当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了,

  • 如何使用Python实现斐波那契数列

    斐波那契数列(Fibonacci)最早由印度数学家Gopala提出,而第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci,斐波那契数列的定义很简单,用数学函数可表示为: 数列从0和1开始,之后的数由前两个数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34. 用 Python 实现斐波那契数列常见的写法有三种,各算法的执行效率也有很大差别,在面试中也会偶尔会被问到,通常面试的时候不是让你简单的用递归写写就完了,

  • php求斐波那契数的两种实现方式【递归与递推】

    本文实例讲述了php求斐波那契数的两种实现方式.分享给大家供大家参考,具体如下: 斐波那契数,亦称之为斐波那契数列(意大利语: Successione di Fibonacci),又称黄金分割数列.费波那西数列.费波拿契数.费氏数列,指的是这样一个数列:1.1.2.3.5.8.13.21.--在数学上,斐波那契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=Fn-1+Fn-2(n>=2,n∈N*),用文字来说,就是斐波那契数列列由 0 和 1 开始,之后的斐波那契数列系数就由之前的两数相

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

  • Python实现斐波那契数列的多种写法总结

    目录 1.for循环 2.while循环 3.使用递归 4.递归+for循环 5.递归+while循环 6.递归+定义函数+for循环 7.指定列表 趣方程求解 pandas 每日一练 斐波那契数列——经典例子,永不过时!!! 1.for循环 def fibonacci1(n): a, b = 0, 1 for i in range(n): a, b = b, a+b print(a) fibonacci1(3) 或 def fib1(w): a, b = 1, 1 for i in range

随机推荐