PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Maximum Product

看板Prob_Solve (計算數學 Problem Solving)作者cutekid (可愛小孩子)時間8年前 (2016/09/12 16:19)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/4 (看更多)

謝謝 dibery 我將你的想法理解後實作了一遍程式網址(Perl): http://codepad.org/cicXQTmo 用了 bottom-up 迭代的方式計算 max_product (捨去遞迴) 時間複雜度應該是 O( 長度 * 長度 * K ) 大於你原來所說的 O( 長度 * K ) 以下為原始碼: ============= #!C:\Perl\bin\perl -w ############## # 欲計算的數字 $N = 746589; ############## # 插入幾個乘號 $K = 2; ########## # 數字長度 $L = length($N); ################ # 產生所有子數字 &GenSubNum; ######################################## # 計算 maxProduct[長度][$k = 0,1,2,3...] # # 長度 : left substring length # k : 插入乘號個數 ########################## # init maxProduct[長度][0] for($i = 0; $i < $L; ++$i){ $maxProduct[$i + 1][0] = $subNum[0][$i + 1]; } ############################################### # 迭代 $k = 1,2,3 ... 算出 maxProduct[長度][$k] for($k = 1; $k <= $K; ++$k){ for($leftLen = $k + 1; $leftLen <= $L - $K + $k; ++$leftLen){ for($i = $k, $max = 0; $i < $leftLen; ++$i){ $v = $maxProduct[$i][$k - 1] * $subNum[$i][$leftLen - $i]; $max = $v if($v > $max); } $maxProduct[$leftLen][$k] = $max; } } ############## # print answer print $maxProduct[$L][$K]; sub GenSubNum { @digit = split('',$N); for($i = 0; $i < $L; ++$i){ for($j = $i, $acc = 0, $len = 1; $j < $L; ++$j, ++$len){ $acc = $acc * 10 + $digit[$j]; $subNum[$i][$len] = $acc; } } } ※ 引述《dibery (簡哥)》之銘言： : ※ 引述《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) 暴力搜尋 : : 還有什麼比較好的算法嗎 : : 謝謝 ^_^ : 寫一下我的想法,有錯請告知 : 這裡就先不考慮 overflow 的問題 : 設計函式 max_product( number, k ) 代表在 number 裡插入 k 個乘號 : 以你第一個例子 : 要求解 max_product( 746589, 2 ) : 它的解是 : 7 * max_product( 46589, 1 ) : 74 * max_product( 6589, 1 ) : 746 * max_product( 589, 1 ) : 7465 * max_product( 89, 1 ) : 這其中一個 : 74658 * max_product( 9, 1 ) 因為 9 沒法插一個乘號進去所以不算 : 然後每一個結果都可以存下來,遞迴就不用每次跑 : 算是 top-down 的 DP 吧,複雜度估計大概是 O( nk ) : 遞迴的終止條件是 k = 0 : 感覺用 python 會比較好寫XD -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.233.210 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1473668359.A.EDF.html