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

Вставка элемента в список (без рекурсии)

16.10.2014, 14:40. Просмотров 921. Ответов 12
Метки нет (Все метки)

Здравствуйте!!! У меня есть такая задача: дан список, число и произвольное s-выражение. Поставить s-выражение в список перед элементом, номер которого равен числу, например (A B C D), T, 3 —> (A B T C D)
В общем, рекурсивный вариант программы я написал:
Lisp
1
2
3
4
(DEFUN INS (LST K N)
(IF(= N 1)
(CONS K LST)
(CONS (CAR LST) (INS (CDR LST) K (- N 1)))))
А вот как решить эту же задачу, не используя рекурсию, а используя циклы и простейшие команды типа LIST, APPEND, CONS и т.д.?
Заранее спасибо!!!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.10.2014, 14:40
Ответы с готовыми решениями:

программа которая берет список и создает список другой из этого же списка + тот же список без последнего элемента
надо написать программу которая берет список и создает список другой из этого же списка + тот же...

Добавление нового элемента в бинарное дерево поиска с вспомогательной функцией(без рекурсии)
с реализацией этой функции с рекурсией проблем нету.но без нее уже по-сложнее(.есть функция иbool...

Вставка элемента в Список
import java.util.ArrayList; import java.util.Random; import java.util.Scanner; public class T1 {...

Вставка элемента в список
Здравствуйте.Пишу код #include <stdlib.h> #include <stdio.h> #include <string.h> #include...

__________________
12
Модератор
Эксперт Python
28529 / 15399 / 3043
Регистрация: 12.02.2012
Сообщений: 25,230
Записей в блоге: 4
16.10.2014, 17:07 2
В Лиспе есть функция subseq, которая выделяет подсписок. С ее помощью все становится очень простым:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(defun task (lst n s)
 (cond  ((zerop n) (cons s lst))
        ((>= n (length lst)) (raiseerror "Индекс за пределами списка!"))
        (t (append (subseq lst 0 n) (list s) (subseq lst n)))))
 
==> task
 
(task '(1 2 3 4) 0 '(a b c))
 
==> ((a b c) 1 2 3 4)
 
(task '(1 2 3 4) 12 '(a b c))
 
Индекс за пределами списка!
==> ERRSTATE
 
(task '(1 2 3 4) 2 '(a b c))
 
==> (1 2 (a b c) 3 4)
2
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,354
16.10.2014, 20:23 3
Цитата Сообщение от Boogerman Посмотреть сообщение
А вот как решить эту же задачу, не используя рекурсию, а используя циклы
Это не идеоматично и в лиспе будет выглядеть очень некрасиво и с костылями. По крайней мере мне так представляется.
Lisp
1
2
3
4
5
;;; racket-lang.org
(define (foo lst a pos)
  (unless (or (< pos 0) (> pos (length lst)))
    (let-values (((h t) (values (take lst (sub1 pos)) (drop lst (sub1 pos)))))
      (append h (list a) t))))
Добавлено через 6 минут
Хвостовая рекурсия это и есть цикл. Напишите функцию, накапливающую результат в аргументе.
0
Модератор
Эксперт Python
28529 / 15399 / 3043
Регистрация: 12.02.2012
Сообщений: 25,230
Записей в блоге: 4
16.10.2014, 21:27 4
Коротко, но неэффективно:

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defun task (lst n s)
  (let ((r nil))
    (dolist (i lst (reverse r))
      (when (= (length r) n) (push s r)) 
      (push i r))))
 
==> task
 
(task '(1 2 3 4 5 6) 3 '(a b c d))
 
==> (1 2 3 (a b c d) 4 5 6)
2
4343 / 3350 / 342
Регистрация: 12.03.2013
Сообщений: 5,838
16.10.2014, 21:38 5
Цитата Сообщение от Catstail Посмотреть сообщение
(reverse r)

Если заменить на nreverse, становится эффективно. Boogerman, push/nreverse - стандартная идиома построения списка с нуля.

Добавлено через 36 секунд
Цитата Сообщение от Catstail Посмотреть сообщение
(= (length r) n)
А, не, насчёт эффективности я пошутил.
3
4493 / 4203 / 354
Регистрация: 12.05.2012
Сообщений: 2,959
16.10.2014, 23:06 6
как вариант:
Lisp
1
2
3
4
5
6
7
8
(defun insert (w n v)
  (loop for a in w
        for i upfrom 1
        when (= i n) collect v
        collect a))
 
> (insert '(1 2 3 4 5) 4 '(a b))
(1 2 3 (A B) 4 5)
3
korvin_
16.10.2014, 23:54
  #7

Не по теме:

Цитата Сообщение от castorsky Посмотреть сообщение
Это не идеоматично и в лиспе будет выглядеть очень некрасиво и с костылями. По крайней мере мне так представляется.
В CL циклы более "идеоматичны", чем рекурсия, что бы это ни значило.

0
Заблокирован
17.10.2014, 02:24 8
Lisp
1
2
3
4
(defun insert (a n lst)
  (append (reverse (nthcdr (- (length lst) n 1) (reverse lst)))
      (list a (nth n lst))
      (nthcdr n lst)))
2
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
17.10.2014, 06:49  [ТС] 9
Спасибо всем большое!!!
0
defun
603 / 617 / 44
Регистрация: 30.04.2011
Сообщений: 702
17.10.2014, 07:25 10
Цитата Сообщение от helter Посмотреть сообщение
А, не, насчёт эффективности я пошутил.
ну и что же с ней не так?)

