※ 引述《TimcApple (肥鹅)》之铭言： : https://reurl.cc/N6zekQ : 一共 10 题和 2021 有关的题目 : 祝各位新年快乐ow o : 推 MisatoMitumi: Q3先给一个157步的参考路径（不过确定有更佳解） 01/03 19:57 : → MisatoMitumi: （只列出取阶乘的数字）2021->26->2116->973->268-> 01/03 19:58 : → MisatoMitumi: 124->1726->53226->3059->36191->35910->32820->110 01/03 19:59 : → AnnaOuO : 看不懂楼上数字变化.. 01/05 11:37 : 推 LPH66 : 以第一个箭头为例, 2021 取阶乘後开十二次平方根得 01/05 12:11 : → LPH66 : 约 26.13, 在这里向下取整得 26; 下一步是 26! 01/05 12:13 : → ejialan : M大列的数列经过取阶乘->取n次平方根->高斯记号 01/05 12:13 : → LPH66 : 其开三次平方根後得约 2116.91 向下取整得 2116 01/05 12:13 : → LPH66 : 依此类推 01/05 12:13 : → ejialan : n依序为12 3 11 10 8 6 10 16 11 15 15 16 01/05 12:18 : 推 LPH66 : OK, 第三题写程式跑个开头就看到为何确定有更佳解了 01/05 18:39 : → LPH66 : 26 可以不用上面说的 14 步获得: 2021 不先做阶乘 01/05 18:40 : → LPH66 : 而是开两次根号再取整得 6, 阶乘 720 开方取整得 26 01/05 18:41 : → LPH66 : 这样只需要 6 步就能到 26 了 01/05 18:41 : 推 LPH66 : 然後这支程式找到以下这个 88 步解: 接 26, 走 01/05 18:52 : → LPH66 : 26-[4]>46-[4]>4062-[13]>37-[4]>496-[8]>24427 01/05 18:53 : → LPH66 : -[14]>784453-[21]>110; -[n]> 表开 n 次平方再取整 01/05 18:54 : → LPH66 : 不过这依然无法保证是最佳解, 因为程式计算关系 01/05 18:56 : → LPH66 : 中间取阶乘只在 < 10^15 的整数上用, 无法确定当 01/05 18:57 : → LPH66 : 允许更大数时有没有可能有更少步数的解 01/05 18:58 : → LPH66 : 啊更正一下, -[n]> 表示阶乘後开 n 次平方再取整 01/05 19:20 : → LPH66 : 漏提了阶乘步骤 XD 01/05 19:20 : 推 MisatoMitumi: 88比预期的要低很多啊... 我是从110逆推的，所以202 01/05 20:05 : → MisatoMitumi: 1->26可以更短是结束前才发现的XD 01/05 20:05 : → MisatoMitumi: LPH大有办法处理到(10^15)!附近吗？我自己的方法是 01/05 20:08 : → MisatoMitumi: 类似试着建立(10^5)内的有向图，然後跑Dijkstra最短 01/05 20:08 : → MisatoMitumi: 路径，不过找到路径就停了 01/05 20:08 : 推 MisatoMitumi: 原来如此，计算Log(n!)的复杂度不是O(n)，看来我太 01/05 20:16 : → MisatoMitumi: 没效率了 01/05 20:16 : 推 LPH66 : 对, 我原本以为大概也要 O(n), 不过想说这总和看着 01/05 21:50 : → LPH66 : 像是个积分, 那似乎能用∫log(n) ~ n log(n) 估计 01/05 21:50 : → LPH66 : 然後一查才发现拉马努金有给出过很好的近似公式 01/05 21:51 : → LPH66 : 大致形状是 n log(n) - n + log(n 的三次式) 01/05 21:53 : → LPH66 : 所以能算的 n 就变成 double 能表达的整数 ~9e15 了 01/05 21:54 : → LPH66 : 不算到极限是因为不太能掌握精确度... 01/05 21:55 : → LPH66 : 然後我没有明确建图, 而是把 阶乘→开方 n 次→取整 01/05 21:58 : → LPH66 : 这样的 n+2 步对不同的 n 值散出去 01/05 21:59 : → LPH66 : 核心还是 Dijkstra 但就是有踩到哪些点再记那些点 01/05 22:00 : 推 MisatoMitumi: 原来如此，公式有趣！不过wiki给的误差大约是1/1400 01/05 23:08 : → MisatoMitumi: n^3，算是有点怕... 不知道现在找到最佳解顶多88步 01/05 23:08 : → MisatoMitumi: 的话，爆出最佳解有没有机会... 01/05 23:08 糟糕, 这两天回头看这支程式发现它有一个溢位 bug 改正之後它找到一个更少步的解了: 2021 开两次根号取整得 6, 然後 6 －[2]→ 5 → 120 ─[6]→ 1278 ─[8]→ 22280837523899 ─[47]→ 110 总计 75 步 问题在於最後这一步: 22280837523899! 开四十七次平方根 我用的 log(n!) 的近似公式是在这里写的这一条： https://math.stackexchange.com/a/138326 (有其他回答有提到那个 log 里的 n 的三次式应该要加 1/30, 不过这里差别不大) 因为有点掌握不住这个式子的误差所以一直不敢完全信任 (虽然是拉马努金提出的但..) 但十四位数的阶乘又不可能真的直接去求... 是有试用过 Mathematica 的 NSum 验证 (用 Euler-Maclaurin formula 由积分推算的) 给出的 log(22280837523899!) 值确实是在 2^47*110 和 2^47*111 之间: 2^47*110 ~ 6.615338*10^14, 2^47*111 ~ 6.6280745*10^14 而 NSum 给出的 log(22280837523899!) (和拉马努金的公式) 都是 ~ 6.6251509*10^14 所以...这个四十七次根号的计算应该是对的吧? ==== 至於那个溢位 bug 是因为我的 log(n!) 函数的参数写错了, 会把 64-bit 整数传成 32-bit 整数进来 所以像上面这种数就会被当成负数传进去了 orz ==== 说起来, : → MisatoMitumi: 不知道现在找到最佳解顶多88步 01/05 23:08 : → MisatoMitumi: 的话，爆出最佳解有没有机会... 01/05 23:08 关於这一点我有想过了 因为太大的数字要使用平方根降下来也不容易 因此在已知有个总步数上限的状况下确实能够给出一个能使用阶乘的上限值 M 当开这麽多次平方根还降不回到这个上限值范围就表示不会是最佳解 就拿现在已知的 75 步来算 如果用 log(M!) ~ M*log(M) 来估的话, 降回到 log(M) 要在 75 次除以 2 内完成 (这还是个很粗略的条件) 但这差不多就是除以了 M, 也就是说 M 最大可以到 2^75 都是可能范围 这个范围好像只比常见的程式整数 / 浮点数的精确度多了一些些而已... -- 1985/01/12 三嶋鸣海 1989/02/22 优希堂悟 1990/02/22 冬川こころ 1993/07/05 小町 つぐみ 欢迎来到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬 チサト 1998/06/18 守野くるみ 打越钢太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遥 2002/12/17 八神ココ 2011/01/11 HAL18於朱仓岳坠机 ∞与∫的世界 2011/04/02 茜崎空 启动 2012/05/21 第貮日蚀计画预定 2017/05/01~07 LeMU崩坏 2019/04/01~07 某大学合宿 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 106.1.234.196 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1610093649.A.080.html ※ 编辑: LPH66 (106.1.234.196 台湾), 01/08/2021 16:17:00