1

我需要编写一个函数，该函数将返回可以将 n（n 是自然数）写为自然数之和的方式数。例如：4可以写成1+1+1+1、1+1+2、2+2、3+1和4。我写了一个函数，返回所有选项的个数，但是不取考虑到可能性 1 + 1 + 2 和 2 + 1 + 1（以及所有类似情况）是相等的。所以对于 n=4 它返回 8 而不是 5。这是我的函数：

(define (possibilities n)
   (define (loop i)
      (cond [(= i n) 1]
         [(> i n) 0]
         [(+ (possibilities (- n i)) (loop (+ i 1)))]))
     (cond [(< n 1) 0]
        [#t (loop 1)]))

您能否帮我修复我的功能，这样它就可以按应有的方式工作。谢谢你。

4

1 回答 1

1

这是一个众所周知的函数，它被称为配分函数 P，它的可能值在整数序列在线百科全书中被称为A000041 。

一个简单的解决方案（不是最快的！）是使用这个辅助函数，它将写作方式的数量表示n为精确k项的总和：

(define (p n k)
  (cond ((> k n) 0)
        ((= k 0) 0)
        ((= k n) 1)
        (else 
         (+ (p (sub1 n) (sub1 k))
            (p (- n k) k)))))

然后我们只需要添加可能的结果，注意边缘情况：

(define (possibilities n)
  (cond ((negative? n) 0)
        ((zero? n) 1)
        (else
         (for/sum ([i (in-range (add1 n))])
           (p n i)))))

例如：

(map possibilities (range 11))
=> '(1 1 2 3 5 7 11 15 22 30 42)
于 2015-01-18T18:54:26.507 回答