使用数字列表的任意精度加法

Question

我想要做的是拿两个列表并将它们加在一起，就像每个列表是一个整数。

(define (reverse lst) 
(if (null? lst) 
    '() 
    (append (reverse (cdr lst)) 
     (list (car lst))))) 

(define (apa-add l1 l2) 
    (define (apa-add-help l1 l2) 
    (cond ((and (null? l1) (null? l2)) '()) 
     ((null? l1) (list (+ (apa-add-help '() (cdr l2))))) 
     ((null? l2) (list (+ (apa-add-help (cdr l1) '())))) 

     ((>= (+ (car l1) (car l2)) 10) 
     (append (apa-add-help (cdr l1) (cdr l2))    
       (list (quotient (+ (car l1) (car l2)) 10)) 
       (list (modulo (+ (car l1) (car l2)) 10)))) ;this is a problem 

     (else (append (apa-add-help (cdr l1) (cdr l2)) 
        (list (+ (car l1) (car l2))))))) 

(apa-add-help (reverse l1) (reverse l2))) 

(apa-add '(4 7 9) '(7 8 4)) 
>'(1 1 1 5 1 3) 

我知道这个问题是在我的递归围绕，我颠倒了列表的顺序，以便更容易的过程，但我似乎无法理解如何添加我的模值（超值携带）到列表中的下一个对象。我怎样才能做到这一点？

Answer 1

reverse已在Racket中定义，因此不需要重新定义它。

我已经重写你的代码的版本是清晰的（对我来说，至少）：

(define (apa-add l1 l2) 

    (define (car0 lst) (if (empty? lst) 0 (car lst))) 
    (define (cdr0 lst) (if (empty? lst) empty (cdr lst))) 

    (let loop ((l1 (reverse l1)) (l2 (reverse l2)) (carry 0) (res '())) 
    (if (and (null? l1) (null? l2) (= 0 carry)) 
     res 
     (let* ((d1 (car0 l1)) 
       (d2 (car0 l2)) 
       (ad (+ d1 d2 carry)) 
       (dn (modulo ad 10))) 
      (loop (cdr0 l1) (cdr0 l2) (quotient (- ad dn) 10) (cons dn res)))))) 

如

-> (apa-add '(4 7 9) '(7 8 4)) 
'(1 2 6 3) 
-> (+ 479 784) 
1263 

car0和cdr0的功能，可以帮助我继续处理空列表作为零列表。

我引入了一个新的变量carry，它用于将值从迭代运送到迭代，就像手动执行一样。

EDIT 1

的named let等效于以下代码：

(define (apa-add l1 l2) 

    (define (car0 lst) (if (empty? lst) 0 (car lst))) 
    (define (cdr0 lst) (if (empty? lst) empty (cdr lst))) 

    (define (apa-add-helper l1 l2 carry res) 
    (if (and (null? l1) (null? l2) (= 0 carry)) 
     res 
     (let* ((d1 (car0 l1)) 
       (d2 (car0 l2)) 
       (ad (+ d1 d2 carry)) 
       (dn (modulo ad 10))) 
      (apa-add-helper (cdr0 l1) (cdr0 l2) (quotient (- ad dn) 10) (cons dn res))))) 

    (apa-add-helper (reverse l1) (reverse l2) 0 '())) 

编辑2

的非尾递归版本将是

(define (apa-add l1 l2) 

    (define (car0 lst) (if (empty? lst) 0 (car lst))) 
    (define (cdr0 lst) (if (empty? lst) empty (cdr lst)))  

    (define (apa-add-helper l1 l2 carry) 
    (if (and (null? l1) (null? l2) (= 0 carry)) 
     '() 
     (let* ((d1 (car0 l1)) 
       (d2 (car0 l2)) 
       (ad (+ d1 d2 carry)) 
       (dn (modulo ad 10))) 
      (cons dn (apa-add-helper (cdr0 l1) (cdr0 l2) (quotient (- ad dn) 10)))))) 

    (reverse (apa-add-helper (reverse l1) (reverse l2) 0)))