示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载导读本文围绕 type-challenges 仓库中的中等难度题目 04182斐波那契序列 / Fibonacci Sequence展开讲解如何纯粹依赖类型系统实现一个泛型FibonacciT输入一个数字T返回斐波那契数列中对应位置的数值。读完本文你将掌握类型层面的“递归 计数器”建模技巧理解如何用元组长度代替数字运算从而在 TypeScript 类型层面完成斐波那契、累加、比较等经典数值计算。一、题目要求与仓库定位本题的官方描述位于 questions/04182-medium-fibonacci-sequence/README.zh-CN.md核心要求只有一句话实现一个接收数字T的泛型FibonacciT并返回其对应的斐波那契数。题目难度标记为medium中等由作者 windliangGitHub 账号wind-liang贡献元数据可在 info.yml 中确认difficulty: medium title: Fibonacci Sequence author: github: wind-liang name: windliang斐波那契数列的起始序列由题目明确给出1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...注意这里的序列从 1 开始而非经典的 0, 1, 1, 2, ...即F(1) 1、F(2) 1、F(3) 2。题目给出的示例为type Result1 Fibonacci3 // 2 type Result2 Fibonacci8 // 21Fibonacci8 21与序列中的第 8 项21完全对应验证了该序列从 1 起步的定义。二、解题起点模板与测试用例2.1 模板文件题目提供的起始模板位于 template.ts内容极简type FibonacciT extends number anyT extends number说明输入被约束为数字字面量类型any是需要被替换掉的占位实现。2.2 测试用例测试用例位于 test-cases.tsimport type { Equal, Expect } from type-challenges/utils type cases [ ExpectEqualFibonacci1, 1, ExpectEqualFibonacci2, 1, ExpectEqualFibonacci3, 2, ExpectEqualFibonacci8, 21, ]四个用例覆盖了序列开头、关键示例与较大输入Fibonacci1应等于1、Fibonacci2应等于1、Fibonacci3应等于2、Fibonacci8应等于21。其中Equal与Expect来自type-challenges/utils其底层Equal实现可在 utils/index.d.ts 中看到是典型的基于函数签名逆变比较的类型等价判定export type EqualX, Y (T() T extends X ? 1 : 2) extends (T() T extends Y ? 1 : 2) ? true : false也就是说你的实现必须让Fibonacci8精确等于21这个数字字面量类型而非任何等价可赋值类型。三、核心难点类型系统里没有循环与算术要解决这道题必须先认清 TypeScript 类型系统的能力边界没有变量与循环类型层面无法写for、while或可变累加器只能靠递归类型与条件类型的分支。没有直接的算术运算T - 1、a b这类表达式在类型层面不存在数字字面量不能直接做加减。但有强大的结构化能力元组tuple是可递归分解的[any, ...Rest]可以剥离首元素元组的length可以“读出”一个数字。于是类型社区形成了一套约定俗成的“元组即数字”建模用元组的长度表示数字用“往元组里追加一个元素”模拟1用“剥离一个元素”模拟-1。四、基础工具用元组构建任意长度的计数序列实现斐波那契的前提是先有一个能按需生成指定长度元组的工具。这个工具可以命名为BuildTuple它接受一个数字N返回一个长度为N的元组type BuildTuple N extends number, Acc extends any[] [] Acc[length] extends N ? Acc : BuildTupleN, [any, ...Acc]其工作原理初始Acc为空元组[]length为0若Acc[length]已经等于目标N递归终止并返回Acc否则把any追加到Acc头部[any, ...Acc]使长度 1然后继续递归。例如BuildTuple3会依次生成[]→[any]→[any, any]→[any, any, any]最终返回长度为 3 的元组。这个工具是本题乃至后续“累加”型题目的地基。五、迭代式建模用元组做计数器推导斐波那契数5.1 思路斐波那契的递推关系是F(n) F(n-1) F(n-2)。类型层面无法直接做加法但可以用并行递推回避算术同时维护三个量——Prev前一个斐波那契数对应F(i-1)用元组表示Current当前斐波那契数对应F(i)用元组表示Counter迭代计数元组从[]表示下标 0增长到目标长度T。每一轮迭代即计数器长度 1我们都把Prev更新为旧的Current把Current更新为“Prev与Current拼接起来的元组”其长度恰好是两者长度之和即实现了F(i-1) F(i)的加法。当Counter的长度达到T时Current的长度就是答案。5.2 完整实现type BuildTuple N extends number, Acc extends any[] [] Acc[length] extends N ? Acc : BuildTupleN, [any, ...Acc] type Fibonacci T extends number, Counter extends any[] [], Prev extends any[] [], Current extends any[] [any] Counter[length] extends T ? Current[length] : FibonacciT, [any, ...Counter], Current, [...Prev, ...Current]关键点逐一拆解初始状态Counter []下标 0、Prev []长度 0代表“第 0 个数”、Current [any]长度 1代表F(1) 1。终止条件Counter[length] extends T成立时返回Current[length]。注意Counter从0开始递增因此当Counter长度等于T时我们恰好完成了T轮推导Current就是F(T)。递推步[any, ...Counter]让计数器长度 1Current成为新的Prev[...Prev, ...Current]拼接出长度为“Prev长度 Current长度”的新元组作为新的Current。5.3 用Fibonacci3走一遍推导轮次Counter 长度Prev 长度Current 长度说明初始001Prev[]Current[any]即F(1)1第 1 轮111新Prev为原Current长度 1拼接后Current长度 01 1即F(2)1第 2 轮212新Prev长度 1拼接后Current长度 11 2即F(3)2第 3 轮323终止条件触发返回Current[length] 3咦这里有个细节需要澄清Counter长度从 0 开始而序列下标从 1 开始。用Fibonacci3验证当Counter长度为 3 时返回的是Current长度 3但题目期望Fibonacci3 2岂不是对不上让我们重新精确推演初始Counter []长度 0Prev []长度 0Current [any]长度 1。此时Counter[length] 0不等于3进入递推。第 1 轮Counter长度 1Prev长度 1Current长度 1。此时 1 ≠ 3继续。第 2 轮Counter长度 2Prev长度 1Current长度 2。2 ≠ 3继续。第 3 轮Counter长度 3Prev长度 2Current长度 3。3 3终止返回3。这确实得到了 3 而非 2。说明上面 5.2 的写法需要调整Current的初值应代表F(1)而Counter的初值也应与序列下标对齐或者在终止判断上做偏移。正确的对齐方式是把Counter初始化为长度 1让“已推导到第 1 项”的状态与序列下标同步type Fibonacci T extends number, Counter extends any[] [any], Prev extends any[] [], Current extends any[] [any] Counter[length] extends T ? Current[length] : FibonacciT, [any, ...Counter], Current, [...Prev, ...Current]重新验证Fibonacci3初始Counter长度 1代表已推到F(1)Current长度 1即F(1)1。1 ≠ 3进入递推。第 1 轮Counter长度 2Prev长度 1Current长度 1即F(2)1。2 ≠ 3继续。第 2 轮Counter长度 3Prev长度 1Current长度 2即F(3)2。3 3返回Current[length] 2。✓再用Fibonacci1验证初始Counter长度 11 extends 1立即成立返回Current[length] 1。✓Fibonacci2初始 1 ≠ 2进入一轮后Counter长度 2、Current长度 1返回 1。✓Fibonacci8会经历 7 轮递推得到Current长度 21。✓ 与 test-cases.ts 中的全部断言一致。六、另一种范式从尾到头递归除了“计数器递增”的迭代式写法斐波那契也可以像普通递归那样从T递减到底但类型系统没有减法只能靠“剥离元组首元素”来模拟T-1。可以把T表示为一个元组然后递归地分解type Fib T extends any[], // 用元组表示目标下标 P extends any[] [], // F(n-2) 的长度 C extends any[] [any], // F(n-1) 的长度 N extends any[] [] // 当前已推进到的下标 T extends [...N, ...infer R] ? R extends [] ? C[length] : FibT, C, [...P, ...C], [any, ...N] : never这种写法把“还差多远”直接编码进元组结构里当T恰好等于[...N, ...[]]即N已经推进到与T等长时返回C[length]否则继续递推。它更贴近“递归 模式匹配”的直觉但可读性略逊于计数器版本理解时容易在infer R的匹配上绕弯。两种写法在类型计算层面等价选哪种取决于你更习惯哪种心智模型。七、复杂度、边界与扩展思考7.1 复杂度与 TypeScript 限制元组拼接[...Prev, ...Current]的时间与两个元组的长度之和成正比因此该实现的类型求值复杂度约为O(T²)随着T增大斐波那契元组呈指数增长实际开销增长很快。TypeScript 编译器对递归深度默认约 50 层与实例化数量有限制因此FibonacciT只能处理较小的T例如T 50。题目与测试用例均只覆盖到8完全在安全范围内。T extends number的约束意味着传入非数字或非字面量时会得到类型错误这也符合题目设计。7.2 复用价值本题用到的三个技巧在 type-challenges 的后续题目中反复出现BuildTuple式计数器是 07544-medium-construct-tuple 等“构造元组”题目的直接模板[...Prev, ...Current]拼接求和是 02257-medium-minusone、04425-medium-greater-than 等数值比较/运算题的核心手段尾递归 多参数累积是规避编译器递归深度限制、把递归改写成尾调用的通用范式。掌握了“元组长度即数字”“拼接即加法”“计数器递归”这三板斧类型层面的数值计算类题目基本都可以举一反三。八、总结题目 04182 表面上是“实现斐波那契”实质考察的是能否识别出类型系统没有算术与循环这个约束能否用元组长度建模数字、用拼接建模加法能否写出带累积状态的尾递归类型在类型层面完成递推。最终可通过测试用例的完整解法如下对应 template.ts 的替换实现type Fibonacci T extends number, Counter extends any[] [any], Prev extends any[] [], Current extends any[] [any] Counter[length] extends T ? Current[length] : FibonacciT, [any, ...Counter], Current, [...Prev, ...Current]将这段代码写入 template.ts 后配合 test-cases.ts 中基于type-challenges/utils的Equal/Expect断言utils/index.d.ts即可完整验证Fibonacci1、Fibonacci2、Fibonacci3、Fibonacci8四个用例。这道题是通往类型级算法世界的一扇门掌握了元组计数与递归递推你就能继续挑战减法、比较、排序乃至更复杂的类型级算法题。赞分享示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载相关推荐Type Challenges项目中的斐波那契序列类型实现解析Type Challenges项目中的斐波那契序列类型实现解析 在TypeScript类型编程领域Type Challenges项目提供了一个极佳的平台来练习示例工程从数学到类型Type-Challenges斐波那契数列的优雅实现从数学到类型Type Challenges斐波那契数列的优雅实现 你是否曾困惑于如何在TypeScript类型系统中实现数学逻辑当普通函数轻松解决的斐波那契示例工程用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort 导读 本篇实战项目来自 curriculum htt文档教程教育上一篇终极指南解决LitGPT中Llama 3.1的RoPE实现问题从定位到修复的完整步骤下一篇go-langserver高级配置指南定制属于你的Go开发环境创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考