Clojure Найти наибольшую последовательность чисел в списке

@Vaderkos · Регистрация: 31.03.2015

Студворк — интернет-сервис помощи студентам

Нужно найти в списке самую длинную убывающую или растущую последовательность чисел
Например
Вводим список
8 4 2 3 2

Получаем две последовательности 8 4 2 и 3 2, нам нужен 8 4 2 так как он длиннее.

@Vaderkos · 27.10.2015, 00:30 **[ТС]**

Хммм, вместе проверять надо, надо из убывающих и возрастающих найти самую длинную

@helter · 27.10.2015, 00:31

Откуда у вас внутренние циклы берутся, я понять не могу.

Если вы за один проход хотите считать и такие, и сякие, как вы хотите обойтись одной переменной temp? Может же получиться, что вы сначала складываете туда возрастающую подпоследовательность, а потом — туда же — убывающую. А потом снова возрастающую. А потом...

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

@Vaderkos · 27.10.2015, 00:37 **[ТС]**

helter, А как насчет сделать отдельно найти самую длинную убывающую а потом самую длинную возрастающую и сравнить в конце?

Добавлено через 3 минуты
helter, Как то так я полагаю?

Lisp
1
2
3
4
5
6
7
(let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el (rest all))
        (if (<= el (first temp)) 
            (push el temp)
            (when (or(> el (first temp) (not (first temp))))
                (setf longest temp)
                (setf longest-len temp-len)))))

@helter · 27.10.2015, 00:42

Сообщение от Vaderkos

helter, А как насчет сделать отдельно найти самую длинную убывающую а потом самую длинную возрастающую и сравнить в конце?

Да, я так и предлагаю. Это будут ровно две функции. Давайте сначала с возрастанием допишем.

Добавлено через 4 минуты

Сообщение от Vaderkos

helter, Как то так я полагаю?

Строчка 5: вы всё время заменяете longest на temp, даже если temp был короче. А заменять надо только если temp-len > longest-len. Вам знаком принцип поиска наибольшего элемента в массиве? Это он, родимый. Как в сказке про солдата, который сначала находил медные монеты, потом серебряные, потом золотые и брал то, что более ценно.

Кроме того, при нарушении монотонности надо и temp менять. Ведь temp — это текущая монотонная последовательность. Если монотонность нарушается, temp присваивается список, состоящий из нарушевшего монотонность элемента, а temp-len выставляется 1.

В частности, список temp никогда не будет пустым. Условие (not (first temp)) не нужно.

@Vaderkos · 27.10.2015, 00:44 **[ТС]**

helter,

Lisp
1
2
3
4
5
(let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el (rest all))
        (if (<= el (first temp)) 
            ((push el temp)   (incf temp-len))
            ((setf longest temp)   (setf longest-len temp-len)))))

@_Ivana · 27.10.2015, 00:45

