lisp编程怎么解决分糖问题

vladimirputin

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 4

2:1 2 3 4

3:1 3 3 3

4:2 2 2 4

5:2 2 3 3

vladimir

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

nzl1116

1. ;;;把n颗糖分给k个人，最多m颗
   
2. (defun AYL-a (n k m / Lst0 I)
   
3.   (if (and (> n k) (> k 1))
   
4.     (progn
   
5.       (setq Lst0 nil I 1)
   
6.       (setq m (min n m))
   
7.       (repeat m
   
8.         (setq Lst0 (cons I Lst0))
   
9.         (setq I (1+ I))
   
10.       )
    
11.       (vl-remove-if (function (lambda (x) (/= (apply '+ x) n))) (combination Lst0 k))
    
12.     )
    
13.   )
    
14. )
    
15. (defun combination (lst m)
    
16.   (cond        ((zerop m) '(()))
    
17.         ((null lst) '())
    
18.         (T
    
19.          (append (mapcar '(lambda (y) (cons (car lst) y))
    
20.                          (combination lst (1- m))
    
21.                  )
    
22.                  (combination (cdr lst) m)
    
23.          )
    
24.         )
    
25.   )
    
26. )

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

xinxirong

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