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

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

26.10.2015, 20:31. Показов 4732. Ответов 84
Метки нет (Все метки)

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

Получаем две последовательности 8 4 2 и 3 2, нам нужен 8 4 2 так как он длиннее.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.10.2015, 20:31
Ответы с готовыми решениями:

В одномерном массиве найти наибольшую последовательность из отрицательных чисел и вывести ее
Дошел до того что нахожу количество отрицательных чисел в наибольшей последовательности, но как...

В одномерном масстве найти наибольшую последовательность из отрицаельных чисел и перенести ее в конец массива
Я нашла наибольшую последовательность из отрицательных чисел, а перенести в конец массива не...

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

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

84
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
26.10.2015, 20:59 2
Нужны переменные: собираемая последовательность, длина собранной последовательности, наибольшая последовательность, длина наибольшей последовательности. Изначально обе последовательности состоят из первого элемента, длины равны 1. Проходим по остальным членам последовательности. Если очередной член не портит монотонность, добавить его к собираемой последовательности, увеличить её длину на 1. Если портит — сравнить длину собранной последовательности с длиной наибольшей; если длина больше — присвоить максимальной последовательности собранную, максимальной длины — длину собранной. В конце — тоже проверить.

Вы действительно не могли додуматься до этого алгоритма?
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
26.10.2015, 21:01  [ТС] 3
Та я вот придумал алгоритм и сижу пишу, но вот решил на всякий случай написать сюда и увидеть идеи)
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
26.10.2015, 21:05 4
При чём лисп? Есть специальный раздел: https://www.cyberforum.ru/algorithms/
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
26.10.2015, 22:23  [ТС] 5
helter, Я вот только не понимаю как правильно сделать проверку, немного написал но вот дальше никак не пойму
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun Long-ciag (k)
(let ((pos 0) (x nil) (longest nil) longest-length (temp nil) temp-length num)
  (loop
    (multiple-value-setq (num pos) (parse-integer k :start pos :junk-allowed t))
    (when (not num) (return longest))
    (if (eq x nil) (push num temp) (push num longest) (setf x t))
    (setf temp-length (length temp))
    (cond 
        ((< num (cdr temp)) 
            (loop
                (multiple-value-setq (num pos) (parse-integer k :start pos :junk-allowed t))
                ()))
        ((> num (cdr temp)) 
            ())
    ))))
 
    
    
    
(Long-ciag (read-line))
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
26.10.2015, 23:10 6
Ого!

Ну, во-первых, список — это список, а не строка. Почему long-ciag принимает строку, а не список?

Во-вторых, if явно неправильный, потому что аргумента у него может быть максимум 2 (then-ветвь и else-ветвь).

Поясните, какой вы алгоритм реализуете, и как. x — это что?

length — это O(n), поэтому если в цикле вызываете length, можете получить O(n^2). Лучше просто увеличивать на 1 значения соответствующих переменных.

Давайте вы уберёте строки и parse-integer-ы, попробуете написать второй вариант, и будем обсуждать построчечно.

Проверку, кстати, делать так:
Lisp
1
2
3
(when (> temp-len longest-len)
  (setf longest temp)
  (setf longest-len temp-len))
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
26.10.2015, 23:18  [ТС] 7
helter,
Я имею ввиду я не знаю как сделать если допустим числа идут по убыванию а потом бах и число которое больше, что в этот момент делать, проверку а затем ?
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
26.10.2015, 23:29 8
В этот момент — сначала проверку и апдейт максимальных значений, потом temp присвоить список из этого нового числа, temp-length присвоить 1.
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
26.10.2015, 23:46  [ТС] 9
helter,
Вот так лучше?
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defun  readIntList (k)
    (let ((pos 0) num var) 
        (loop 
            (multiple-value-setq (num pos) (parse-integer k :start pos :junk-allowed t))
            (when (not num)(return))
            (push num var))(reverse var)))
 
 
 
(let ((all (readintlist (read-line))) (longest nil) (lon-len 0) (temp nil) (temp-len 0)) 
    (loop
        
        
        
        
        ))
Только вот с чего теперь начать?
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
26.10.2015, 23:50 10
Дались вам строки.

