首先畫個圖： 9 8 7 6 5 4 3 2 1 1234567 位數 假設數值為2545397。 9 x 8 7 x 6 5 x x 4 x 3 x 2x 1 1234567 很容易可以看到，重要的是建立四個遞增點，剩下的點只要在前一個遞增點以下 就不會影響結果： 9 x 8 - 7 - 6 - 5 x x - 4 - - - 3 - - - 2x - - - 1 - - - 1234567 那麼四個遞增點怎麼建立呢？四層迴圈硬跑基本上寫得正確就不會跑出不可能的 狀態，也就是後數比前數大或相等即可（以Python為例，注意range(a, b)表示包含a 到(b-1)）： sum = 0 n_list = [0] * 4 for n_list[0] in range(0, 10): for n_list[1] in range(n_list[0], 10): for n_list[2] in range(n_list[1], 10): for n_list[3] in range(n_list[2], 10): sum += poss_num(n_list) 每建立一套遞增點，例如2559，那麼我們就要插入剩下三個數並確保三個數不會 影響遞增點數量。 首先觀察2前面不能插值，因為2前面<= 2會使遞增點多一，> 2會使2不再是遞增 點。 再來，如果我們要插在2跟5之間，合法值有幾個？答案是0、1，也就是< 2的兩 個數。同理，插在5跟5之間只要看前面的5而可以接受0~4，5跟9之間也是看5而同樣 是0~4，9之後則是0~8。也就是說，很巧地，你要插一個值到x這個值後面，就有x這 麼多種不重複的可能性。 我們驗證一下極端值0是不是也符合？0369為例，0後面可以插值而不影響遞增數 量或位置嗎？看來是不行的，插個0或以上就變成遞增五個數了，所以0後面插值的可 能性確實是0種。 那麼同樣2559為例，如果我們要插2個值在2後面，1個在9後面，有幾種可能？ 2005590 2005591 2005592 . . 2005598 2015590 . . 2115598 接在2後面的值有2種可能，9後面就有9種可能，所以是2*2*9 = 36。也就是說， 我們甚至都不用列出來，直接可以簡單乘法就算出這邊的可能性。 那麼同樣跑完全沒有多餘的迴圈來決定三個數「依序」插在哪裡，就可以個別用 上述公式解算出各種插入位置的可能性。第一個數可以有四個位置選擇（四個遞增點 之後），第二個數必須在第一個數同樣或更後面的位置，以此類推。最後就可以加總 ： def poss_num(n_list): sum = 0 pos_list = [0] * 3 for pos_list[0] in range(0, 4): for pos_list[1] in range(pos_list[0], 4): for pos_list[2] in range(pos_list[1], 4): sum += ( n_list[pos_list[0]] * n_list[pos_list[1]] * n_list[pos_list[2]] ) return sum 總結一下，關鍵就在於兩個點： 1. 選取數字時的迴圈怎麼樣徹底避開不可能狀況 -> 兩者都是遞增 2. 遞增四個數字以及插入位置確定後，如何避免一一窮舉 -> 注意到內層有公式解 注意Python完整Code要把poss_num()的定義搬到主迴圈前面去。執行時間基本上 按下去就出來了。 有心的話可以將兩個多層迴圈都改寫為stack，這樣你就可以處理此問題的通解 ：任意位數，任意遞增長度。 -- 「傳說的最後，魔王總是被勇者封印。但勇者會逝去、封印會衰弱，魔王卻永遠 不滅。傳說呢？傳說持續著。只是，變質了。所以對於傳說而言，只有反覆無常的自 己是主角，而魔王只是配角。勇者？勇者不過是消耗品罷了，封印則什麼也不是。妳 好不容易有機會當上配角，怎麼走回頭路想成為消耗品？妳早晚會什麼也不是的。」 －－星．幻．夢的傳說 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.17.60 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1598937076.A.A19.html ※ 編輯: ddavid (114.32.17.60 臺灣), 09/01/2020 13:14:25 還好，你的改良版cut方式夠好，該砍的都有砍掉的話，大概就只多一些量不大 的邏輯判斷成本吧。 ※ 編輯: ddavid (114.32.17.60 臺灣), 09/01/2020 14:53:04 ※ 編輯: ddavid (1.164.183.14 臺灣), 11/21/2020 02:01:20