Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
2 / 2 / 0
Регистрация: 14.09.2014
Сообщений: 82
1

Рекурсия для обработки списков

11.10.2014, 12:40. Просмотров 1097. Ответов 13
Метки нет (Все метки)

Написать функцию, возвращающую для заданного списка lst список вида ((атом1 <число вхождений в список lst>) (атом2 <число вхождений в список lst>)...). Опишите функцию, выполняющую обработку. Приведите набор тестовых вызовов описанной функции, демонстрирующих всеварианты ее работы.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.10.2014, 12:40
Ответы с готовыми решениями:

Рекурсия для списков
Всем привет. Найти последний отличный от NIL атом в заданном списке: (A B (S 1) ((C)) NIL) —&gt; C...

простые рекурсивные функции для обработки списков
определить рекурсивные функции в соответствии с номером варианта. В данном задании все операции...

Построение итерационных программ для обработки списков
Помогите, пожалуйста, написать 2 программы с использованием цикла loop) Заранее огромное спасибо))...

Произведение всех лементов списка и под списков (Рекурсия)
Нужнов с помощью рекурсии найти произведение всех элементов списка и под списков входящих в этот...

__________________
13
Модератор
Эксперт Python
28529 / 15399 / 3043
Регистрация: 12.02.2012
Сообщений: 25,230
Записей в блоге: 4
11.10.2014, 12:48 2
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defun task (lst)
  (cond ((null lst) nil)
        (t (let* ((a (car lst))
                  (l1 (length lst))
                  (tail (remove a lst)) 
                  (l2 (length tail)))
             (cons (list a (- l1 l2)) (task tail))))))
 
 
==> task
 
(task '(1 2 3))
 
==> ((1 1) (2 1) (3 1))
 
(task '(1 2 3 1 2 3 4 5 6))
 
==> ((1 2) (2 2) (3 2) (4 1) (5 1) (6 1))
2
4493 / 4203 / 354
Регистрация: 12.05.2012
Сообщений: 2,959
13.10.2014, 11:29 3
как вариант:
Lisp
1
2
3
4
5
(defun atom-count (w &aux (v (remove-duplicates w)))
  (mapcar #'(lambda (a) (list a (count a w))) v))
 
> (atom-count '(a b b c c c))
((A 1) (B 2) (C 3))
3
2 / 2 / 0
Регистрация: 14.09.2014
Сообщений: 82
22.10.2014, 17:16  [ТС] 4
Catstail, нужна хвостовая рекурсия.
0
Модератор
Эксперт Python
28529 / 15399 / 3043
Регистрация: 12.02.2012
Сообщений: 25,230
Записей в блоге: 4
22.10.2014, 18:09 5
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(defun task (lst &optional (res nil))
  (cond ((null lst) (reverse res))
        (t (let* ((a (car lst))
                  (l1 (length lst))
                  (tail (remove a lst)) 
                  (l2 (length tail)))
                 (task tail (cons (list a (- l1 l2)) res))))))
 
==> task
 
(task '(1 2 3 1 2 3 4 5 6))
 
==> ((1 2) (2 2) (3 2) (4 1) (5 1) (6 1))
2
429 / 383 / 200
Регистрация: 12.08.2011
Сообщений: 1,610
23.10.2014, 11:39 6
На языке Factor:

Lisp
{ "a" 88 "b" 8 "a" 8 } dup length <hashtable> swap [ over inc-at ] each
 
--- Data stack:
H{ { "a" 2 } { "b" 1 } { 88 1 } { 8 2 } }
2
2 / 2 / 0
Регистрация: 14.09.2014
Сообщений: 82
23.10.2014, 20:54  [ТС] 7
Время выполнения length и remove зависит от длины исходного списка. Получается в каждом вызове - 3 вызова зависящих от длины. Напишите вспомогательную функцию (или обойдитесь этой, с дополнительными параметрами) в которой все нужные вычисления выполнятся за один проход (результат таких вычислений можно представить как список из трех элементов).

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defun task (lst &optional (res nil))
  (if (null lst) (reverse res)
        (let* ((a (car lst))
                  (l1 (length lst))
                  (tail (remove a lst)) 
                  (l2 (length tail)))
                 (task tail (cons (list a (- l1 l2)) res)))))
 
(print (task '(1 2 3)))
(print (task '(1 2 3 1 2 3 4 5 6)))
(print (task '(a b a b b c d 4 5 a 4)))
1
429 / 383 / 200
Регистрация: 12.08.2011
Сообщений: 1,610
24.10.2014, 11:17 8
Проще составить функцию, эквивалентную inc-at в моем коде на языке Factor. Вот концепт, но я не проверял:

Lisp
(defun inc-at (at ass)
    (let ((pair (assoc at ass)))
        (if pair (rplacd pair (1+ (cdr pair)))
                 (acons at 1 ass))))
2
4343 / 3350 / 342
Регистрация: 12.03.2013
Сообщений: 5,838
24.10.2014, 19:16 9
Я бы вместо (rplacd pair (1+ (cdr pair))) написал (incf (cdr pair)). Вообще, меня пугают rplaca и rplacd, я пишу (setf (cdr x) y), а incf построен на setf, и можно использовать ту же магию. А в качестве стилистического пожелания я бы предложил не писать ветку "нет" сразу под ифом, а то она воспринимается как "да".

Может, стоило бы хеш-таблицу использовать.
1
Модератор
Эксперт Python
28529 / 15399 / 3043
Регистрация: 12.02.2012
Сообщений: 25,230
Записей в блоге: 4
24.10.2014, 19:33 10
Lisp
1
2
3
4
5
6
7
(defun add-el (a lst)
  (cond ((null lst) (list (list a 1)))
        ((eq a (caar lst)) (cons (list (caar lst) (+ 1 (cadar lst))) (cdr lst)))
        (t (cons (car lst) (add-el a (cdr lst))))))
 
(defun task (lst &optional (res nil))
  (if (null lst) res (task (cdr lst) (add-el (car lst) res))))
1
2 / 2 / 0
Регистрация: 14.09.2014
Сообщений: 82
29.10.2014, 20:09  [ТС] 11
Нужна хвостовая рекурсия и одна глобальная функция...
0
castorsky
29.10.2014, 21:35
  #12

Не по теме:

через месяц окажется что нужно было написать на паскале

0
Заблокирован
01.11.2014, 11:44 13
Цитата Сообщение от Kris123 Посмотреть сообщение
Нужна хвостовая рекурсия и одна глобальная функция...
Попробуй включить мозг и пойти в поиск, прежде чем требовать что-то в таком тоне. Тема обсуждалась неоднократно!
Вот например https://www.cyberforum.ru/lisp/thread1125677.html
1
2 / 2 / 0
Регистрация: 14.09.2014
Сообщений: 82
02.11.2014, 13:41  [ТС] 14
ur_naz, я уже давно сделала все! к сожалению, тут нельзя удалять комментарии)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.11.2014, 13:41

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Рекурсия для линейных списков
Пусть в файле хранятся записи со сведениями об автомобилях и их владельцах (марка, номер ГАИ,...

Применение рекурсии для обработки списков
Все вхождения заданного элемента уменьшите на заданное число.не работает! в чем ошибка?...

Применение рекурсии для обработки списков
Замените голову списка.

Применение рекурсии для обработки списков
6) Выведите максимальный элемент.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.