Блог

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

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

Примером, который я использую, является добавление 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). В основном (двоичный файл. FinalCarry)

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

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

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

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

Это противоречит цели получения и удаления «последнего» элемента, а скорее извлечения и удаления первого, что намного проще сделать в Scheme.

Теперь вот остальное. Я абстрагировался от некоторых проблем, например. то, что происходит, когда вы делаете (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, но я не делал этого в программировании. Вы должны попробовать.