Я тут не мешаю процессу, для сравнения только выложу свой вариант

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defn task (l)
    (defn sub-pred (pred)
        (defn go (l a r)
            (def h (car l) t (cdr l))
            (cond (null? l) (cons (reverse r) nil)
                  (or (null? a) (pred a h)) (go t h (cons h r))
                  (cons (reverse r) (go t h (cons h nil))) ))
        (go l nil nil))
    (cadr (foldr (lambda (x a) (def l (length x)) (cond (> l (car a)) (cons l x nil) a))
        '(0 nil) (append (sub-pred <) (sub-pred >)))))
 
(printLn (task '(8 4 2 3 2)))
 
........
 
(8 4 2)

@Vaderkos · 27.10.2015, 00:47 **[ТС]**

_Ivana, Что это за лисп?

@helter · 27.10.2015, 00:49

Вы в REPL-е-то тестируйте, тестируйте.

Сразу бы увидели, что на строки 4 и 5 ругается. А так — я буду ругаться. При обычном вычислении списка на первом месте должно стоять имя функции или лямбда-выражение. А у вас — (push el temp). Это же не имя функции и не лямбда-выражение.

Вы хотите в одно выражение засунуть два. Операторные скобки, так сказать. (Вы си или паскаль знаете?) Операторные скобки — это progn. Поэтому ветка «да» будет

Lisp
1
2
3
(progn
  (push el temp)
  (incf temp-len))

А насчёт ветки «нет» — обратите ещё раз внимание:

Сообщение от helter

вы всё время заменяете longest на temp, даже если temp был короче. А заменять надо только если temp-len > longest-len. Вам знаком принцип поиска наибольшего элемента в массиве? Это он, родимый. Как в сказке про солдата, который сначала находил медные монеты, потом серебряные, потом золотые и брал то, что более ценно.

@_Ivana · 27.10.2015, 00:49

Vaderkos, вы лучше в алгоритмах разбирайтесь, как вам уже выше советовали, а не диалекты лиспа сравнивайте. Поймете или придумаете алгоритм - реализуете везде.

@helter · 27.10.2015, 00:52

Сообщение от _Ivana

Я тут не мешаю процессу, для сравнения только выложу свой вариант

Я ничего не понял. А к какому списку применяется foldr?

@_Ivana · 27.10.2015, 00:55

foldr применяется к списку, образованному конкатенацией двух списков, каждый из которых получен разбиением исходного списка на подсписки, удовлетворяющие бинарному предикату - в данном случае < и >. И ищет элемент максимальной длины.

Lisp
1
(append (sub-pred <) (sub-pred >)) == ((8) (4) (2 3) (2) (8 4 2) (3 2))

@Vaderkos · 27.10.2015, 01:02 **[ТС]**

helter,

Вот так вроде бы работает

Lisp
1
2
3
4
5
6
(let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el (rest all))
        (if (>= el (first temp)) 
            (progn (push el temp)   (incf temp-len))
            (if (> temp-len long-len)
                (progn(setf longest temp)  (setf long-len temp-len)))))(reverse longest))

@helter · 27.10.2015, 01:06

Ну вот, по-моему, неплохо.

Теперь в конец приделать такую же проверку, и почти готово.

Есть такая хитрость. Если при выполнении условия вы хотите сделать одно ли несколько действий, а при невыполнении — ничего, лучше использовать when вместо if. Во-первых, люди сразу поймут, что вы хотите. Во-вторых, внутри when не надо писать progn. Поэтому в ответ «как делать тест», я где-то выше написал вам с when.

@Vaderkos · 27.10.2015, 01:31 **[ТС]**

helter,

Lisp
1
2
3
4
5
6
7
(let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el (rest all))
        (if (>= el (first temp)) 
            (progn (push el temp)   (incf temp-len))
            (when (> temp-len long-len)
                (setf longest temp)
                (setf long-len temp-len))))(reverse longest))

Добавлено через 5 минут
Вы это имели ввиду?

Добавлено через 6 минут
helter, Вот только почему обычная смена знака не подходит для убывающих??

Lisp
1
2
3
4
5
6
7
(let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el (rest all))
        (if (<= el (last temp)) 
            (progn (push el temp)   (incf temp-len))
            (when (> temp-len long-len)
                (setf longest temp)
                (setf long-len temp-len))))(reverse longest))

Добавлено через 5 минут
а что если просто развернуть all и еще раз пройтись той же функцией?

Добавлено через 2 минуты
Единственная проблема, что в all чисел может быть от 0 до 10в7

@helter · 27.10.2015, 01:36

Сообщение от Vaderkos

Вы это имели ввиду?

Нет.

У вас REPL под рукой. Ладно, я сделаю за вас:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
;;; это у вас в файле
(defun foo (all)
  (let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el (rest all))
      (if (>= el (first temp)) 
          (progn (push el temp)   (incf temp-len))
          (when (> temp-len long-len)
            (setf longest temp)
            (setf long-len temp-len))))
    (reverse longest)))
 
