Re: [問題] Maximum Product
看板Prob_Solve (計算數學 Problem Solving)作者pttworld (批踢踢世界)時間8年前 (2016/09/10 13:49)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/4 (看更多)
※ 引述《cutekid (可愛小孩子)》之銘言：
: 給定一個數字 N (由 1 ~ 9組成)
: 其中插入 K 個乘號，使最後相乘的值要最大
: 舉例:
: N = 746589, K = 2, 最大值 = 7465 x 8 x 9
: N = 1111114, K = 3, 最大值 = 11 x 11 x 11 x 4
: 請問這題除了 C(長度 - 1,K) 暴力搜尋
: 還有什麼比較好的算法嗎
: 謝謝 ^_^
一個數插入乘號使得乘積小於原數。
對於每一列n，
迭代比較列n-1之每一欄m，插入乘號後左乘以右之乘積，
乘積最大之m即為切點。
如left boundary ~ m形成的值大於m ~ right boundary，
列n之比較範圍為left boundary ~ m，反之為m ~ right boundary。
C++版本，輸出為切點索引值。
https://gist.github.com/anonymous/f4a2a632cd7f44a11ecd957fbd23dae1
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.43.36.13
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1473486544.A.D78.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
