숫자를 계산하는 다른 방법

Question

자연 수의 합계로 쓰여진 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)])) 

당신은 내 기능을 수정 좀 도와 주 시겠어요. 고맙습니다.

Answer 1

이것은 잘 알려진 함수로 partition function P이라고하며 가능한 값은 정수 시퀀스의 온라인 백과 사전에서 A000041으로 참조됩니다.

한 간단한 솔루션 (안 가장 빠른!) 정확히 k 용어의 합으로 n를 작성하는 방법의 수를 나타내며,이 도우미 기능을 사용하는 것입니다 :

(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) 

,536,