Вычитание списков в двоичной системе счисления

@Alisa_lime · Регистрация: 10.12.2012

Студворк — интернет-сервис помощи студентам

Доброго времени суток, помогите реализовать операцию вычитания в двоисной системе счисления.

На вход подаются два списка, представляющих собой двоичные числа. Результат - разность этих списков.
Считается, что l1 > l2 по условию.

Решила воспользоваться заменой вычитания на сложение, но не все получается..

razr - уранивает разряды введенных списков
inv - заменяем 1 на 0 и наоборот
add - прибавляем к l2 1. складываем два числа. удаляем старшую единицу

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun razr (l1 l2)
(cond
    ...
(let ((l (length l1)))
 
)
)
 
(defun inv (l2)
  (cond ((null l2) nil)
        ((= (car l2) 0) (cons 1 (inv (cdr l2)))) (t (cons 0 (inv (cdr l2))))
        ((cons (car l2) (inv (cdr l2))))
    )
)
 
(defun add (l1 l2)
(cond 
( (> (length l1) (length l2)) (razr l1 l2))
(inv l2)
)

Из всего этого работает только инверсия
Может я вообще не в том направлении мыслю, пожалуйста, помогите

@_sg · 11.12.2012, 21:46

Common Lisp:

Lisp
1
2
3
4
5
(defun binary-abstract (w)
  (format nil "~b" (reduce #'- (mapcar #'(lambda (a) (parse-integer (write-to-string a) :radix 2)) w))))
 
> (binary-abstract '(110101 100101))
"10000"

@Alisa_lime · 11.12.2012, 21:58 **[ТС]**

_sg, Спасибо, вот только вычитание нужно реализовать с помощью простых функций типа cdr car lenght

@Catstail · 12.12.2012, 10:56

Вот вычитание "из первых принципов"... Вычитаемое не должно быть больше уменьшаемого (как в задании). Среда - HomeLisp:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
(defun align-bin (lst n)
   (cond ((= n (length lst)) lst)
         ((> n (length lst)) (cons 0 (align-bin lst (- n 1))))
         (t (raiseerror "Ошибка при вызове align-bin"))))
 
 
(defun inv-bin (lst)
  (cond ((null lst) nil)
        (t (cons (- 1 (car lst)) (inv-bin (cdr lst))))))
         
(defun sub-bin (L1 L2)
  (let* ((Res nil)
         (Resn nil) 
         (Sh 0) 
         (z  0)
         (ml (max (length L1) (length L2)))
         (A1 (reverse (align-bin L1 ml)))
         (A2 (reverse (inv-bin (align-bin L2 ml)))))
        (dotimes (i ml Res)
          (setq z (+ Sh (car A1) (car A2)))
          (setq Res (append Res (list (% z 2))))
          (setq Sh (\ z 2))
          (setq A1 (cdr A1))
          (setq A2 (cdr A2))
        )
        (if (= Sh 0) 
            (reverse (inv-bin Res))
            (progn
             (dotimes (i ml Resn)
               (setq z (+ Sh (car Res)))
               (setq Resn (append Resn (list (% z 2))))
               (setq Sh (\ z 2))
               (setq Res (cdr Res))
             )
             (reverse (if (> Sh 0) (inv-bin (resn)) resn))
            )
        )
))
    
 
(sub-bin '(1 1 1 1) '(1 0 1))  ;; 15 - 5
 
==> (1 0 1 0) ;; =10
 
(sub-bin '(1 1 1 1) '(1 1)) ;; 15 - 3
 
==> (1 1 0 0) ;; = 12

@Alisa_lime · 12.12.2012, 11:38 **[ТС]**

Спасибо, но нужно использовать максимум функцию reverse.
вот со сложением получилось и вычитание должно быть по аналогии. примерно таким:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(defun binadd (x y)
(reverse (preobr (add (reverse x) (reverse y))))
)
 
(defun preobr (x)
(cond 
((null x) x)
((null (cdr x))
(cond
((< (car x) 2) x)
(t (list (- (car x) 2) 1))))
 
(t (cons
(cond
((< (car x) 2) (car x))
(t (- (car x) 2)))
(preobr 
(cond
((< (car x) 2) (cdr x))
(t (rplaca (cdr x) (+ (cadr x) 1))))
)))
)
)
 
(defun add (x y)
(cond 
((null x) (if 
(null y) nil 
y)) 
((null y) (if 
(null x) nil 
x))
(t (cons (+ (car x) (car y)) (add (cdr x) (cdr y))))
)
)

Добавлено через 12 минут
так. кажется получилось. только нули с высших разрядов удалить не знаю как

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(defun b (x y)
(reverse (preobr (add (reverse x) (reverse y))))
)
 
(defun preobr (x)
(cond 
((null x) x)
((null (cdr x))
(cond
((< (car x) 2) x)
(t (list (- (car x) 2) 1))))
 
(t (cons
(cond
((> (car x) -1) (car x))
(t (+ (car x) 2)))
(preobr 
(cond
((> (car x) -1) (cdr x))
(t (rplaca (cdr x) (- (cadr x) 1))))
)))
)
)
 
(defun add (x y)
(cond 
((null x) (if 
(null y) nil 
y)) 
((null y) (if 
(null x) nil 
x))
(t (cons (- (car x) (car y)) (add (cdr x) (cdr y))))
)
)

@Catstail · 12.12.2012, 11:48

Это-то как раз несложно:

Lisp
1
2
3
4
5
6
7
8
9
10
(defun del-zero (lst)
  (cond ((= 1 (length lst)) lst)
        ((= 0 (car lst)) (del-zero (cdr lst)))
        ((= 1 (car lst)) lst)))
 
==> del-zero
 
(del-zero '(0 0 1 0 1))
 
==> (1 0 1)

Вот только применение rplaca/rplacd может вызвать нарекание...

@Alisa_lime · 12.12.2012, 14:32 **[ТС]**

Catstail, Спасибо, Вы всегда приходите на помощь)
очень благодарна Вам.

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@Alisa_lime 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 11
	11.12.2012, 21:58 [ТС]
	_sg, Спасибо, вот только вычитание нужно реализовать с помощью простых функций типа cdr car lenght 0

@Alisa_lime 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 11
	12.12.2012, 14:32 [ТС]
	Catstail, Спасибо, Вы всегда приходите на помощь) очень благодарна Вам. 0