Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Lisp
Перезагрузить страницу Найти длину самой длинной входящей в него последовательности
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
Unhappy Найти длину самой длинной входящей в него последовательности - 17.05.2009, 17:40

Буду очень признательна если поможете с этим заданием! Очень нужно!

Задан список чисел. Найти длину самой длинной входящей в него последовательности. А - возрастающая, В - убывающая, V - пилообразная (пилообразная например 5 6 4 8 7 1 и т.д.) Найти длину и номер первого элемента.

Как я поняла надо найти самую длинную последовательность из А,В,V, выдать: ее; ее длину; номер элемента, с которого она начинается.
Ответить с цитированием
  (#2 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
По умолчанию 20.05.2009, 11:44

Неужели никто не может помочь?
Ответить с цитированием
  (#3 (permalink)) Старый
VH VH вне форума
Member
 
Сообщений: 781
Сказал(а) спасибо: 0
Поблагодарили 11 раз(а) в 10 сообщениях
Регистрация: 29.06.2006
По умолчанию 20.05.2009, 17:30

Нахождение длины и начального номера максимальной возрастающей последовательности:
Код:
(defun F (L &optional (acc (if L (cons (cons 1 0) nil))))
  (cond
   ((null L) (if acc (assoc (apply 'max (mapcar 'car acc)) acc)))
   ((null (cdr L)) (F nil acc))
   (T
    (F
     (cdr L)
     (if (< (car L) (cadr L))
      (cons (cons (1+ (caar acc)) (cdar acc)) (cdr acc))
      (cons (cons 1 (+ (cdar acc) (caar acc))) acc))))))
Формат возвращаемого значения: (длина . номер). Номера элементов списка начинаются с 0(нуля)!
Ответить с цитированием
  (#4 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
По умолчанию 20.05.2009, 22:46

Спасибо огромное за код! Вы меня 2 раз спасли))

