Задачки по Лиспу

@maje · Регистрация: 21.10.2013

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

1. Есть список с подсписками вида ((1, (2, 4, z, 6), 7, ), 9, 8, ... ). Подсчитать количество элементов, расположенных на втором и четвертом уровнях вложенности.
2. С ассоциативного списка (a-1 b-2 c-3 d-4 e-5 f-6 g-7 ...) выбрать все значения, которые больше введенного числа. Собрать в список их ключи.

@_sg · 24.10.2013, 23:53

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun dive-elms (n w &aux (a (car w)) (d (cdr w)))
   (cond ((null w) nil)
         ((= n 0) w)
         ((atom a) (dive-elms n d))
         ((nconc (dive-elms (1- n) a) (dive-elms n d)))))
 
(defun dive-count (n w)
  (count-if #'atom (dive-elms n w)))
 
 
> (dive-count 2 '(a(b(((c)) 1)d e)((f))((2(g))3)))
3
> (dive-count 4 '(a(b(((c)) 1)d e)((f))((2(g))3)))
1

Добавлено через 59 секунд

Lisp
1
2
3
4
5
6
7
8
9
10
(defun dive-count (n w &aux (a (car w)) (d (cdr w)))
   (cond ((null w) 0)
         ((= n 0) (count-if #'atom w))
         ((atom a) (dive-count n d))
         ((+ (dive-count (1- n) a) (dive-count n d)))))
 
> (dive-count 2 '(a(b(((c)) 1)d e)((f))((2(g))3)))
3
> (dive-count 4 '(a(b(((c)) 1)d e)((f))((2(g))3)))
1

@maje · 25.10.2013, 01:10 **[ТС]**

К сожалению, в HomeLisp'е не работает. А в какой среде вы пишете?

@_sg · 25.10.2013, 08:17

Которая работает с Common Lisp - SBCL, CLISP, LispWorks.

@Catstail · 25.10.2013, 10:48

Вот решение _sg, адаптированное под HomeLisp:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(defun dive-elms (n w &aux (a (car w)) (d (cdr w)))
   (cond ((null w) nil)
         ((= n 0) w)
         ((atom a) (dive-elms n d))
         (t (nconc (dive-elms (1- n) a) (dive-elms n d)))))
 
(defun dive-count (n w)
  (apply '+ (mapcar #'(lambda (x) (if (atom x) 1 0)) (dive-elms n w))))
 
 
(dive-count 2 '(a(b(((c)) 1)d e)((f))((2(g))3)))
 
==> 3
 
(dive-count 4 '(a(b(((c)) 1)d e)((f))((2(g))3)))
 
==> 1

Собственно, проблем было две:

1) в cond нельзя опускать ветвь с "(t"
2) в HomeLisp (пока) нет функции count-if

Добавлено через 6 минут
Вот вторая задача:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
;; Выбор из ассоциативного списка alist значений, больших n
 
(defun task-1 (alist n)
 (remove nil (mapcar #'(lambda (x) (if (> (cdr x) n) (cdr x) nil)) alist)))
 
==> task-1
 
(task-1 '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (f . 6) (g . 7)) 4)
 
==> (5 6 7)
 
;; список ключей ассоциативного списка alist со значениями, большими n
 
(defun task-2 (alist n)
 (remove nil (mapcar #'(lambda (x) (if (> (cdr x) n) (car x) nil)) alist)))
 
==> task-2
(task-2 '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (f . 6) (g . 7)) 4)
 
==> (e f g)

@_sg · 25.10.2013, 11:04

Lisp
1
2
3
4
5
(defun keys+ (w n)
  (mapcar #'cdr  (remove-if #'(lambda (a) (<= a n)) w  :key #'cdr)))
 
> (keys+ '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (f . 6) (g . 7)) 4)
(5 6 7)

Добавлено через 34 секунды

Lisp
1
2
3
4
5
(defun keys+ (w n)
  (mapcar #'cdr  (remove-if-not #'(lambda (a) (> a n)) w  :key #'cdr)))
 
> (keys+ '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (f . 6) (g . 7)) 4)
(5 6 7)

@Catstail · 25.10.2013, 11:06

А вот еще одно решение первой задачи (в одну функцию):

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
(defun lv-count (lst lv &optional (c 0))
  (cond ((> c lv) 0)
        ((= lv c)
         (let ((r nil))
              (dolist (i lst (length r))
                (when (atom i) (push i r)))))
        (t
           (apply '+ (mapcar #'(lambda (x) (if (atom x) 0 (lv-count x lv (+ c 1)))) lst)))))
 
==> lv-count
 
(lv-count '(1 2 (3 4) (((5))) 6 (7 8)) 0)
 
==> 3
 
(lv-count '(1 2 (3 4) (((5))) 6 (7 8)) 1)
 
==> 4
 
(lv-count '(1 2 (3 4) (((5))) 6 (7 8)) 2)
 
==> 0
 
(lv-count '(1 2 (3 4) (((5))) 6 (7 8)) 3)
 
==> 1
 
(lv-count '(1 2 (3 4) (((5))) 6 (7 8)) 4)
 
==> 0

@maje · 26.10.2013, 16:14 **[ТС]**

спасибо!

Добавлено через 18 часов 15 минут
Очень нужна помощь со след. задачами:
3. Определить функционал, который с линейного числового списка выбирает все четные числа. Пример: (1 2 3 4 ...) ==> (2 4 ...). Длина списка не определена.

А вот посложнее задачки:
4. Написать функцию, которая вычисляет сечение двух множеств. (Без дубликатов атомов в множествах)
5. На графе задан циклический маршрут ((a c) (c e) (e d) (d c) (c b) (b a)), где (a b c d e) - вершины графа. Определить является ли он простым циклом. (задача по графам)

@_sg · 26.10.2013, 16:25

Lisp
1
2
3
4
5
6
7
(defun evens (w)
  (cond ((null w) nil)
        ((evenp (car w)) (cons (car w) (evens (cdr w))))
        (t (evens (cdr w)))))
 
> (evens '(0 1 2 3 4 5))
(0 2 4)

Добавлено через 59 секунд

Lisp
1
2
3
4
5
(defun evens (w)
  (when w (if (evenp (car w)) (cons (car w) (evens (cdr w))) (evens (cdr w)))))
 
> (evens '(0 1 2 3 4 5))
(0 2 4)

Добавлено через 54 секунды

Lisp
1
2
3
4
5
(defun evens (w)
  (remove-if-not #'evenp w))
 
> (evens '(0 1 2 3 4 5))
(0 2 4)

Добавлено через 1 минуту

Lisp
1
2
3
4
5
(defun evens (w)
  (loop for a in w when (evenp a) collect a))
 
> (evens '(0 1 2 3 4 5))
(0 2 4)

Добавлено через 1 минуту

Lisp
1
2
3
4
5
6
7
(defun _intersection (w v)
  (cond ((null w) nil)
        ((member (car w) v) (cons (car w) (_intersection (cdr w) v)))
        ((_intersection (cdr w) v))))
 
> (_intersection '(a s d f g h ) '(q a w s e d r))
(A S D)

Добавлено через 27 секунд

Lisp
1
2
3
4
5
(defun _intersection (w v) 
  (loop for a in w when (member a v) collect a))
 
> (_intersection '(a s d f g h ) '(q a w s e d r))
(A S D)

Добавлено через 19 секунд

Lisp
1
2
3
4
5
(defun _intersection (w v)
  (remove-if-not #'(lambda (a) (member a v)) w)) 
 
> (_intersection '(a s d f g h ) '(q a w s e d r))
(A S D)

@maje · 26.10.2013, 16:56 **[ТС]**

благодарю, _sg!

@Catstail · 26.10.2013, 19:16

Вот еще две реализации пересечения:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(defun inters (v w &optional r)
  (cond ((null v) r)
        ((member (car v) w) (inters (cdr v) w (cons (car v) r)))
        (t (inters (cdr v) w r))))
 
==> inters
 
(inters '(a s d f g h ) '(q a w s e d r))
 
==> (d s a)
 
(defun inters (v w)
  (let ((r nil))
    (dolist (i v r)
      (when (member i w) (push i r)))))
 
==> inters
 
(inters '(a s d f g h ) '(q a w s e d r))
 
==> (d s a)

Добавлено через 4 минуты
Если считать простым циклом цикл, в котором не повторяются ребра, то вот:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun simpl (loo)
  (cond ((null loo) t)
        ((member (car loo) (cdr loo)) nil)
        (t (simpl (cdr loo)))))
 
==> simpl
 
(simpl '((a c) (c e) (e d) (d c) (c b) (b a)))
 
==> T
 
(simpl '((a c) (c e) (e d) (d c) (c e) (e b) (b c) (c b) (b a)))
 
==> NIL

@_sg · 26.10.2013, 19:29

Lisp
1
2
3
4
5
6
7
(defun _intersection (w v &aux (a (car w)))
  (when w (if (member a v)
              (cons a (_intersection (cdr w) v))
              (_intersection (cdr w) v))))
 
> (_intersection '(a s d f g h ) '(q a w s e d r))
(A S D)

@maje · 04.11.2013, 00:19 **[ТС]**

Сообщение от Catstail

Если считать простым циклом цикл, в котором не повторяются ребра

Спасибо за вариант.
Если учитывать следующие определения:

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

Название: pic1.png
Просмотров: 60

Размер: 1.6 Кб

Название: pic1.png
Просмотров: 60

Размер: 1.6 Кб

Вот, например, по приведенному рисунку можно сказать, что в графе существуют
2 непростых цикла:
((b a)(a c)(c e)(e d)(d c)(c b))
((b a)(a c)(c d)(d e)(e c)(c b))
и 2 простых цикла:
((b a)(a c)(c b))
((c d)(d e)(e c))

Как реализовать ту же задачку (5)? Буду очень благодарен!

@Catstail · 04.11.2013, 10:03

Сообщение от maje

Как реализовать ту же задачку (5)

- и где ее условие?

@maje · 04.11.2013, 14:36 **[ТС]**

Вот она:
5. На графе задан циклический маршрут ((a c) (c e) (e d) (d c) (c b) (b a)), где (a b c d e) - вершины графа. Определить является ли он простым циклом. (задача по графам)

@Catstail · 04.11.2013, 14:44

Так я же ее и решил: см. мой пост от 26.10.13

@maje · 04.11.2013, 14:47 **[ТС]**

да, я видел, но не корректно работает, нужно учитывать еще и неповторяимость вершин на графе (суть простого цикла)

@Catstail · 04.11.2013, 15:17

Тогда вот:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun is-simpl (loo)
  (let ((beg (mapcar 'car loo))
        (end (mapcar 'cadr loo)))
      (and (= (length beg) (length (setof beg)))
           (= (length end) (length (setof end))))))
 
==> is-simpl
 
(is-simpl '((a c) (c e) (e d) (d c) (c b) (b a)))
 
==> NIL
 
(is-simpl '((a c) (c e) (e d) (d f) (f b) (b a)))
 
==> T

@maje · 05.11.2013, 23:15 **[ТС]**

Гениально! Спасибо огромное)

@maje · 06.11.2013, 03:35 **[ТС]**

Задача. Определить функционал, который с линейного числового списка выбирает все четные числа. Пример: (1 2 3 4 ...) ==> (2 4 ...). Длина списка не определена.

Эта задача уже решалась.

Сообщение от _sg

Lisp
1
2
3
4
5
6
7
(defun evens (w)
  (cond ((null w) nil)
        ((evenp (car w)) (cons (car w) (evens (cdr w))))
        (t (evens (cdr w)))))
 
> (evens '(0 1 2 3 4 5))
(0 2 4)

Помогите реализовать этот код функционалом (переделать в функционал), т.е. чтобы в созданный функционал передавались два аргумента: первый - функция, которая будет обрабатывать (проверять на четность) элементы списка, переданного в качестве второго аргумента.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

Задачки по Лиспу

Решение

Решение

@maje 1 / 1 / 0 Регистрация: 21.10.2013 Сообщений: 18

	Задачки по Лиспу 24.10.2013, 22:45. Показов 2599. Ответов 22 Метки нет (Все метки) 1. Есть список с подсписками вида ((1, (2, 4, z, 6), 7, ), 9, 8, ... ). Подсчитать количество элементов, расположенных на втором и четвертом уровнях вложенности. 2. С ассоциативного списка (a-1 b-2 c-3 d-4 e-5 f-6 g-7 ...) выбрать все значения, которые больше введенного числа. Собрать в список их ключи. 0

@maje 1 / 1 / 0 Регистрация: 21.10.2013 Сообщений: 18
	25.10.2013, 01:10 [ТС]
	К сожалению, в HomeLisp'е не работает. А в какой среде вы пишете? 0

@_sg 4706 / 4401 / 380 Регистрация: 12.05.2012 Сообщений: 3,100
	25.10.2013, 08:17
	Которая работает с Common Lisp - SBCL, CLISP, LispWorks. 0

@maje 1 / 1 / 0 Регистрация: 21.10.2013 Сообщений: 18
	26.10.2013, 16:14 [ТС]
	спасибо! Добавлено через 18 часов 15 минут Очень нужна помощь со след. задачами: 3. Определить функционал, который с линейного числового списка выбирает все четные числа. Пример: (1 2 3 4 ...) ==> (2 4 ...). Длина списка не определена. А вот посложнее задачки: 4. Написать функцию, которая вычисляет сечение двух множеств. (Без дубликатов атомов в множествах) 5. На графе задан циклический маршрут ((a c) (c e) (e d) (d c) (c b) (b a)), где (a b c d e) - вершины графа. Определить является ли он простым циклом. (задача по графам) 0

@maje 1 / 1 / 0 Регистрация: 21.10.2013 Сообщений: 18
	26.10.2013, 16:56 [ТС]
	благодарю, _sg! 0

@maje 1 / 1 / 0 Регистрация: 21.10.2013 Сообщений: 18
	04.11.2013, 14:36 [ТС]
	Вот она: 5. На графе задан циклический маршрут ((a c) (c e) (e d) (d c) (c b) (b a)), где (a b c d e) - вершины графа. Определить является ли он простым циклом. (задача по графам) 0

@Catstail Супер-модератор 38163 / 21098 / 4306 Регистрация: 12.02.2012 Сообщений: 34,686 Записей в блоге: 14
	04.11.2013, 14:44
	Так я же ее и решил: см. мой пост от 26.10.13 0

@maje 1 / 1 / 0 Регистрация: 21.10.2013 Сообщений: 18
	04.11.2013, 14:47 [ТС]
	да, я видел, но не корректно работает, нужно учитывать еще и неповторяимость вершин на графе (суть простого цикла) 0

@maje 1 / 1 / 0 Регистрация: 21.10.2013 Сообщений: 18
	05.11.2013, 23:15 [ТС]
	Гениально! Спасибо огромное) 0