Re: [閒聊] 現實世界有哪些原理不明的科技

看板C_Chat作者arrenwu (不是綿芽的錯)時間3年前 (2020/12/11 13:58)推噓5(5推 0噓 1→)

留言6則, 5人參與討論串19/19 (看更多)

※ 引述《initial13254 (瑟約)》之銘言： : 以前有上過一個演算法的課 : 有一個很鳥的作業 : 題目是有個老闆想送人冬瓜磚共N個冬瓜磚長寬高10公分 : 他想用包裝紙這些冬瓜磚而且包裝起來要 : : 1.包裝成一個x*y*z的長方體 : 2.包裝紙越少越好 : 3.不能有空隙 : : 一旦N是質數例如19 你包裝起來必定是一個190*10*10的超長超細長方體 : 雖然我覺得題目可能有少打什麼或有錯誤不過課本上面就是這麼寫的 : : 起初並沒有什麼難但隨者數字越來越大就越不知道怎麼設計 : 當N是4個質數相乘之前我都還行 5個質數相乘我就炸了 : 開始亂瞎猜什麼開立方根阿先乘個3看看阿反正跟數學邏輯沒什麼關係了 : : 最後老師上課講解告訴我 : 題目好像怪怪的只好用暴力破解法喔啾咪 : 推 e5a1t20: 滿足正整數xyz=N，求xy+xz+zy最小，只求表面積還是包裝 12/10 21:07 : → e5a1t20: 紙還要長方形把冬瓜磚包起來？ 12/10 21:07 : → e5a1t20: 求最小N/x+xN/k+k，讓k=xy，這樣算起來暴力解的複雜度大 12/10 21:25 : → e5a1t20: 概比N的因數數量^2小 12/10 21:25 我剛剛在看角卷綿芽昨天的SC時候想到這問題 https://pbs.twimg.com/media/EoUJcfJUYAE8uhJ.jpg

這個演算法問題其實還滿有趣的啊假設我們考慮一個比較廣泛的問題：給定兩個整數 N 和 n，求所有滿足 x_1*x_2*....x_n = N 的正整數組合 (x_1,x_2,...,x_n) 中， n Σ N/x_i 的最小值 i=1 原來的那個包裝問題就是這問題在 n=3 的特例假設給定兩整數N,n所能得到的最小值是 f(N,n)，則我們有 f(N,n) = min N/u + u*f(N/u, n-1) u | N (意即u是N的因數) f(N,1) = 1 f(1,n) = n 這作法時間複雜度是 o( (N的因數數量)^2*n ) 硬爆我覺得就算用backtracking在n稍大都會炸開來 -- https://pbs.twimg.com/media/ElI7vEBVkAEvNtS.jpg

Cinderella Switch by 角卷綿芽、不知火芙蕾雅 2020-11-28 星期六 4pm~8pm -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.234.190.206 (美國) ※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1607666313.A.BCD.html

推

kuninaka

12/11 14:03, 3年前 , 1^F

12/11 14:03, 1^F

推

knight45683

12/11 14:09, 3年前 , 2^F

12/11 14:09, 2^F

可能是因為瓦他咩太知性了嘻嘻也可能是因為她桌子上那些零食長得有點像 xy+yz+zx https://pbs.twimg.com/media/EoiVVjXVQAA4lWf.jpg