Re: [討論] 排列組合的演算法解題已刪文

看板Programming作者AntaresStar時間3年前 (2021/09/06 11:13)推噓0(0推 0噓 3→)

留言3則, 1人參與討論串7/7 (看更多)

想了一個遞迴DP 因為這是一個取或不取的問題很適用遞迴法基本型態會是 f(n) = g(f(n-1), f(n-2), ... ) 這樣 g()通常是min或sum或if-else 可以系統化來寫這3個步驟: 1. 寫遞迴式 2. 寫終止條件 3. 寫查表以這題來說可以寫一個遞迴 rec(0,0,0) : // pos:第幾位, prev:上次的數字, acc:目前取幾位了 int rec(int pos, int prev, int acc) { // 遞迴式 int ret = 0; for (int i = 0; i < 10; ++i) { if (i >= prev) ret += rec(pos+1, i, acc+1); // 要這位數 else ret += rec(pos+1, prev, acc); // 不要這位數 } return ret; } 那麼再來就是終止條件我想了3個: int rec(int pos, int prev, int acc) { // 終止條件 if (acc > 4) return 0; // 取超過了 if (pos > 6) return acc == 4; // 到底了是否剛好取到4個 if ((7 - pos) + acc < 4) return 0; // 不夠取了 // 遞迴式 ... } 到這應該就可以運作了以c++ code來說其實已經夠快不過這樣還沒用到查表於是直接把整個rec的參數拿來當key: struct S { int pos, prev, acc; bool operator<(const S &o) const { if (pos != o.pos) return pos < o.pos; if (prev != o.prev) return prev < o.prev; return acc < o.acc; } }; static map<S, int> cache; int rec(int pos, int prev, int acc) { // 終止條件 ... // 查表 auto iter = cache.find({pos,prev,acc}); if (iter != cache.end()) return iter->second; // 遞迴式 ... cache[{pos,prev,acc}] = ret; return ret; } 這樣就完成啦答案是2027025 (希望是對的) 時間的話在我電腦上直接暴力解是0.75秒純遞迴是0.063 加DP是0.017 看起來似乎合理 ※ 引述《applebeing (蘋果人)》之銘言： : 求職時線上測驗的問題，有算出解答，但覺得應該有更好的解法， : 向各位版友請教解題想法。 : 問題如下： : 一個七位數的數字，從第七位到個位數的順序開始比對。 : 若當前位數的值，不小於曾出現過的數的最大值，就記錄起來。 : 請問紀錄結果為四個數字的可能組合數有幾組？ : 例： : 2334849 - 由左至右 : 第一位數 2 加入紀錄 : 第二位數 3 大於等於2，加入紀錄 : 第三位數 3 大於等於3，加入紀錄 : 第四位數 4 大於等於3，加入紀錄 : 第五位數 8 大於等於4，加入紀錄 : 第六位數 4 不紀錄 : 第七位數 9 大於等於8，加入紀錄 : 紀錄結果為 6 : 6429748 - 紀錄 69 （2個數） : 4629889 - 紀錄 4699（4個數） : 各位數可以為 0，例如 0001234、0007899 也符合要求。 : 我用迴圈跑 1~一千萬涵蓋七位數，每個數字都檢查紀錄結果，得出組數。 : 跑了五分多鐘，很笨也很沒有效率。 : 想請問是否有更效率的解題方式？ : 請大家指教，感謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.101.100 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1630898019.A.D1D.html