社区 › 编程申请 › lisp编程怎么解决分糖问题

vladimirputin 发表于 2016-10-19 12:52:30

lisp编程怎么解决分糖问题

lisp编程怎么解决分糖问题?
将n(n<60)颗糖分给k(1 ￡ k < 20)个人,每人分到的数量至少1颗、至多m (1 ￡ m < 10)颗,一共有多少种分法?并列出所有分法。
例如:当n = 3,k = 2,m = 2时,只有1种分法:(1,2).其中(1,2)和(2,1)被认为是同一种分法.
再如:当n = 6,k = 3,m = 3时,有2种分法:(1,2,3),(2,2,2).
对于n=10,k=4,m=4的结果实际上只有5种方案：
1:1 1 4 42:1 2 3 43:1 3 3 34:2 2 2 45:2 2 3 3

vladimir 发表于 2016-10-24 09:46:51

这个问题很复杂，涉及到动态规划算法，lisp解决不了的。很遗憾啊！ lisp不是万能的。

nzl1116 发表于 2016-10-25 19:11:53

;;;把n颗糖分给k个人，最多m颗
(defun AYL-a (n k m / Lst0 I)
(if (and (> n k) (> k 1))
    (progn
      (setq Lst0 nil I 1)
      (setq m (min n m))
      (repeat m
        (setq Lst0 (cons I Lst0))
        (setq I (1+ I))
      )
      (vl-remove-if (function (lambda (x) (/= (apply '+ x) n))) (combination Lst0 k))
    )
)
)
(defun combination (lst m)
(cond        ((zerop m) '(()))
        ((null lst) '())
        (T
       (append (mapcar '(lambda (y) (cons (car lst) y))
                       (combination lst (1- m))
               )
               (combination (cdr lst) m)
       )
        )
)
)

xinxirong 发表于 2017-8-12 20:32:36

算法跟语言无关，具体的code跟语言有关。效率主要跟算法有关

查看完整版本: lisp编程怎么解决分糖问题