Подскажите, для убывающей и пилообразной алгоритм выглядит похоже? Можно ли их объединить в 1 программу?
Ответить с цитированием
  (#5 (permalink)) Старый
VH VH вне форума
Member
 
Сообщений: 781
Сказал(а) спасибо: 0
Поблагодарили 11 раз(а) в 10 сообщениях
Регистрация: 29.06.2006
По умолчанию 20.05.2009, 23:15

Для убывающей последовательности достаточно заменить вызов функции (<) на вызов функции (>).
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
По умолчанию 21.05.2009, 01:49

Спасибо большое, буду разбираться с прогой))
Ответить с цитированием
  (#7 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
По умолчанию 23.05.2009, 18:41

Пробовала в Мулиспе пустить - ругается на строчку (cons (cons (1+ (caar acc))
Ответить с цитированием
  (#8 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
По умолчанию 24.05.2009, 23:03

Все работает отлично в Корман Лисп! Пыталась написать пилообразную получилось это:
Код:
(defun F (L &optional (acc (if L (cons (cons 1 0) nil))))
  (cond
   ((null L) (if acc (assoc (apply 'max (mapcar 'car acc)) acc)))
   ((null (cdr L)) (F nil acc))
   (T
    (F
     (cdr L)
    (if 
         (cond
             ((< (car L) (cadr L))
             (> (cadr L) (caddr L)))
             (T nil))
             
                    
         (cons (cons  (1+ (caar acc)) (cdar acc)) (cdr acc))
         (cons (cons 1 (+ (cdar acc) (caar acc))) acc))
     
                ))))
Работает неправильно:
(F'(3 7 2)) ->(2 . 0)
(F'(4 6 5 6 2)) -> (2 . 2)

А в обратную сторону, т.е. если задавать первый элемент больше второго и т.д. не работает, т.к. не смогла совместить в одной проге чтоб и туда и туда((((

Подскажите где исправить, пожалуйста! Весь вечер проковырялась!
Ответить с цитированием
  (#9 (permalink)) Старый
VH VH вне форума
Member
 
Сообщений: 781
Сказал(а) спасибо: 0
Поблагодарили 11 раз(а) в 10 сообщениях
Регистрация: 29.06.2006
По умолчанию 01.06.2009, 14:02

Пилообразная последовательность (если текущий элемент больше предыдущего, то следующий меньше текущего - и наоборот) <на мой взгляд, несколько коряво>:
Код:
(defun F (L &optional (acc (if L (cons (cons 1 0) nil))) (sign (if L (if (cdr L) (- (cadr L) (car L))))))
  (cond
   ((null L) (if acc (assoc (apply 'max (mapcar 'car acc)) acc)))
   ((null (cdr L)) (F nil (reverse acc) sign))
   ((zerop sign) (F (cdr L) (cons (cons 1 (+ (cdar acc) (caar acc))) acc)))
   (T
    ((lambda (result)
      (F
       (cdr L)
       (if result
        (cons (cons (1+ (caar acc)) (cdar acc)) (cdr acc))
        (cons (cons 2 (+ (1- (cdar acc)) (caar acc))) acc))
       (* (if result -1 +1) sign)))
     (plusp (* sign (- (cadr L) (car L))))))))
Следующий вариант:
Код:
(defun F (L &optional (acc (if L (cons (cons 1 0) nil))) (sign (if L (if (cdr L) (- (cadr L) (car L))))))
  (cond
   ((null L)
    (if acc (assoc (apply 'max (mapcar 'car acc)) acc)))
   ((null (cdr L))
    (F nil (reverse acc) sign))
   ((zerop sign)
    (F (cdr L) (cons (cons 1 (+ (cdar acc) (caar acc))) acc)))
   ((plusp (* sign (- (cadr L) (car L))))
    (F (cdr L) (cons (cons (1+ (caar acc)) (cdar acc)) (cdr acc)) (- sign)))
   (T
    (F L (cons (cons 1 (+ (caar acc) (1- (cdar acc)))) acc)))))
Ответить с цитированием
  (#10 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
По умолчанию 01.06.2009, 20:36

Спасиб большое=) Надеюсь все таки сдам зачет. Преклоняюсь перед мастером))) Как отблагодарить?
Ответить с цитированием
  (#11 (permalink)) Старый
VH VH вне форума
Member
 
Сообщений: 781
Сказал(а) спасибо: 0
Поблагодарили 11 раз(а) в 10 сообщениях
Регистрация: 29.06.2006
По умолчанию 02.06.2009, 01:10

Идея достаточно проста: найти длины всех последовательностей в списке, а затем вернуть сведения про последовательность максимальной длины.
Сведения о последовательностях накапливаются в списке-аккумуляторе acc. Если список изначально не пустой, то в аккумулятор помещается точечная пара (длина . начальный номер) в виде (1 . 0). По мере продвижения по списку либо (при выполнении условия продолжения последовательности) изменяется первый элемент аккумулятора (длина увеличивается на единицу), либо (при обнаружении «дефекта» в последовательности) в аккумулятор спереди добавляется еще одна точечная пара для подсчета длины новой последовательности. Так как сведения о последовательностях списка располагаются в аккумуляторе "в обратном порядке", желательно перед поиском максимальной длины «перевернуть» аккумулятор - это удобно сделать, когда в списке остался один элемент. Наконец, когда список полностью просмотрен, можно выбрать посредством функции (car) длины последовательностей, найти посредством функции (max) максимальную длину и извлечь посредством функции (assoc) из аккумулятора сведения про эту последовательность.
Так что предпочтительным для случая возрастающей(убывающей) последовательности будет вариант c «обращением» аккумулятора:
Код:
(defun F (L &optional (acc (if L (cons (cons 1 0) nil))))
  (cond
   ((null L) (if acc (assoc (apply 'max (mapcar 'car acc)) acc)))
   ((null (cdr L)) (F nil (reverse acc)))
   (T
    (F
     (cdr L)
     (if (< (car L) (cadr L))
      (cons (cons (1+ (caar acc)) (cdar acc)) (cdr acc))
      (cons (cons 1 (+ (cdar acc) (caar acc))) acc))))))
Для случая пилообразной последовательности добавляется маятник sign, который на каждом шаге меняет знак. Изначально этот маятник получает значение приращения (разницы между следующим и текущим элементом). Если очередное приращение равно нулю, то в акумулятор добавляется точечная пара про последовательность из одного элемента. На каждом шаге вычисляется произведение текущего маятника и текущего приращения. Это число положительно, если знаки маятника и приращения совпадают - в этом случае пилообразная последовательность продолжается и изменяется первый элемент аккумулятора. Если у маятника и приращения разные знаки, то выполняется добавление в аккумулятор точечной пары про новую последовательность с «текущего места» в списке. По завершении просмотра списка определяется последовательность максимальной длины.
Ответить с цитированием
  (#12 (permalink)) Старый
Paprika Paprika вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2009
По умолчанию 02.06.2009, 02:37

Спасиб за разъяснения=))) Их очень не хватало))
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
По данной хорде A найти длину дуги, если она соответствует центральному углу в C град Demon21 Haskell 0 16.05.2011 11:33
Найти НОК последовательности чисел hazardhz Haskell 4 08.04.2011 10:40
Найти порядковый номер ого из элементов последовательности... razor052 Pascal 1 27.10.2010 10:43
Найти максимальную длину строки Цвяточек Алгоритмы 1 06.10.2010 03:53
Лексемы как найти длину Sergio_ml Perl 0 28.06.2010 09:42
Как найти символ в строке и после него вставить контрольную сумму babkin C++ Builder 7 11.02.2009 15:00
Найти длину списка Rizaya Prolog 2 11.01.2006 19:01
Shenduler где найти код для него ORION Delphi 1 30.12.2005 14:16
EhLib где найти для него информацию konstantinus Delphi 1 19.12.2005 14:38
Как можно найти адрес последовательности байтов в памяти Fess exe Visual C++ 9 17.10.2004 19:55
Smtp Server Hunter где найти ссылку на него Anonymous DHTML, JavaScript, VBScript 2 25.05.2004 22:36
В Exele необходимо найти адрес самой нижней ячейки Kain Visual Basic 1 28.11.2002 14:25



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов