При использовании рекурсии, как я могу добавить или объединить несколько пар в один более длинный список?

Question

Это домашнее задание, поэтому, пожалуйста, укажите правильное направление без решения.По сути, в Схеме я пытаюсь создать многоразрядный сумматор, начиная с логических элементов.

Спасибо за чтение / помощь.

Пример, который я использую, - это добавление 101001 и 011101 с 1 переносом.
Я чувствую, что у меня есть список и я добавляю его везде?Но если это правильный шаг, я не могу заставить это работать.

(define l-and (lambda (x y) (if (and (equal? x 1) (equal? y 1)) 1 0)))

(define l-or (lambda (x y) (if (or (equal? x 1) (equal? y 1)) 1 0)))

(define l-xor (lambda (x y) (if (or (equal? (l-and x y) 1) (and (equal? x 0) (equal? y 0)) ) 0 1)))

(define l-not (lambda (x) (if (equal? x 0) 1 0)))

(define fulladdr (lambda (x y z)
  (cons
  (l-xor (l-xor x y) z)
  (l-or (l-and x y) (l-and z (l-xor x y)))
  )
))

(define (removelast lis)
  ;(display (reverse(cdr (reverse lis)))) For debugging
  (if (null? (cdr lis)) 
  '() 
  (reverse(cdr (reverse lis)
))))

(define (last-element lis)
  ;(display (car(reverse lis))) For debugging
  (if (null? (cdr lis)) 
  '() (car(reverse lis))
))

(define n-bit-addr (lambda (l1 l2 x) 
  (if (or (null? l1) (null? l2)) 
  '() 
  (let ((carry (cdr (fulladdr (last-element l1) (last-element l2) x)))) 
  (let (( sum (car (fulladdr (last-element l1) (last-element l2) x))))
  ;(display carry) For debugging
  (cons
    (fulladdr (last-element l1) (last-element l2) x)
      (n-bit-addr (removelast l1) (removelast l2) carry)

)))))

Когда я запускаю свой код с этим примером, парой других, я получаю правильный вывод, вроде: ((1. 1) (1. 0) (1. 0) (0.1) (0. 1) (0. 1)) Я пытаюсь выяснить, как отформатировать это так, чтобы мой вывод был (111000.1).В основном (Binary. FinalCarry)

Answer 1

Вот некоторые наблюдения.Сумматор использует перенос, поэтому вам нужно будет указывать от значащих цифр до самых значимых.

Список создается от начала к началу.например.(1 2) может быть создано (cons 1 (cons 2 '())), что означает, что второй аргумент (cons 2 '()) должен быть завершен.

Я полагаю, ваши аргументы - это двоичные цифры в списке, такие как (1 0 1 0) как 10.Если у вас есть помощник или имя let, у вас могут быть два аргумента: перенос и сумма в качестве параметров, чтобы вы могли использовать их в качестве состояния.Также вы звоните fulladdr с одинаковыми аргументами 3 раза.Вот что, я думаю, вы должны сделать:

(define (n-bit-addr l1 l2)
  (helper (reverse l1) (reverse l2) 0 '())) 

Это лишает цели получение и удаление «последнего» элемента, а скорее выборку и удаление первого, что гораздо проще сделать в Схеме.

Теперь вот и все остальное.Я отвел некоторые из спорных, например.то, что происходит, когда вы делаете (n-bit-addr '(1 1) '(1 1 1 0)), волшебным образом обходится без непосредственного использования car и cdr.

(define (helper l1 l2 carry acc)
  ;; actual implementation of n-bit-addr
  (if (finished? l1 l2)
      (finish acc carry)
      (let* ((res (fulladdr (car0 l1) (car0 l2) carry))
             (sum (car res))
             (carry (cdr res)))
        (helper (cdr* l1) <??> <??> <??>))))

(define (car0 lst)
  ;; returns 0 if lst is null? (car lst) otherwise
  )

(define (cdr* lst)
  ;; return '() if lst is null? (cdr lst) otherwise
  )

(define (finished? l1 l2)
  ;; return #t is both are null?
  )

(define (finish sum carry)
  ;; return whatever structure one would want with the last result
  ;; I would imagine carry could be the the highest bit if it's set. thus
  ;; (n-bit-addr '(1) '(1)) ; ==> (1 0)
  )

Теперь, если (1 0 1 0) неудовлетворительно, вы должны сделать number->logic и logic->number, которые преобразуют (1 0 1 0) в #b1010.Это легко сделать с помощью итерации и арифметики списка.Поскольку вы хотите знать, как составлять списки для нумерации, я сделаю по-другому:

(define (number->logic n)
  (let loop ((n n) (acc '()))
    (cond ((not (zero? n)) (loop (quotient n 2) (cons (remainder n 2) acc)))
          ((null? acc) '(0))
          (else acc))))

(number->logic #b1010) ; ==> (1 0 1 0)

Обратите внимание, что #b1010 - это просто изящный способ написания 10

(number->logic 10) ; ==> (1 0 1 0)

Обратным путем будет запуск аккумулятора с 0 и для каждого элемента в списке, чтобы умножить аккумулятор на 2 и добавить бит.Когда список равен null?, аккумулятор будет номером.

(logic->number '(1 0 1 0)) ; ==> 10

Я помню, как строил сумматоры с помощью nand gates в школе, но я не делал этого в программировании.Тебе стоит попробовать это.