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

Re: [問題] 0～9 挑k個數字, 組出最接近 A 的數字

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間10年前 (2014/11/01 15:05)推噓1(1推 0噓 4→)

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

※ 引述《flere (人間失格)》之銘言： : 有想到個方法大家討論討論> < : 不知道有沒有哪邊沒考慮清楚的!! : 能使用k個數字, 我們可以窮舉是哪k個 : 對於每一個可能的組合去求出最接近的數字後面應該沒什麼大問題。但對於窮舉k個，我考慮有規則的情況。 let d(x) 為 A 的 digits 數。於是原本題目的解的domain可以為 d(A) 必定 > k，不然就直接輸出A。後面敘述的最高位想法是可以拿來規則化取候選 digits 1.對於 k = 1，候選 digits 為最高位，和 (最高位 -1) 如果(最高位 - 1) == 0，則為9，此特殊case適用尚未轉化過的，且後面剩下位數必須都填9。何謂轉化請見2. 2.對於 k = 2 含以上，從d(A)裡面取出並轉化。直到k = 0為止不轉化 input(262004, 2) 取最高位 2 並且當為解的第一位並轉化 input(62004, 1) 取 6 或 5，可以計算已經用掉2個digits 轉化 (XXXX, 0) XXXX用候選digits: 2, 6, 5填滿，262222, 252222, 266666, 265555 舉幾個例子 case 1: input(210004, 2) => 取 2 => input(10004, 1) 僅取1 => input(XXXX, 0) =>填滿 212222, 211111 case 2: input(8000, 1) => 取8, 7 => (XXX, 0) => 填滿 8888, 7777 case 3: input(1000, 1) => 取1, 9 (special case) => (XXX, 0) =>填滿 1111 和 999 cae 4: input(88449, 2) => 取8 => (8449, 1) => 取8, 7 分兩路 =>(449, 1) => 取4 => (49, 0) => 88488, 88448, 88444 =>(449, 0) => 87888, 87777 應該可以實作了。 : 對於一個N位數的數字而言 : 我們的答案可能為N位數或N-1位數 : 想不到答案要N+1位數的case.. : 以N-1位數的答案ans而言 : ans肯定比要求的數字A還小 : 故ans要盡可能大 : 則ans會只由一種數字組成 : 接下來討論ans為N位數的情況 : 由於我們已經窮舉哪k個數能使用 : 所以我們可以從最高位開始決定要放什麼數字 : 假設數字A的最高位數為m : 則有三種情況: : 1. 我們最高位放的數字>m, 這表示剩下N-1個位置, 我們要用k個數字組的盡量小 : 2. 我們最高位放的數字<m, 這表示剩下N-1個位置, 我們要用k個數字組的盡量大 : 3. 最高位放的數字=m, 則問題轉化成(A-m*10^N,k), N-1個位數的問題 : 對於(1,2)而言, 嘗試的數字必定是比m大(小)的裡面最小(大)的, 只需嘗試一次 : 且不須遞迴下去, 因為k個數字組最大最小可以直接算出 : 對於(3)則最多只有一種可能, : 因此複雜度為(10取k)*(N個位數)*(每個位數3種可能) ===================================編輯分隔線===================== 補上實作連結 http://ideone.com/nOsGRz 修正特殊case：當尚未進行轉化，並且最高位減1 == 0的時候判斷首兩位數為10才補滿N - 1位數的9 否則取1和9繼續遞迴。修正結束條件：當轉化後k == 0但目前所在的digit之前尚未用過才停止開始填滿。若所在digit仍有用過那麼索引要往後推，並繼續遞迴。詳情看code就知道了，這樣一來大部分case應該都能跑很快了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.203.156 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1414825535.A.FDA.html