Форум программистов, компьютерный форум, киберфорум
Наши страницы
Haskell
Войти
Регистрация
Восстановить пароль
 
no swear
183 / 157 / 82
Регистрация: 01.07.2016
Сообщений: 881
Завершенные тесты: 1
1

Поиск и вывод периода в списке

27.01.2019, 21:01. Просмотров 366. Ответов 10
Метки нет (Все метки)

Дан список (конечный или бесконечный), содержащий периодически повторяющуюся последовательность элементов. Получить его период, т.е. конечный список, содержащий начало исходного списка до первого повторения первого элемента (не включая повтор первого элемента). Сигнатура функции:
Haskell
1
    beginning :: Eq a => [a]->[a]
Пример ее применения:
Haskell
1
2
3
    
Prelude> beginning [1,3,5,4,1,3,5,4,1,3,5,4]
[1,3,5,4]
Я написал решение но насколько оно удовлетворяет функциональному стилю программирования?
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
beginning :: Eq a => [a] -> [a]
beginning (x:xs) = beginning' (x:[]) xs
 
beginning' :: Eq a => [a] -> [a] -> [a]
beginning' prd [] = prd
beginning' prd (x:xs)
    | find == True = prd
    | find == False = beginning' (prd ++ x:[]) xs
    where
        find = check prd (x:xs)
 
check :: Eq a => [a] -> [a] -> Bool
check prd xs = check' prd xs []
 
check' :: Eq a => [a] -> [a] -> [a] -> Bool
check' [] [] _ = True
check' prd xs zs
    | length prd == 0 = check' zs xs []
check' _ [] _ = False
check' (y:prd) (x:xs) zs
    | y == x = check' prd xs (zs ++ y:[])
    | y /= x = False
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.01.2019, 21:01
Ответы с готовыми решениями:

Поиск положительных элементов во вложенном списке и вывод их в отдельный список
polozh(,,). polozh(,N,L):-H>0,append(N,H,L),polozh(T,L,L). pol(S,Z):-polozh(S,,Z). Что не так,...

Период из запроса разбить на начало периода и конец периода
есть запрос "выбрать оборотыпродажи. период как период из продажиобороты " на выходе имеем...

Вывод сумм в отчете ДДС не по неделям, а по дням периода
Здравствуйте! Помогите, пожалуйста, видоизменить отчет. Собственно об отчете: 1. Имеется отчет,...

1 С Управление Автотранспортом. Вывод на печать периода в заголовке в виде слова
Добрый день! Есть отчет. В заголовке к нему выводится период в виде: "за 01.11.2016 -...

Подбор с периода, согласно результатам формулы, и вывод результата в форму и добавка в таблицу Access (функция if)
Всем привет! Я новичек в Access и тем более в языках программирования. Но, я учусь... Нужна ваша...

10
Catstail
Модератор
24605 / 12513 / 2284
Регистрация: 12.02.2012
Сообщений: 20,332
28.01.2019, 09:14 2
Цитата Сообщение от no swear Посмотреть сообщение
насколько оно удовлетворяет функциональному стилю программирования?
- если бы не удовлетворяло, то и не работало бы . Другой вопрос: можно ли лаконичнее решить эту задачу? Вот мой вариант (он использует стандартную функцию isPrefixOf из Data.List, но ее нетрудно реализовать и самому):

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import Data.List
 
isPeriod :: (Eq a) => [a] -> Int -> [a] -> Bool
isPeriod _ _ [] = True
isPeriod p n s  | isPrefixOf p s = isPeriod p n $ drop n s
                | otherwise = False
                
getPrefixes :: (Eq a) => [a] -> [[a]]
getPrefixes x = map (\ a -> take a x) [1..(length x) `div` 2]               
 
getPeriod :: (Eq a) => [a] -> [a]
getPeriod x | null r = []
            | otherwise = head r
              where r=filter (\p -> isPeriod p (length p) x) (getPrefixes x)
 
