Добавить число в упорядоченный в порядке возрастания список

barret · Регистрация: 07.04.2007

Всем здрасти.
Помогите с программой, а то что-т никак не врублюсь:

Добавить число в упорядоченный в порядке возрастания список без нарушения порядка.
Например: >(функция 7 ‘(1 3 5 8 11)) результат: (1 3 5 7 8 11). Никак не дойдет какая функция ето делает ((

Желательно задачу решить двумя способами: рекурсивно и с помощью организации циклов.

_sg · 07.04.2007, 23:53

Код:

(defun plunge-in (n w)
  (when w ((lambda (a d)
             (if (atom d)
                 (list a n)
                 (if (<= n a)
                     (cons n w)
                     (cons a (plunge-in n d)))))
           (car w) (cdr w))))

(plunge-in 7 '(1 3 5 8 11))
(1 3 5 7 8 11)

Код:

(defun squeeze-in (n w)
  (let ((e))
    (loop for i from 0 below (length w) do
          ((lambda (u)
             (when  (and  (<= n u) (or (= i 0) (> n (nth (1- i) w))))
               (push n e))
             (push u e)
             (when (and (> n u) (= (length w) (1+ i)))
               (push n e)))
           (nth i w)))
    (nreverse e)))

(squeeze-in 7 '(1 3 5 8 11))
(1 3 5 7 8 11)

Alexey Dejneka · 08.04.2007, 08:12

SQUEEZE работает квадратичное время.

Код:

(defun plug-in (x list)
  (loop for (y . rest) on list
        when (< x y)
          nconc (list* x y rest) into head
          and return head
        collect y into head
        finally (return (nconc head (list x)))))

В каком диалекте есть WHEN и нет LET?

_sg · 08.04.2007, 10:23

Цитата:

SQUEEZE работает квадратичное время.

Код:

(defun plug-in (x list)
  (loop for (y . rest) on list
        when (< x y)
          nconc (list* x y rest) into head
          and return head
        collect y into head
        finally (return (nconc head (list x)))))

Спасибо.

Цитата:

В каком диалекте есть WHEN и нет LET?

?

Код:

(defun cram-in (n w)
  (sort (cons n w) #'<))

Alexey Dejneka · 08.04.2007, 11:35

Вряд ли SORT будет учитывать, что список уже отсортирован.

Код:

(defun cram-in (n w)
  (merge 'list (list n) w #'<))

_sg, интересно, почему Вы пишете LAMBDA вместо LET? VH, видимо, хочет использовать минимум средств, а Вы?

_sg · 08.04.2007, 15:57

Цитата:

Вряд ли SORT будет учитывать, что список уже отсортирован.

Код:

(defun cram-in (n w)
  (merge 'list (list n) w #'<))

Спасибо.

Возможно, что lambda разгружает верхнюю часть кода и не нарушает функционального стиля,
хотя согласен с Вами, что let* и let имеют свои преимущества (в том числе - слитность) и чаще
применяются.

_sg · 09.04.2007, 11:15

Код:

(defun plunge-in (n w)
  (when w (let ((a (car w)) (d (cdr w)))
            (if (atom d)
                (list a n)
                (if (<= n a)
                    (cons n w)
                    (cons a (plunge-in n d)))))))

Код:

(defun plunge-in (n w)
  (when w ((lambda (a d)
             (if (atom d)
                 (list a n)
                 (if (<= n a)
                     (cons n w)
                     (cons a (plunge-in n d)))))
           (car w) (cdr w))))

barret · 12.04.2007, 13:30

Всем большое спасибо! Разобрался )

_sg · 15.04.2007, 00:39

)

Код:

(defun plunge-in (n w)
  (when w (let ((a (car w)) (d (cdr w)))
            (cond ((atom d) (list a n))
                  ((> n a) (cons a (plunge-in n d)))
                  ((cons n w))))))

Код:

(defun plunge-in (n w)
  (when w ((lambda (a d)
             (cond ((atom d) (list a n))
                   ((> n a) (cons a (plunge-in n d)))
                   ((cons n w))))
           (car w) (cdr w))))

barret · 26.04.2007, 09:43

А как бы ету программу сделать чистой рекурсией, тоесть без "let", "list"?

_sg · 26.04.2007, 12:54

Код:

(defun set-in (n w)
  (cond ((null w) (cons n nil))
        ((> n (car w)) (cons (car w) (set-in n (cdr w))))
        ((cons n w))))

(set-in 7 '(1 3 5 8 11))
(1 3 5 7 8 11)

barret · 03.05.2007, 20:17

Возможно ли ету программу разработать в итерационном варианте ? Тоесть что бы в функции использовались лишь приметивы car, cdr и cons, а все остальные должны должны быть определыны через эти приметивы.

Alexey Dejneka · 03.05.2007, 20:55

Итерация - это концевая рекурсия? Тогда можно. Но, чтобы Вам не было совсем скучно, я не стал описывать, как выразить > и COND через примитивы CONS, CAR и CDR - надеюсь, с этим проблем не возникнет.

Код:

(defun my-revappend (list tail)
  "Returns (APPEND (REVERSE LIST) TAIL)."
  (cond (list
         (my-revappend (cdr list) (cons (car list) tail)))
        (t
         tail)))

(defun plug-in (x list &optional (head-reversed nil))
  (cond ((cond (list (> x (car list))))
         (plug-in x (cdr list) (cons (car list) head-reversed)))
        (t
         (revappend head-reversed (cons x list)))))

barret · 03.05.2007, 22:54

2 Alexey Dejneka
А можно чуть по подробней, у меня впринципи и вызвало затруднее, то как выразить cond через приметивы. В принципи так то понятно, но вот что то не получается.
Заранее спасибо.

Опции темы
Версия для печати Отправить по электронной почте
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Записать каждое предложение текста в порядке возрастания	berserker	Lisp	9	28.12.2011 20:59
Преобразовать дерево в простой список, где вершины записываются в обратном порядке	Lilj	Prolog	0	19.05.2011 12:03
Вывод слова в порядке возрастания длины в С++	Dariya	Вопросы начинающих программистов	3	30.11.2010 18:43
Дана матрица 4*4, нужно выстроить элементы в ней в порядке возрастания	Wispa)	Lisp	2	05.05.2010 13:56
Получить список всех делителей на указанное число.Prolog	armoko	Prolog	3	13.04.2010 08:23
Вычислить полное число подсписков, входящих в данный список	Sergio_ml	Lisp	3	26.01.2010 00:00
Определить число вхождений элемента X в список L	AntonioG1988	Lisp	13	21.12.2009 16:25
Вставить новый элемент в упорядоченный список	-Scratch-	Prolog	6	04.04.2009 13:43
Как добавить элемент в список?	Ant_vkl	Prolog	0	21.05.2008 23:20
Распределить карты по масти в порядке возрастания	yura_korepin	Lisp	3	09.12.2007 19:42
Нужно определить функцию сортирующую данный список в любом порядке	Дрон	Lisp	1	02.06.2007 18:33
Как добавить в таблицу достаточное число строк	Ajaks	Visual C++	3	03.11.2006 14:06

Alexey Dejneka Member Сообщений: 451 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 23.11.2004	08.04.2007, 08:12 SQUEEZE работает квадратичное время. Код: (defun plug-in (x list) (loop for (y . rest) on list when (< x y) nconc (list* x y rest) into head and return head collect y into head finally (return (nconc head (list x))))) В каком диалекте есть WHEN и нет LET?

Alexey Dejneka Member Сообщений: 451 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 23.11.2004	08.04.2007, 11:35 Вряд ли SORT будет учитывать, что список уже отсортирован. Код: (defun cram-in (n w) (merge 'list (list n) w #'<)) _sg, интересно, почему Вы пишете LAMBDA вместо LET? VH, видимо, хочет использовать минимум средств, а Вы?

barret Новичок Сообщений: 7 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 07.04.2007	12.04.2007, 13:30 Всем большое спасибо! Разобрался )

barret Новичок Сообщений: 7 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 07.04.2007	26.04.2007, 09:43 А как бы ету программу сделать чистой рекурсией, тоесть без "let", "list"?

_sg Member Сообщений: 522 Сказал(а) спасибо: 5 Поблагодарили 42 раз(а) в 38 сообщениях Регистрация: 23.01.2007	26.04.2007, 12:54 Код: (defun set-in (n w) (cond ((null w) (cons n nil)) ((> n (car w)) (cons (car w) (set-in n (cdr w)))) ((cons n w)))) (set-in 7 '(1 3 5 8 11)) (1 3 5 7 8 11)

barret Новичок Сообщений: 7 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 07.04.2007	03.05.2007, 20:17 Возможно ли ету программу разработать в итерационном варианте ? Тоесть что бы в функции использовались лишь приметивы car, cdr и cons, а все остальные должны должны быть определыны через эти приметивы.

barret Новичок Сообщений: 7 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 07.04.2007	03.05.2007, 22:54 2 Alexey Dejneka А можно чуть по подробней, у меня впринципи и вызвало затруднее, то как выразить cond через приметивы. В принципи так то понятно, но вот что то не получается. Заранее спасибо.

Ads