Кликните здесь для просмотра всего текста
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
INSOMNIA> (defparameter
              lst
            (make-list 1000000))
LST
INSOMNIA> (length lst)
1000000
INSOMNIA> (time (repeat 1000000 (length lst)))
Evaluation took:
  0.008 seconds of real time
  0.009000 seconds of total run time (0.009000 user, 0.000000 system)
  112.50% CPU
  20,729,186 processor cycles
  0 bytes consed
  
1000000
INSOMNIA>
2
4343 / 3350 / 342
Регистрация: 12.03.2013
Сообщений: 5,838
17.10.2014, 16:16 11
Цитата Сообщение от transformator.t Посмотреть сообщение
ну и что же с ней не так?)
Там в цикле (без необходимости) вычисляется (length r), так что получается O(n2) вместо O(n).
0
defun
603 / 617 / 44
Регистрация: 30.04.2011
Сообщений: 702
17.10.2014, 16:50 12
helter, для теоретика это важно,... наверное..
0
Модератор
Эксперт Python
28529 / 15399 / 3043
Регистрация: 12.02.2012
Сообщений: 25,230
Записей в блоге: 4
17.10.2014, 17:47 13
Цитата Сообщение от helter Посмотреть сообщение
Там в цикле (без необходимости) вычисляется (length r)
- это я и имел в виду, когда писал "коротко, но не эффективно". Так чуть эффективнее:

Lisp
1
2
3
4
5
6
(defun task (lst n s)
  (let ((r nil) (с 0))
    (dolist (i lst (reverse r))
      (when (= с n) (push s r)) 
      (push i r)
      (setq c (+ c 1))))
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.10.2014, 17:47

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

Вставка элемента в список
Составьте программу , которая вставляет в непустой список L , элементы которого упорядочены по не...

Связный список и вставка элемента
Мне надо написать прогу, которая создает связный список (линейный), вставляет в любом месте...

Вставка элемента в однонаправленный список
помогите написать функцию добавления в конец списка нового элемента требования: ф-ция типа void ,...

Вставка элемента в список на все X позиции
Имеется программа вставки элемента в список ins(1,EL,,). ins(N,EL,,):- N1=N-1, ins(N1,EL,T,T1)....


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

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

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