*Main Data.List> getPeriod "abababab"
"ab"
*Main Data.List> getPeriod [1,3,5,4,1,3,5,4,1,3,5,4]
[1,3,5,4]
2
no swear
183 / 157 / 82
Регистрация: 01.07.2016
Сообщений: 881
Завершенные тесты: 1
28.01.2019, 10:15  [ТС] 3
Catstail, Спасибо за код. Будет с чем сравнивать мой быдлокод
0
Catstail
Модератор
24605 / 12513 / 2284
Регистрация: 12.02.2012
Сообщений: 20,332
28.01.2019, 10:27 4
no swear, зачем же так самоуничижаться! Нулевое требование к коду - код должен работать правильно! Все остальное вторично. Ваш код работает, я проверял.
У меня получилось чуть короче за счет двух моментов: 1) использование библ. функции 2) использование map и filter. Зачастую рекурсию имеет смысл "заменять" отображениями и фильтрами.
1
28.01.2019, 10:27
no swear
183 / 157 / 82
Регистрация: 01.07.2016
Сообщений: 881
Завершенные тесты: 1
28.01.2019, 10:48  [ТС] 5
Цитата Сообщение от Catstail Посмотреть сообщение
Зачастую рекурсию имеет смысл "заменять" отображениями и фильтрами.
Приму к сведению, но я буду стараться решать более лаконично примеры и задачи
0
Somebody
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
28.01.2019, 19:22 6
Что-то как-то всё сложно, или это я не так понял. До повторения первого элемента - это
Haskell
1
2
getPeriod [] = []
getPeriod (x : xs) = x : takeWhile (/= x) xs
(а реальный поиск цикла всё равно на бесконечных списках не получится).
2
no swear
183 / 157 / 82
Регистрация: 01.07.2016
Сообщений: 881
Завершенные тесты: 1
28.01.2019, 22:30  [ТС] 7
Somebody, Такой тест не проходит
Haskell
1
2
*Main> getPeriod [1,2,3,1,2,3,4]
[1,2,3]
А должен быть весь список
Haskell
1
[1,2,3,1,2,3,4]
0
Somebody
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
28.01.2019, 23:24 8
Цитата Сообщение от no swear Посмотреть сообщение
Получить ... конечный список, содержащий начало исходного списка до первого повторения первого элемента
По этому определению getPeriod [1,2,3,1,2,3,4] == [1,2,3] - что не так?
Классическое же определение периода несовместимо с
Цитата Сообщение от no swear Посмотреть сообщение
Дан список (конечный или бесконечный)
, так как нельзя найти период бесконечного списка за конечное время и конечность списка определить тоже нельзя.
1
no swear
183 / 157 / 82
Регистрация: 01.07.2016
Сообщений: 881
Завершенные тесты: 1
28.01.2019, 23:36  [ТС] 9
Цитата Сообщение от Somebody Посмотреть сообщение
Дан список (конечный или бесконечный)
По поводу условия мне самому непонятно как выглядит решения для бесконечного списка поэтому работал с конечным списком. Но подозреваю что ваше решение подходит под оба определения конечного и бесконечного списка

Цитата Сообщение от Somebody Посмотреть сообщение
По этому определению getPeriod [1,2,3,1,2,3,4] == [1,2,3] - что не так?
Моя программа ищет период во всём списке, то есть участок где блоки повторяются целиком а здесь из за 4 в конце нет полного повторения. Если бы было [1,2,3,1,2,3] то ответ [1,2,3]. Но опять повторюсь что по моему в условии это и имелось ввиду потому как ваша программа работает строго по условию задачи. Работает строго до повторения первого элемента

Добавлено через 6 минут
Можно считать что я специально усложнил себе задачу
0
Mysterious Light
Эксперт по математике/физике
4095 / 2004 / 410
Регистрация: 19.07.2009
Сообщений: 3,024
Записей в блоге: 22
29.01.2019, 09:30 10
Решение Поиск и вывод периода в списке не работает даже для "101210121012".

Catstail, предлагаю заменить у Вас
Haskell
1
isPeriod p _ s = s `isPrefixOf` cycle p
Правда, в этом случае возможны будут префиксы некратной длины, т.е. не укладывающиеся целое число раз в строку. Например, "123" в "1231231231". Если мы запрещаем этот вариант, то есть предложение в getPrefixes идти по делителям (length x).
3
Curry
2952 / 2021 / 252
Регистрация: 01.06.2013
Сообщений: 4,415
Записей в блоге: 8
29.01.2019, 19:02 11
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
beginning :: Eq a => [a]->[a]
beginning s | maxp > 1 = go (tail s) 2 
            | otherwise = [] -- слишком короткая последовательность
    where maxp = length s `div` 2 
          go ~(_:ss) i | i<=maxp = if isPeriod ss then take i s
                                   else go ss $ i+1
                       | otherwise = [] -- периодичность не найдена
            where isPeriod [] = True
                  isPeriod t = go' s i t
                    where go' _ 0 s' = isPeriod s'
                          go' _ _ [] = True -- если допустим последний неполный период. Иначе False
                          go' ~(x:xs) j (y:ys) = (x==y) && go' xs (j-1) ys
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Решение Поиск и вывод периода в списке не работает даже для "101210121012".
Вообще то это был намёк что задание плохо составлено:
Цитата Сообщение от no swear Посмотреть сообщение
Получить его период, т.е. конечный список, содержащий начало исходного списка до первого повторения первого элемента (не включая повтор первого элемента).
Т.е. формально то решение подходит.
И, да, бесконечный список невозможно проверить на периодичность.
3
29.01.2019, 19:02
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2019, 19:02

Как сделать автоматический вывод периода в Word, который автоматически подставляет нужные даты при открытии
Здравствуйте! Есть выпуск новостей в Word 2010, где в колонтитулах написан период, который каждый...

Поиск в списке
Найти в списке все фамилии, начинающиеся со слога «Ма».

Поиск в списке
Нужно из текстового файла вида: lr001 Шевченко lr003 Горький lr002 Лермонтов ... lr00n Захаров...


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

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

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