[其他] 2021 新年數學題目

看板Math作者 (肥鵝)時間3年前 (2021/01/01 00:15), 編輯推噓14(14推 0噓 39→)
留言53則, 7人參與, 4年前最新討論串1/3 (看更多)
https://reurl.cc/N6zekQ 一共 10 題和 2021 有關的題目 祝各位新年快樂ow o -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.12.204 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1609431322.A.092.html
推
01/02 07:33, 4年前 , 1F
用心推!
01/02 07:33, 1F
→
01/02 07:33, 4年前 , 2F
想比對一下原po預設的答案，第一題上下倒過來看，
01/02 07:33, 2F
→
01/02 07:34, 4年前 , 3F
動三根火柴棒有1201+01=1202
01/02 07:34, 3F
推
01/02 07:40, 4年前 , 4F
第八題看來是rank 1，然後第一小題給的是generator
01/02 07:40, 4F
推
01/02 13:03, 4年前 , 5F
2.2^11-3^3不知是否最小
01/02 13:03, 5F
推
01/02 17:20, 4年前 , 6F
樓上，我的答案和你一樣
01/02 17:20, 6F
推
01/02 19:27, 4年前 , 7F
回5.6樓，第二題的證明才是真正有趣的。
01/02 19:27, 7F
推
01/03 19:57, 4年前 , 8F
Q3先給一個157步的參考路徑（不過確定有更佳解）
01/03 19:57, 8F
→
01/03 19:58, 4年前 , 9F
（只列出取階乘的數字）2021->26->2116->973->268->
01/03 19:58, 9F
→
01/03 19:59, 4年前 , 10F
124->1726->53226->3059->36191->35910->32820->110
01/03 19:59, 10F
→
01/05 11:37, 4年前 , 11F
看不懂樓上數字變化..
01/05 11:37, 11F
推
01/05 12:11, 4年前 , 12F
以第一個箭頭為例, 2021 取階乘後開十二次平方根得
01/05 12:11, 12F
→
01/05 12:13, 4年前 , 13F
約 26.13, 在這裡向下取整得 26; 下一步是 26!
01/05 12:13, 13F
→
01/05 12:13, 4年前 , 14F
M大列的數列經過取階乘->取n次平方根->高斯記號
01/05 12:13, 14F
→
01/05 12:13, 4年前 , 15F
其開三次平方根後得約 2116.91 向下取整得 2116
01/05 12:13, 15F
→
01/05 12:13, 4年前 , 16F
依此類推
01/05 12:13, 16F
→
01/05 12:18, 4年前 , 17F
n依序為12 3 11 10 8 6 10 16 11 15 15 16
01/05 12:18, 17F
推
01/05 18:39, 4年前 , 18F
OK, 第三題寫程式跑個開頭就看到為何確定有更佳解了
01/05 18:39, 18F
→
01/05 18:40, 4年前 , 19F
26 可以不用上面說的 14 步獲得: 2021 不先做階乘
01/05 18:40, 19F
→
01/05 18:41, 4年前 , 20F
而是開兩次根號再取整得 6, 階乘 720 開方取整得 26
01/05 18:41, 20F
→
01/05 18:41, 4年前 , 21F
這樣只需要 6 步就能到 26 了
01/05 18:41, 21F
推
01/05 18:52, 4年前 , 22F
然後這支程式找到以下這個 88 步解: 接 26, 走
01/05 18:52, 22F
→
01/05 18:53, 4年前 , 23F
26-[4]>46-[4]>4062-[13]>37-[4]>496-[8]>24427
01/05 18:53, 23F
→
01/05 18:54, 4年前 , 24F
-[14]>784453-[21]>110; -[n]> 表開 n 次平方再取整
01/05 18:54, 24F
→
01/05 18:56, 4年前 , 25F
不過這依然無法保證是最佳解, 因為程式計算關係
01/05 18:56, 25F
→
01/05 18:57, 4年前 , 26F
中間取階乘只在 < 10^15 的整數上用, 無法確定當
01/05 18:57, 26F
→
01/05 18:58, 4年前 , 27F
允許更大數時有沒有可能有更少步數的解
01/05 18:58, 27F
→
01/05 19:20, 4年前 , 28F
啊更正一下, -[n]> 表示階乘後開 n 次平方再取整
01/05 19:20, 28F
→
01/05 19:20, 4年前 , 29F
漏提了階乘步驟 XD
01/05 19:20, 29F
推
01/05 20:05, 4年前 , 30F
88比預期的要低很多啊... 我是從110逆推的，所以202
01/05 20:05, 30F
→
01/05 20:05, 4年前 , 31F
1->26可以更短是結束前才發現的XD
01/05 20:05, 31F
→
01/05 20:08, 4年前 , 32F
LPH大有辦法處理到(10^15)!附近嗎？我自己的方法是
01/05 20:08, 32F
→
01/05 20:08, 4年前 , 33F
類似試著建立(10^5)內的有向圖，然後跑Dijkstra最短
01/05 20:08, 33F
→
01/05 20:08, 4年前 , 34F
路徑，不過找到路徑就停了
01/05 20:08, 34F
推
01/05 20:16, 4年前 , 35F
原來如此，計算Log(n!)的複雜度不是O(n)，看來我太
01/05 20:16, 35F
→
01/05 20:16, 4年前 , 36F
沒效率了
01/05 20:16, 36F
推
01/05 21:50, 4年前 , 37F
對, 我原本以為大概也要 O(n), 不過想說這總和看著
01/05 21:50, 37F
→
01/05 21:50, 4年前 , 38F
像是個積分, 那似乎能用∫log(n) ~ n log(n) 估計
01/05 21:50, 38F
→
01/05 21:51, 4年前 , 39F
然後一查才發現拉馬努金有給出過很好的近似公式
01/05 21:51, 39F
→
01/05 21:53, 4年前 , 40F
大致形狀是 n log(n) - n + log(n 的三次式)
01/05 21:53, 40F
→
01/05 21:54, 4年前 , 41F
所以能算的 n 就變成 double 能表達的整數 ~9e15 了
01/05 21:54, 41F
→
01/05 21:55, 4年前 , 42F
不算到極限是因為不太能掌握精確度...
01/05 21:55, 42F
→
01/05 21:58, 4年前 , 43F
然後我沒有明確建圖, 而是把 階乘→開方 n 次→取整
01/05 21:58, 43F
→
01/05 21:59, 4年前 , 44F
這樣的 n+2 步對不同的 n 值散出去
01/05 21:59, 44F
→
01/05 22:00, 4年前 , 45F
核心還是 Dijkstra 但就是有踩到哪些點再記那些點
01/05 22:00, 45F
推
01/05 23:08, 4年前 , 46F
原來如此，公式有趣！不過wiki給的誤差大約是1/1400
01/05 23:08, 46F
→
01/05 23:08, 4年前 , 47F
n^3，算是有點怕... 不知道現在找到最佳解頂多88步
01/05 23:08, 47F
→
01/05 23:08, 4年前 , 48F
的話，爆出最佳解有沒有機會...
01/05 23:08, 48F
推
01/06 11:28, 4年前 , 49F
話說第九題我做出這個結果:
01/06 11:28, 49F
→
01/06 11:28, 4年前 , 50F
01/06 11:28, 50F
→
01/06 11:29, 4年前 , 51F
是不是最後那個條件有點太鬆了...?
01/06 11:29, 51F
→
01/06 11:31, 4年前 , 52F
等式只能推得領導係數我覺得是故意設計的
01/06 11:31, 52F
→
01/06 11:31, 4年前 , 53F
(那個形式實在太剛好了) 所以猜是後一條件放太寬
01/06 11:31, 53F
‣ 更多 TimcApple 的文章
文章代碼(AID): #1VxVaQ2I (Math)
‣ 更多 TimcApple 的文章
文章代碼(AID): #1VxVaQ2I (Math)