作者kaneson (Lance)
看板Programming
标题Re: [讨论] 排列组合的演算法解题
时间Sun Sep 6 11:12:55 2020
为了打发时间想了一个递回解
# call poss(7, 4, 0) in main()
def poss(field, pick, cur_max):
if field < pick:
return 0
if pick == 0:
return cur_max ** field
if field == 0:
return 0
_sum = 0
i = cur_max if cur_max > 0 else 1
for n in range(i, 10):
_sum += poss(field-1, pick-1, n)
_sum += i * poss(field-1, pick, cur_max)
return _sum
第一个参数是剩余栏位数
第二个参数还有几个栏位要满足条件
第三个就是当前最大值
其中如果满足的位数已经取完且还有剩余位，
例如 1234*** 剩下三位各可以取0~3，
可以直接算所以就列入base case
general case 的话这里不好说明，
自己在纸笔上展开可能比较好理解，
原则上就是分为目前最高位是否要取大於等於目前最大值。
例如 poss(3, 1, 5)
意思是目前剩3位,还有1位要满足不小於5,
可以展开成目前最大位要满足, 有5~9,
所以後面就是poss(2, 0, 5) ~ poss(2, 0, 9)
还有目前最大位不要满足, 有0~4,
所以後面就是 5组 (0~4) poss(2, 1, 5)
而当前最大值是0的话比较特别，
想了很久一开始也完全想不到如何把它凑进递回式里
我自己的电脑可以跑在0.008秒内
不过我如果是在短时间限制的面试里大概也只写得出brute force XD
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.32.154.236 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Programming/M.1599361977.A.673.html
※ 编辑: kaneson (114.32.154.236 台湾), 09/06/2020 11:14:12
※ 编辑: kaneson (114.32.154.236 台湾), 09/06/2020 11:24:34
※ 编辑: kaneson (114.32.154.236 台湾), 09/06/2020 11:25:45
※ 编辑: kaneson (114.32.154.236 台湾), 09/06/2020 11:29:20