首先画个图： 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/cn.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