0 / 0 / 0
Регистрация: 11.11.2016
Сообщений: 9
1

Написать рекурсивную функцию, удаляющую x (последнее вхождение) из списка l

11.11.2016, 16:36. Показов 2465. Ответов 22
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Прочитать из файла значение переменной x. Написать рекурсивную функцию, удаляющую x
(последнее вхождение) из списка l. Список задать при вызове функции.
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun l1(l)
(reverse (cdr(reverse l)))
)
;переворачивает список, берет от полученного хвост, и полученный
;хвост переворачивает
 
(defun ud (l &key x)
(cond ((null l) l) 
     ( (equal (car l) x)(cdr l))
     ( (no equal (car 1) x) (cdr 1))
 (t (cons (ud (l)) (car (reverse l))))
 
(setf 'f (open "C:/lispprakt/input78.txt"))
(ud l :x (read f))
(close f)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.11.2016, 16:36
Ответы с готовыми решениями:

Написать рекурсивную функцию, удаляющую из многоуровневого списка символы
Напишите функцию, аргументом которой является список, удаляющую из этого списка все нечисловые...

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

Написать программу, удаляющую из строки первое и последнее вхождение заданной подстроки
2.*Написать программу, удаляющую из строки первое и последнее вхождение заданной подстроки. 3.*Все...

Написать функцию primer(str1, str2) удаляющую из строки str1 последнее вхождение строки str2. Функция возвращает указатель str1
помогите пожалуйста

22
4816 / 2276 / 287
Регистрация: 01.03.2013
Сообщений: 5,944
Записей в блоге: 27
11.11.2016, 16:44 2
Так надо просто вылить воду из чайника и свести к предыдущей задаче реверснуть список, удалить первое вхождение и снова реверснуть. А первое вхождение удалили в соседней теме уже, так что оно удалено - осталось только 2 раза реверснуть список
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
35593 / 19491 / 4074
Регистрация: 12.02.2012
Сообщений: 32,531
Записей в блоге: 13
12.11.2016, 10:13 3
_Ivana, не согласен. Два реверса - много. Можно проще:
Lisp
1
2
3
(defun dellast (lst)
   (cond ((null (cdr lst)) nil)
              (t (cons (car lst) (dellast (cdr lst))))))
1
4816 / 2276 / 287
Регистрация: 01.03.2013
Сообщений: 5,944
Записей в блоге: 27
12.11.2016, 10:20 4
Catstail,

1) ваш код удаляет последний элемент списка безо всяких проверок на равенство х

2) согласен, что можно его чуть допилить и написать примерно так - бежим по списку, если текущий элемент = х - то смотрим, есть ли х в хвосте списка - и если есть, то пропускаем и бежим дальше, а если нет - то удаляем и останавливаемся. НО! Будет ли такой вариант оптимальнее моего? Имхо - нет. Ибо если у нас 20 вхождений х в список, мы будем 20 раз пробегать и искать его в хвосте. А в моем варианте сложность 3n - реверс + пробежка поиска первого х + реверс.
1
4687 / 4383 / 379
Регистрация: 12.05.2012
Сообщений: 3,089
12.11.2016, 10:21 5
как вариант:
Lisp
1
2
3
4
5
(defun -butlast (w)
  (when (cdr w) (cons (car w) (-butlast (cdr w)))))
 
> (-butlast '(a b))
(A)
0
4816 / 2276 / 287
Регистрация: 01.03.2013
Сообщений: 5,944
Записей в блоге: 27
12.11.2016, 10:22 6
Или я ошибся в телепатии и в задаче надо действительно написать батласт безо всяких проверок на равенство х.
0
4687 / 4383 / 379
Регистрация: 12.05.2012
Сообщений: 3,089
12.11.2016, 10:41 7
Lisp
1
2
3
4
5
(defun -butlast (a w)
  (remove a w :count 1 :from-end t))
 
> (-butlast 'a '(a b))
(B)
Добавлено через 14 минут
Lisp
1
2
3
4
5
6
7
8
9
10
(defun butlast-elm (a w)
  (cond ((null w) nil)
        ((equalp (car w) a) (if (member a (cdr w))
                                (cons (car w)
                                      (butlast-elm a (cdr w)))
                                (butlast-elm a (cdr w))))
        ((cons (car w) (butlast-elm a (cdr w))))))
 
> (butlast-elm 'a '(a b a b))
(A B B)
Добавлено через 2 минуты
Lisp
1
2
3
4
5
6
7
8
9
(defun butlast-elm (e w &aux (a (car w)) (d (cdr w)))
  (cond ((null w) nil)
        ((equalp a e) (if (member e d)
                          (cons a (butlast-elm e d))
                          (butlast-elm e d)))
        ((cons a (butlast-elm e d)))))
 
> (butlast-elm 'a '(a b a b))
(A B B)
2
4816 / 2276 / 287
Регистрация: 01.03.2013
Сообщений: 5,944
Записей в блоге: 27
12.11.2016, 10:49 8
_sg, ваш средний вариант пишется с парой улучшений:
Lisp
1
2
3
4
5
6
7
8
(defn butlast-elm (a w)
    cond (null? w) nil
         (and (eq? (car w) a) (not (elem a (cdr w)))) (cdr w)
         (cons (car w) (butlast-elm a (cdr w)) ))
 
(butlast-elm 'a '(a b a b))
 
=> (a b b)
2
4687 / 4383 / 379
Регистрация: 12.05.2012
Сообщений: 3,089
12.11.2016, 11:10 9
_Ivana, спасибо, как вариант:
Lisp
1
2
3
4
5
6
7
8
9
(defun butlast-elm (e w &aux (a (car w)) (d (cdr w)))
  (cond ((null w) nil)
        ((equalp a e) (if (member e d)
                          (cons a (butlast-elm e d))
                          d))
        ((cons a (butlast-elm e d)))))
 
> (butlast-elm 'a '(a b a b))
(A B B)
1
4816 / 2276 / 287
Регистрация: 01.03.2013
Сообщений: 5,944
Записей в блоге: 27
12.11.2016, 11:16 10
_sg, никак не хотите объединить кейсы конса с продолжением в один? Или таким образом ограничиваете пробежку member когда голова не равна е? Мой кот эксплуатирует ленивость форы and, которая у меня определена как
Lisp
1
defmacro and (x y) cond x y false
и не будет вычислять второй аргумент, если первый уже ложь. Поэтому в моем примере пробежка поиска
Lisp
1
(not (elem a (cdr w)))
будет только когда голова равна а, поэтому неоптимальности не будет (в этом смысле, т.к. общая неоптимальность алгоритма описана несколькими постами выше). Но конечно для таких хаков надо знать тонкости и фичи конкретного языка.
2
4687 / 4383 / 379
Регистрация: 12.05.2012
Сообщений: 3,089
12.11.2016, 11:17 11
Lisp
1
2
3
4
5
6
(defun butlast-elm (e w &aux (a (car w)) (d (cdr w)))
  (when w (if (and (equalp a e) (not (member e d))) d
              (cons a (butlast-elm e d)))))
 
> (butlast-elm 'a '(a b a b))
(A B B)
1
0 / 0 / 0
Регистрация: 11.11.2016
Сообщений: 9
12.11.2016, 11:54  [ТС] 12
А вы можете написать задачу полностью,чтобы она брала элементы из файла)Прочитать из файла значение переменной x. Написать рекурсивную функцию, удаляющую x
(последнее вхождение) из списка l. Список задать при вызове функции.
Реализовать функцию в
четырёх вариантах с использованием обязательных, необязательных, остаточных,
именованных параметров. Исходные данные прочитать из файла
0
4687 / 4383 / 379
Регистрация: 12.05.2012
Сообщений: 3,089
12.11.2016, 12:52 13
d:/test.txt
a
a
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun butlast-elm-from-file (path w &aux e)
  (with-open-file (s path :direction :input)
    (do ((line (read-line s nil :eof)(read-line s nil :eof))) 
        ((eql line :eof))
      (setf e (concatenate 'string e line))))
  (butlast-elm e w))
 
(defun butlast-elm (e w &aux (a (car w)) (d (cdr w)))
  (when w (if (and (equalp a e) (not (member e d :test #'equalp))) d
              (cons a (butlast-elm e d)))))
 
> (butlast-elm "aa" '("aa" "bb" "aa" "bb"))
("aa" "bb" "bb")
> (butlast-elm-from-file "d:/test.txt" '("aa" "bb" "aa" "bb"))
("aa" "bb" "bb")
Добавлено через 2 минуты
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun butlast-elm-from-file (path w &aux e)
  (with-open-file (s path :direction :input)
    (do ((line (read-line s nil :eof)(read-line s nil :eof))) 
        ((eql line :eof))
      (setf e (concatenate 'string e line))))
  (butlast-elm (read-from-string e) w))
 
(defun butlast-elm (e w &aux (a (car w)) (d (cdr w)))
  (when w (if (and (equalp a e) (not (member e d :test #'equalp))) d
              (cons a (butlast-elm e d)))))
 
> (butlast-elm 'aa '(aa bb aa bb))
(AA BB BB)
> (butlast-elm-from-file "d:/test.txt" '(aa bb aa bb))
(AA BB BB)
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
35593 / 19491 / 4074
Регистрация: 12.02.2012
Сообщений: 32,531
Записей в блоге: 13
13.11.2016, 13:10 14
_Ivana, а, да... Ваша правда.

Добавлено через 23 часа 39 минут
За два полных прохода по списку:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun del-last (lst a)
  (labels ((last-pos (x y c p)
             (cond ((null x) p)
                   ((eq y (car x)) (last-pos (cdr x) y (+ c 1) c))
                   (t (last-pos (cdr x) y c p))))
           (del-by-pos (x y p)
             (cond ((and (= p 0)(eq (car x) y)) (cdr x))
                   ((eq (car x) y) (cons (car x) (del-by-pos (cdr x) y (- p 1))))
                   (t (cons (car x) (del-by-pos (cdr x) y p))))))
    (del-by-pos lst a (last-pos lst a 0 0))))          
             
==> DEL-LAST
 
(del-last '(1 2 3 4 1 2 3 1 2) 1)
 
==> (1 2 3 4 1 2 3 2)
 
(del-last '(1 2 3 4 1 2 3 1 1 1 2) 1)
 
==> (1 2 3 4 1 2 3 1 1 2)
2
4816 / 2276 / 287
Регистрация: 01.03.2013
Сообщений: 5,944
Записей в блоге: 27
14.11.2016, 01:11 15
Ну да, за первый проход узнаем индекс последнего иска а за второй удалим его по этому индексу.
1
0 / 0 / 0
Регистрация: 11.11.2016
Сообщений: 9
14.11.2016, 15:09  [ТС] 16
Lisp
1
2
3
4
5
(defun ud (l x)
   (cond ((null l) l)
        ((equal (car l) x)(cdr l))
        ((not (equal (car l) x) (cdr l)))
        (t (cons (ud (l)) (car (reverse l))))))
Скажите,что сделать,чтобы удалялось последнее вхождение,а не первое! Именно в моей функции
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
35593 / 19491 / 4074
Регистрация: 12.02.2012
Сообщений: 32,531
Записей в блоге: 13
14.11.2016, 17:47 17
Цитата Сообщение от Анастасия Сильч Посмотреть сообщение
Именно в моей функции
а она вообще неправильна. Некоторые ошибки я исправил, но не все. Код неверный.
0
0 / 0 / 0
Регистрация: 11.11.2016
Сообщений: 9
14.11.2016, 18:09  [ТС] 18
Скажите,а вы можете немного пояснить мне свою функцию! Я на начальном этапе обучения,и мы пока некоторыми понятиями не оперируем)прошу вас сделать комментарии.
Lisp
1
2
3
4
5
6
7
8
9
10
(defun del-last (lst a)
  (labels ((last-pos (x y c p) ;; ВОТ ЗДЕСЬ
             (cond ((null x) p)
                   ((eq y (car x)) (last-pos (cdr x) y (+ c 1) c)) ;; ВОТ ЗДЕСЬ
                   (t (last-pos (cdr x) y c p))))
           (del-by-pos (x y p) ;; И ЧТО ДЕЛАЕТ ВОТ ЭТА ФУНКЦИЯ
             (cond ((and (= p 0)(eq (car x) y)) (cdr x))
                   ((eq (car x) y) (cons (car x) (del-by-pos (cdr x) y (- p 1))))
                   (t (cons (car x) (del-by-pos (cdr x) y p))))))
    (del-by-pos lst a (last-pos lst a 0 0))))  ;;        И НА ЭТОМ ЭТАПЕ
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
35593 / 19491 / 4074
Регистрация: 12.02.2012
Сообщений: 32,531
Записей в блоге: 13
14.11.2016, 18:30 19
Проще не использовать локальные функции (labels), а сначала написать две вспомогательные функции:

1) Поиск позиции последнего вхождения атома в список:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(defun last-pos (lst x c p) 
  (cond ((null lst) p)
        ((eq (car lst) x) (last-pos (cdr lst) x (+ c 1) c))
        (t (last-pos (cdr lst) x (+ c 1) p))))
  
 
==> LAST-POS
 
(last-pos '(1 2 3 1 2 2 6) 2 0 0)
 
==> 5
 
(last-pos '(1 2 3 1 2 2 6) 1 0 0)
 
==> 3
 
(last-pos '(1 2 3 1 2 2 6) 6 0 0)
 
==> 6
Здесь c - накопительный параметр, содержащий номер очередного элемента списка (с нуля), p - накопительный параметр, содержащий позицию последнего вхождения x в lst.

2) Удалить из списка n-й по счету (с нуля) элемент. Это совсем просто:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(defun del-by-pos (lst n)
  (cond ((zerop n) (cdr lst))
        (t (cons (car lst) (del-by-pos (cdr lst) (- n 1))))))
 
==> DEL-BY-POS
 
(del-by-pos '(1 2 3 4) 3)
 
==> (1 2 3)
 
(del-by-pos '(1 2 3 4) 2)
 
==> (1 2 4)
А теперь удалить последнее вхождение заданного можно так:

Lisp
1
2
3
4
5
6
7
8
(defun del-last (lst x)
 (del-by-pos lst (last-pos lst x 0 0))) ;; ищем сначала позицию последнего вхождения, а потом удаляем...
 
==> DEL-LAST
 
(del-last '(1 2 3 1 1 7) 1)
 
==> (1 2 3 1 7)
0
0 / 0 / 0
Регистрация: 11.11.2016
Сообщений: 9
14.11.2016, 18:52  [ТС] 20
Спасибо! А теперь мне нужно их написать так,чтобы вся программа брала данные из файла)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.11.2016, 18:52
Помогаю со студенческими работами здесь

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

Написать функцию, удаляющую из списка каждый k-ый элемент
В общем есть задачка: Написать функцию, удаляющую из списка каждый k-ый элемент. Так вот,...

Clojure Написать функцию, удаляющую из исходного списка подсписки заданной глубины
Помогите сделать задание, нужно сделать через рекурсию, циклы нельзя использовать

Определите функцию, удаляющую каждое третье вхождение
И снова я. Благодарю за отклики и решения. Определите функцию, удаляющую каждое третье...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru