Re: [問題] 0～9 挑k個數字, 組出最接近 A 的數字
看板Prob_Solve (計算數學 Problem Solving)作者flere (人間失格)時間10年前 (2014/11/01 13:02)推噓2(2推 0噓 3→)留言5則, 3人參與討論串4/5 (看更多)
有想到個方法大家討論討論> <
不知道有沒有哪邊沒考慮清楚的!!
能使用k個數字, 我們可以窮舉是哪k個
對於每一個可能的組合去求出最接近的數字
對於一個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種可能)
補上一個測資:(7099,2) 答案為7111
若取前k個不同的數字當候選的話, 就會無法得到7111這個答案了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.152.218.19
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1414818126.A.BAE.html
推
11/01 13:53, , 1F
11/01 13:53, 1F
→
11/01 13:54, , 2F
11/01 13:54, 2F
→
11/01 13:54, , 3F
11/01 13:54, 3F
→
11/01 13:55, , 4F
11/01 13:55, 4F
※ 編輯: flere (58.152.218.19), 11/02/2014 11:55:20
推
11/02 13:05, , 5F
11/02 13:05, 5F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 4 之 5 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
