推 MisatoMitumi: 用心推! 01/02 07:33
→ MisatoMitumi: 想比對一下原po預設的答案，第一題上下倒過來看， 01/02 07:33
→ MisatoMitumi: 動三根火柴棒有1201+01=1202 01/02 07:34
推 MisatoMitumi: 第八題看來是rank 1，然後第一小題給的是generator 01/02 07:40
推 Starvilo : 2.2^11-3^3不知是否最小 01/02 13:03
推 reye : 樓上，我的答案和你一樣 01/02 17:20
推 alan23273850: 回5.6樓，第二題的證明才是真正有趣的。 01/02 19:27
推 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
推 LPH66 : 話說第九題我做出這個結果: 01/06 11:28
→ LPH66 : 是不是最後那個條件有點太鬆了...? 01/06 11:29
→ LPH66 : 等式只能推得領導係數我覺得是故意設計的 01/06 11:31
→ LPH66 : (那個形式實在太剛好了) 所以猜是後一條件放太寬 01/06 11:31
→ TimcApple : 嗯 是設計失誤 我第一個等式解錯了 01/09 10:54