(구성표) 목록의 일부 숫자가 특정 숫자와 합쳐 졌는지 확인하십시오.

Question

나는 목록과 합계를 취하는 프로그램을 만들고있다. 목록에있는 숫자 중 일부가 합계와 일치하면 true를 반환합니다. 그렇지 않으면 거짓을 반환합니다. 어떤 경우에는 효과가 있지만 다른 경우에는 효과가없는 것 같습니다. 예를 들어,

경우 I 입력이 :

(numlist-sum '(5 9) 9) 

(9) 번호 중 하나는 합과 동일하기 때문에 사실 반환해야합니다 (9). 그러나, 어떤 이유로, 그것의 잘못된 반환.

문제점을 파악할 수 없습니다. 도와주세요?

(define (numlist-sum? ls sum) 
    (if (null? ls) #t 
    (if (and (null? (cdr ls)) (equal? (car ls) sum)) #t 
     (if (equal? (car ls) sum) #t 
      (if (equal? (cdr ls) sum) #t 
       (if (equal? (apply + (car ls) (cdr ls)) sum) #t 
        #f)))))) 

Answer 1

이 문제를 해결하기위한 몇 가지 힌트 (숙제처럼 보임)를 제공해 드리겠습니다. 먼저 목록의 가능한 모든 하위 집합을 생성하는 절차를 작성하십시오 (예 : 목록의 power set). 예를 들어 :

(powerset '(1 2 3)) 
=> '(() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)) 

손에 위의 절차와

(그리고 구글은 당신의 가장 친한 친구 인 알고리즘을 쉽게 찾을 수), 단순히 하위 목록의 각을 반복하고 값 합계 :

(apply + '(2 3)) 
=> 5 

을

하위 목록의 합계 중 하나가 예상 값과 같으면 #t을 반환하십시오. 합계가 예상 값을 충족시키지 않으면 #f을 리턴하십시오.

EDIT : I가 깜빡하고

이 잘 알려진 문제이다 - 효율적으로 해결 될 수 subset sum problem,이다 (이상,보다 효율적으로 전력 세트 생성 이하) dynamic programming를 사용한다. 그러나 나는 이것이 그 숙제의 목표라고 생각하지 않습니다.

Answer 2

다음은 각 요소를 하나씩 확인한 다음 첫 번째 요소가 합계가 아닌 경우 목록을 되풀이하는 솔루션입니다.

(define (numlist-sum? ls sum) 
    (or (null? ls) 
     (if (and (null? (cdr ls)) (equal? (car ls) sum)) 
     (equal? (car ls) sum) 
     (equal? (cdr ls) sum) 
     (equal? (apply + (car ls) (cdr ls)) sum))) 

내가 (... #T 다른 PRED 경우) 조금 어색 '의 사용을 말하고 싶지만하고 숨 깁니다 또한

(define (numlist-sum list sum) 
    (and (not (null? list)) 
     (let ((head (car list))) 
     (cond ((number? head) 
       (or (= sum head) 
        (numlist-sum (cdr list) sum))) 
       ((list? head) 
       (or (= sum (apply + head)) 
        (numlist-sum (cdr list) sum))) 
       (else 'ill-formed-list))))) 

, 당신의 코드는 다음과 같이 다시 쓸 수 있습니다 코드의 진정한 논리.