;;; Это у вас в REPLе
> (foo '(1 2 3 4))
NIL
> (foo '(1 2 1 2 3 4))
(1 2)

И вы начинаете думать: что не так?

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

Добавлено через 1 минуту

Сообщение от Vaderkos

helter, Вот только почему обычная смена знака не подходит для убывающих??

Не торопитесь, доделайте одно сначала.

@_Ivana · 27.10.2015, 01:40

Сообщение от Vaderkos

Единственная проблема, что в all чисел может быть от 0 до 10в7

Ну с этого и надо было начинать

Тогда отставить мой алгоритм, надо написать нормальный

@Vaderkos · 27.10.2015, 01:43 **[ТС]**

Сообщение от helter

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

Немного не понял, в смысле оно возвращает первую найденную послдовательность?

Добавлено через 56 секунд
Ага, и если последовательность была одна то возвращает пустой список

@helter · 27.10.2015, 01:47

Вот ещё для размышления

Lisp
1
2
> (foo '(1 2 1 2 3 4 1 2 1 2 3 4 5))
(1 2 2 3 4)

Перечитайте ещё несколько раз моё предыдущее сообщение. А также вот это:

Сообщение от helter

Кроме того, при нарушении монотонности надо и temp менять. Ведь temp — это текущая монотонная последовательность. Если монотонность нарушается, temp присваивается список, состоящий из нарушевшего монотонность элемента, а temp-len выставляется 1.

@Vaderkos · 27.10.2015, 01:58 **[ТС]**

У меня компилится, без ошибок, но если дам много чисел то умирает
helter,

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun find-longest (arr) 
    (let ((longest '()) (long-len 0) (temp (list (first arr))) (temp-len 1))
        (dolist (el (rest arr))
            (if (>= el (first temp)) 
                (progn (push el temp)   (incf temp-len))
                (when (> temp-len long-len)
                    (setf longest temp)
                    (setf long-len temp-len)
                    (setf temp-len 1)
                    (setf temp el))))
        (when (> temp-len long-len)
        (setf longest temp)
        (setf long-len temp-len))
        (reverse longest)))

FIND-LONGEST
* (find-longest '(1 2 1 2 3 4 1 2 1 2 3 4 5))

debugger invoked on a TYPE-ERROR in thread
#<THREAD "main thread" RUNNING {1002C6BC53}>:
The value 1 is not of type LIST.

Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.
0

(FIND-LONGEST (1 2 1 2 3 4 1 2 1 2 3 4 ...))
0] 0

*

@_Ivana · 27.10.2015, 01:59

Навскидку, с одним реверсом в конце. Хотя и его по-хорошему надо исключить.

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defn task (l)
    (defn sub-pred (pred)
        (defn go (l x acc acc-size res res-size)
            (def h (car l) t (cdr l))
            (cond (null? l) (cons res res-size)
                  (or (null? x) (pred x h)) (go t h (cons h acc) (+ 1 acc-size) res res-size)
                  (cond (> acc-size res-size) (go t h (cons h nil) 1 acc acc-size)
                        (go t h (cons h nil) 1 res res-size)) ))
        (go l nil nil 0 nil 0))
    (def a (sub-pred <) d (sub-pred >))
    (reverse (cond (> (cadr a) (cadr d)) (car a) (car d))))

Новые блоги и статьи Все статьи Все блоги /
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@Vaderkos 84 / 83 / 8 Регистрация: 31.03.2015 Сообщений: 447

	Clojure Найти наибольшую последовательность чисел в списке 26.10.2015, 20:31. Показов 6195. Ответов 84 Метки нет (Все метки) Нужно найти в списке самую длинную убывающую или растущую последовательность чисел Например Вводим список 8 4 2 3 2 Получаем две последовательности 8 4 2 и 3 2, нам нужен 8 4 2 так как он длиннее. 0

@Vaderkos 84 / 83 / 8 Регистрация: 31.03.2015 Сообщений: 447
	27.10.2015, 00:30 [ТС]
	Хммм, вместе проверять надо, надо из убывающих и возрастающих найти самую длинную 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	27.10.2015, 00:31
	Откуда у вас внутренние циклы берутся, я понять не могу. Если вы за один проход хотите считать и такие, и сякие, как вы хотите обойтись одной переменной temp? Может же получиться, что вы сначала складываете туда возрастающую подпоследовательность, а потом — туда же — убывающую. А потом снова возрастающую. А потом... Вообще, самый простой вариант — не париться с двумя сравнениями сразу, а написать функцию, которая ищет самую длинную возрастающую подпоследовательность или самую длинную убывающую. Найти обе и вернуть ту, которая длиннее. Получается в два прохода, но имеет ли смысл городить огород? 0

@Vaderkos 84 / 83 / 8 Регистрация: 31.03.2015 Сообщений: 447
	27.10.2015, 00:47 [ТС]
	_Ivana, Что это за лисп? 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	27.10.2015, 00:49
	Vaderkos, вы лучше в алгоритмах разбирайтесь, как вам уже выше советовали, а не диалекты лиспа сравнивайте. Поймете или придумаете алгоритм - реализуете везде. 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	27.10.2015, 01:06
	Ну вот, по-моему, неплохо. Теперь в конец приделать такую же проверку, и почти готово. Есть такая хитрость. Если при выполнении условия вы хотите сделать одно ли несколько действий, а при невыполнении — ничего, лучше использовать when вместо if. Во-первых, люди сразу поймут, что вы хотите. Во-вторых, внутри when не надо писать progn. Поэтому в ответ «как делать тест», я где-то выше написал вам с when. 0