方案：列出所有的方式，使更改爲10使用列表

目標：總：10個 denoms：（10 10 1）回報（（10）（5）（5 1 1 1 1 1）（1 1 1 1 1 1 1 1 1 1））方案：列出所有的方式，使更改爲10使用列表

我的代碼：

(define (changes-list total denoms) 

    (cond 

    ((null? denoms) nil) 

    ((= total 0)) 

    ((> (car denoms) total) (changes-list total (cdr denoms))) 

    (else 

     (if (= total (car denoms)) (cons (list (car denoms)) (changes-list total (cdr denoms))) 
     (append (cons-all (car denoms) (changes-list (- total (car denoms)) denoms)))) 
    ) ) )

~~~~~~ 什麼我的代碼輸出，現在的問題是：（（10）（5）（5 1 1 1 1 1））我認爲問題可能存在於cond中，當我調用（cdr denoms）上的更改列表並將denoms更改爲空並退出但我不知道如何解除x這。所有幫助非常感謝！

來源

2016-04-24 Hermione

有兩種情況，你需要聯合在一起：使用'（汽車denoms）'，而不是'（汽車denoms）'。你只是在做前者。 – molbdnilo

假設下面的兩個條件（否則你應該檢查參數）：

total總是非負，
denoms在遞減順序和最後一個元素進行排序總是1，

這裏是一個可能的解決方案：

(define (cons-all x lst) 
    (map (lambda (l) (cons x l)) lst)) 

(define (repeat n x) 
    (if (= n 0) 
     '() 
     (cons x (repeat (- n 1) x)))) 

(define (changes-list total denoms) 
    (cond ((= total 0) '(())) 
     ((null? (cdr denoms)) (list (repeat total (car denoms)))) 
     ((< total (car denoms)) (changes-list total (cdr denoms))) 
     (else (append (cons-all (car denoms) (changes-list (- total (car denoms)) denoms)) 
         (changes-list total (cdr denoms)))))) 

(changes-list '6 (2 1)) ; => ((2 2 2) (2 2 1 1) (2 1 1 1 1) (1 1 1 1 1 1))

來源

2016-04-25 05:35:03 Renzo

在嘗試不同的路徑，其中不是每個人都將產生一個有效的解決方案，我想以一個path列表可跟蹤路徑，並累加器acc只保留中標結果：

(define (changes-list total denoms) 
    (let iter ((total total) (denoms denoms) (path '()) (acc '())) 
    (cond 
     ((= total 0) (cons (reverse path) acc)) ; the current path lead to a solution => keep path in accumulator 
     ((or (< total 0) (null? denoms)) acc) ; discard path 
     (else 
     (let ((denom (car denoms))) ; first denomination 
     (iter (- total denom)  ; (1) use first denomination 
       denoms 
       (cons denom path) 
       (iter total   ; (2) drop first denomination 
        (cdr denoms) 
        path 
        acc)))))))

測試：

> (changes-list 10 '(10 5 1)) 
'((10) (5 5) (5 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1)) 
> (changes-list 6 '(2 1)) 
'((2 2 2) (2 2 1 1) (2 1 1 1 1) (1 1 1 1 1 1))

來源

2016-04-25 18:24:49 uselpa

方案：列出所有的方式，使更改爲10使用列表

回答

相關問題