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

看板Programming作者SocketAM2 (AM2)時間4年前 (2020/09/01 10:50)推噓1(1推 0噓 0→)

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

基本想法是一個個位數iterate過去有個簡單的剪枝手段：不可能達成4個的時候就不用往下數了例如10000xx，最多就3個數再來是個簡單的算小計手段：已經數到四個數了，剩下的位數只能在已知最大值之內例如1234xyz中的xyz各能在(0,1,2,3,4)中任選，所以這類共5^3=125個我試了下python，光用上面這兩招沒特別雕語法大概可以跑在一秒多原po可以參考看看還有版友想得到其他有效手段嗎？剛剛又發現一個不錯的手段：建表查表例如前面算過1234xyz這類共125個建個表，key是“ 前四位數最大為4，且已經數到4個數了”，值是125 以後再碰到這種case就直接小計125 遇到表上沒有的就往下拆分算完再加進表內加上這招可以壓到0.03秒左右 ※ 引述《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), 來自: 140.109.189.166 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1598928609.A.178.html ※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 10:53:29 ※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 10:55:03 ※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 10:57:40 ※ 編輯: SocketAM2 (140.109.189.166 臺灣), 09/01/2020 11:18:55