Newman-Conway 序列详解：从递推定义到 O(n) 动态规划实现（cosmos 开源算法库）

教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载Newman-Conway 序列Newman-Conway Sequence是一类以自身先前项为索引的自引用递推序列由递推关系 P(n) P(P(n-1)) P(n − P(n-1)) 定义其数值增长率低于对数级在算法分析中常用于演示递归爆栈问题与动态规划记忆化优化。本文以 cosmos 开源算法库 中 newman_conway 目录下的文档与源码为主线完整推导递推公式、梳理序列模式并给出 C/C 的朴素递归、自底向上 DP 与单值查询三种可运行实现及复杂度对比。递推定义与数学背景递推关系Recurrence RelationNewman-Conway 序列的递推定义非常简洁由 Morris Newman 与 John Conway 提出基础条件与递推式如下P(1) 1 P(2) 1 P(n) P( P(n-1) ) P( n - P(n-1) ) n ≥ 3递推式的核心在于自引用索引第 n 项的值不仅依赖于前一项的值还以「前一项的值」本身作为下标去查询序列。这种值即下标的双层寻址结构使其无法像普通一阶递推那样直接由前几项线性推出必须依赖完整的已知项集合这正是它适合演示动态规划的原因。序列模式Pattern按照上述递推式展开从第 1 项开始的前若干项为1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ...该模式由仓库中 newman_conway_sequence.c 的实际运行输出验证程序默认打印前 20 项结果为1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12与递推定义完全一致。观察该序列可以发现几个重要性质增长缓慢P(n) 的增长速度远低于线性约为P(n) ≈ n / log₂ n前 20 项的最大值仅为 12大量重复值值 1、2、4、8 等 2 的幂及其附近的值会连续重复多次如 8 连续出现 4 次体现了递推式中P(n-1)与n - P(n-1)两分支取值频繁落入同一小区间与 Golomb 序列、Conway 数列相关该序列常与著名的 Hofstadter-Conway $10000 序列一同讨论二者共享类似的自引用结构且都与n/2附近的密度函数有关。复杂度分析对于计算第 n 个 Newman-Conway 数在自底向上动态规划策略下Time Complexity: O(n) Space Complexity: O(n)时间 O(n)只需从第 3 项迭代到第 n 项每项做一次常数时间的数组双重索引加法空间 O(n)需要长度为 n1 的数组保存全部已计算项因为递推式的索引是动态的P(n-1)的值决定了第二个下标无法只保留常数个最近项。注意如果采用朴素的直接递归实现每次调用会展开成两棵指数级递归树时间复杂度退化到O(2^n)且大量重复计算P(n-1)。因此上述 O(n) 复杂度特指 DP/记忆化实现详见下文对比。朴素递归实现及其问题仓库中的 newman_conway_recursion.cpp 直接按递推式进行递归是对定义最忠实、但效率最低的写法unsigned int NewmanConwaySequence::calculateNewmanConwaySequenceTermRecur(unsigned int n) { if (n 1 or n 2) return 1; else return calculateNewmanConwaySequenceTermRecur(calculateNewmanConwaySequenceTermRecur(n - 1)) calculateNewmanConwaySequenceTermRecur(n - calculateNewmanConwaySequenceTermRecur(n - 1)); }该实现存在两个致命问题指数级重复计算calculateNewmanConwaySequenceTermRecur(n - 1)在表达式中被多次重复调用且每次外层调用都会递归触发两棵子调用树调用次数呈指数增长n 稍大如 n40即难以在合理时间内完成函数调用开销巨大即使忽略重复计算每个节点的多层嵌套调用也带来极高的栈开销。因此该实现仅适合教学演示递推式的原貌实际计算必须使用 DP。自底向上动态规划实现推荐生成前 n 项C 实现newman_conway_sequence.c 使用定长数组自底向上递推并打印全部项void newman_conway_sequence(int number_of_terms) { int array[number_of_terms 1]; array[0] 0; array[1] 1; array[2] 1; int i; for (i 3; i number_of_terms; i) array[i] array[array[i - 1]] array[i - array[i - 1]]; for (i 1; i number_of_terms; i) printf(%d , array[i]); printf(\n); }实现要点array[0] 0作为哨兵占位array[1] array[2] 1对应递推基础条件保证下标从 1 开始与数学定义对齐递推循环体中array[array[i-1]]与array[i - array[i-1]]正是递推式P(P(n-1)) P(n - P(n-1))的直接翻译main中默认以number_of_terms 20演示可直接编译运行验证上文输出。生成前 n 项C 实现newman_conway_sequence.cpp 使用std::vector动态扩容避免 VLA更符合 C 工程实践std::vectorint NewmanConwaySequence(int number) { std::vectorint arr(number 1); arr[0] 0; arr[1] 1; arr[2] 1; for (int i 3; i number; i) arr[i] arr[arr[i - 1]] arr[i - arr[i - 1]]; return arr; }单值查询与整序列生成二合一DP 版code/dynamic_programming/src/newman_conway/newman_conway_dp.cpp 将 Newman-Conway 序列同时收录于动态规划目录提供两种模式传入flag true生成并打印包含 n 个元素的完整序列传入flag false只打印第 n 项的值ncs[n]。两种模式共享同一段自底向上递推循环unsigned int ncs[n 1]; ncs[0] 0; ncs[1] 1; ncs[2] 1; for (int i 3; i n; i) ncs[i] ncs[ncs[i - 1]] ncs[i - ncs[i - 1]];由于计算第 n 项必然依赖之前所有项两种模式的复杂度均为 O(n) 时间、O(n) 空间单值查询并不比全序列生成更省——这正是该序列区别于普通递推的特殊之处。运行与验证C 版本gcc newman_conway_sequence.c -o newman_conway ./newman_conway # 输出1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12C 版本递归版与 DP 版均以标准输入读取 ng newman_conway_dp.cpp -o newman_conway_dp ./newman_conway_dp # 依次输入 n 与模式标志非零生成整序列0 查询单值自校验将 DP 输出与递推定义手算对比前 10 项必须满足1, 1, 2, 2, 3, 4, 4, 4, 5, 6同时可验证P(n) ≤ n恒成立因为索引始终落在已计算区间内。总结Newman-Conway 序列是理解自引用递推 动态规划的经典范例实现方式对应源码时间复杂度空间复杂度适用场景朴素递归newman_conway_recursion.cppO(2^n)指数O(n)递归栈教学演示递推原貌自底向上 DPCnewman_conway_sequence.cO(n)O(n)生成序列、验证模式自底向上 DPCnewman_conway_sequence.cppO(n)O(n)工程化生成序列DP 单值/整序列二合一newman_conway_dp.cppO(n)O(n)按需查询第 n 项或全序列实践建议凡涉及 Newman-Conway 类自引用递推包括 Golomb、Hofstadter 等相似数列一律优先使用自底向上 DP避免朴素递归的指数级灾难。相关源码与文档位于 code/mathematical_algorithms/src/newman_conway 与 code/dynamic_programming/src/newman_conway可供进一步阅读与运行验证。赞分享教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载相关推荐LeetCode 338 Counting Bits 详解从 O(n log n) 到 O(n) 的五种解法与动态规划推导LeetCode 338 Counting Bits 详解从 O n log n 到 O n 的五种解法与动态规划推导 导读 本文基于当前仓库中 LeetCo示例工程教程LeetCode-Book 精讲最长递增子序列LIS——从 O(N²) 动态规划到 O(NlogN) 二分优化LeetCode Book 精讲最长递增子序列LIS——从 O N² 动态规划到 O NlogN 二分优化 本文以 LeetCode Book 仓库中《K示例工程Cosmos 仓库中的 Coin Change 动态规划解法从递推公式到多语言实现Cosmos 仓库中的 Coin Change 动态规划解法从递推公式到多语言实现 导读 本文以 coin_change 目录 https://link.gi教程示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考