Вы мой алгоритм хотите кодить или другой?
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
26.10.2015, 23:51  [ТС] 11
helter, Ваш, но я не знаю с чего начать и как лучше сделать цыкл((
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
26.10.2015, 23:54 12
Цитата Сообщение от helter Посмотреть сообщение
Изначально обе последовательности состоят из первого элемента, длины равны 1.
Где вот это?
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
26.10.2015, 23:55  [ТС] 13
helter,
Lisp
1
2
3
4
5
6
7
8
9
10
(let ((all (readintlist (read-line))) (longest nil) (long-len 0) (temp nil) (temp-len 0))
    (push (car all) temp)
    (push (car all) longest)
    (incf long-len)
    (incf temp-len)
    (loop for el in all 
        do 
        
                
        ))
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
27.10.2015, 00:03 14
Цитата Сообщение от Vaderkos Посмотреть сообщение
как лучше сделать цыкл
dolist

Добавлено через 7 минут
Я ещё раз ненавязчиво предложу: давайте уберём строки. Задача про последовательности чисел. Массивы литер сюда никаким боком.

Цитата Сообщение от Vaderkos Посмотреть сообщение
(let ((all (readintlist (read-line))) (longest nil) (long-len 0) (temp nil) (temp-len 0)) (push (car all) temp) (push (car all) longest) (incf long-len) (incf temp-len)
LET используется одновременно и для создания переменных, и для инициализации. Почему сразу не инициализировать правильно?
Lisp
1
2
3
4
5
(let ((longest '())
      (long-len 0)
      (temp (list (first all)))
      (temp-len 1))
  ...)
Пришла мысль, что в качестве самого длинного списка можно взять пустой, а длину его ― 0. Непонятно, какой смысл был делать его из одного элемента. А temp нет смысла брать пустым, потому что для проверки монотонности вы будете сравнивать элемент с его головой. То есть надо, чтобы голова была.
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
27.10.2015, 00:03  [ТС] 15
helter,
Lisp
1
2
3
4
5
6
7
8
9
(let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el all)
        (if (<= el (car temp)) 
            (push el temp) 
            (when (> temp-len longest-len)
                (setf longest temp)
                (setf longest-len temp-len))
                )       
        ))
Согласен так лучше
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
27.10.2015, 00:10 16
Ну вот, почти хорошо. Только на самой первой итерации вы сравниваете голову списка all с самой собой, занесённой в temp. А потом второй раз заносите её в temp. Я же пишу:
Цитата Сообщение от helter Посмотреть сообщение
Проходим по остальным членам последовательности.
Цитата Сообщение от helter Посмотреть сообщение
остальным
Теперь, когда вы заканчиваете цикл, у вас будет temp, который не сравнивался с longest. Придётся сравнить отдельно.

Добавлено через 2 минуты
«Остальная часть» в лиспе будет rest, «первый элемент» — first. Когда работаете со списками, имеет смысл употреблять эти слова вместо car и cdr. car и cdr — более низкий уровень, уровень конс-ячеек, из которых можно делать разные структуры данных. Списки — только одна из таких структур. При работе со списками лучше использовать термины, относящиеся именно к спискам.
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
27.10.2015, 00:17  [ТС] 17
helter, а как через dolist пойти по следующим елементам?

Добавлено через 11 секунд
Увидел

Добавлено через 3 минуты
helter, Не догоняю, как лисп понимает что мы уже использовали first и дает нам rest
Lisp
1
2
(if (<= el (first (rest all))) 
            (push el temp)
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
27.10.2015, 00:18 18
Никак не понимает. Просто пишем пишем (dolist (el (rest all))...)
0
84 / 83 / 8
Регистрация: 31.03.2015
Сообщений: 447
27.10.2015, 00:27  [ТС] 19
И проблема в том, что последовательности могут быть как возрастающими так и убывающими, как это сделать?

Добавлено через 50 секунд
helter, Аааа, то есть rest отдает все елементы кроме первого?

Добавлено через 7 минут
helter,
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(let ((longest '()) (long-len 0) (temp (list (first all))) (temp-len 1))
    (dolist (el (rest all))
        (cond 
            ( (<= el (first temp)) 
                (loop 
                    (push el temp)
                    (when (> el (first temp))
                        (setf longest temp)
                        (setf longest-len temp-len)
                        return)))
                        
            ( (>= el (first temp)) 
                (loop 
                    (push el temp)
                    (when (< el (first temp))
                        (setf longest temp)
                        (setf longest-len temp-len)
                        return)))
        )))
0
4527 / 3521 / 358
Регистрация: 12.03.2013
Сообщений: 6,038
27.10.2015, 00:27 20
Цитата Сообщение от Vaderkos Посмотреть сообщение
helter, Аааа, то есть rest отдает все елементы кроме первого?
Ну да. По сути это тот же cdr, только человеческим словом.

Цитата Сообщение от Vaderkos Посмотреть сообщение
И проблема в том, что последовательности могут быть как возрастающими так и убывающими, как это сделать?
Надо одновременно проверять или отдельно? Я думал, что отдельно, потому что в примере
Цитата Сообщение от Vaderkos Посмотреть сообщение
Вводим список
8 4 2 3 2
Получаем две последовательности 8 4 2 и 3 2, нам нужен 8 4 2 так как он длиннее.
есть и возрастающая последовательность 2 3, которую вы не перечислили. Если отдельно, мы добавим потом тестирующую функцию. Если вместе — придётся усложнять алгоритм.
0
27.10.2015, 00:27
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.10.2015, 00:27
Помогаю со студенческими работами здесь

В списке чисел найти самую длинную последовательность
Помогите, пожалуйста, решить задачу. Очень нужно. В списке чисел, которые записаны в файл (имеют...

Найти наибольшую неубывающую последовательность
1Дана последовательность чисел a1, a2, …, an. Найти в ней наибольшую неубывающую...

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

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


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

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

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