Re: [問題] 0～9 挑k個數字, 組出最接近 A 的數字
※ 引述《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
推
11/01 15:10, , 1F
11/01 15:10, 1F
→
11/01 15:15, , 2F
11/01 15:15, 2F
我用遞迴去產生填滿，因為位數少，速度還算快。
※ 編輯: bleed1979 (220.135.203.156), 11/01/2014 19:32:38
→
11/02 11:50, , 3F
11/02 11:50, 3F
→
11/02 12:08, , 4F
11/02 12:08, 4F
→
11/02 12:13, , 5F
11/02 12:13, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 5 篇)：