使用数字列表进行任意精度加法 [英] arbitrary precision addition using lists of digits

问题描述

我想要做的是将两个列表合并在一起，就像每个列表都是整数一样。

What I'm trying to do is take two lists and add them together like each list is a whole number.

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

我知道问题是围绕递归，我颠倒了列表的顺序以简化处理过程，但是我似乎不明白如何将我的模值（继承的值）添加到列表中的下一个对象。我该怎么做？

I know that the problem is revolved around my recursion, I reversed the order of the lists to allow for easier process, however I can't seem to understand how to add my modulo value (carried over value) to the next object in the list. How can I do this?

推荐答案

reverse 已经在球拍中定义了因此，无需重新定义它。

reverse is already defined in Racket so there's no need to redefine it.

我已经将您的代码重写为一个更清晰的版本（至少对我而言）：

I have rewritten your code for a version that is clearer (to me, at least):

(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 是帮助我继续将空列表作为零列表处理的函数。

car0and cdr0 are functions that help me to continue processing empty lists as a list of zeroes.

I引入了一个新变量进位，该进位用于在每次迭代之间进行值赋值，就像您手动进行操作一样。

I introduced a new variable, carry, which is used to carry a value from iteration to iteration, just as you do it manually.

编辑1

名为$ let的等效于以下代码：

The named let is equivalent to the following code:

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

这篇关于使用数字列表进行任意精度加法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！