0 / 0 / 0
Регистрация: 08.10.2013
Сообщений: 5
1

Список входа -> выхода

08.10.2013, 23:25. Показов 1036. Ответов 4
Метки нет (Все метки)

Добрый вечер. Вот такая задачка: Словарь в задании - список пар значений с одинаковым типом (например пара слов, пара символов, или другие типы, которые можно сравнивать). Например, в словаре есть список [(„a”, „aa”), („bb”, „bbb”), („c”, „def”)]; этот словарь переводит „a” как „aa”, „bb” как „bbb” и „c” как „def”.

Задание A. Создать двух аргументную функцию pp, которая получив 2 разных словоря (список пар сзачений одного типа), А и В, выдаёт словарь С, который является композицией словорей А и В: в словаре С возможны только и только такие списки (x,z), для которых существует такой y, что (x,y) входит в словарь А и (y,z) входит в словарь В.

У каждого значения из входящего словоря, может быть несколько переводов. Известно, что одна и та-же пара во входящем словоре, не может быть дважды. программе нужно обеспечить, чтобы и при выходе не повторялись пары.

В рещении нелбзя использовать встроенную функцию nub.
Примеры:
Вход [(a, b)] un [(b,c), (b,d)] ответ [(a,c), (a,d)]
Вход [(a, b), (e, b)] un [(b,c), (b,d)] ответ [(a,c), (a,d), (e, c), (e,d)]
Вход [(a, b), (a, d), (a, e)] un [(b,c), (d,c)] ответ [(a,c)]

Задание В. Зоздать функцию qq с одним аргументом, которая получив словарь А, выдаёт его транзитивное замыкание. Если композицию словарей X и Y обозначаем как X o Y, тогда обычный результат является сочетанием A, A o A, A o (A o A), A o (A o (A o A)), ...

Формально обозначаем Ai как A1 =A и Ai+1 =A o Ai .
А транзитивное замыкание А* тогда является  { Ai | i N }.

Программе нужно обечпечить остановку и не допустить дубликаты.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.10.2013, 23:25
Ответы с готовыми решениями:

Сеанс входа/выхода
Добрый день, я совсем новичок и прошу помощи. Пишу обработку по анализированию времени нахождения...

Delphi настройка входа\выхода
Доброго времени суток. У меня такой вот вопрос: вроде бы давно работаю в Delphi, но до сих пор не...

Время входа/выхода в систему
Подскажите пожалуйста, где виндовс ХР сохраняет время последнего входа и выхода из системы (т.е. во...

Строки в файлах входа и выхода
Сразу извиняюсь, если такая тема уже есть. Вопрос такой: например есть файл INPUT.txt, в нем есть 3...

4
Модератор
Эксперт функциональных языков программированияЭксперт Python
29663 / 16213 / 3242
Регистрация: 12.02.2012
Сообщений: 26,860
Записей в блоге: 5
09.10.2013, 08:41 2
Первое задание (примитивное решение):

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fromJust :: Maybe a -> a
fromJust (Just a) = a
 
-- "Перевод" пары по словарю
 
transPair :: (String,String) -> [(String,String)] -> Maybe  (String,String)
transPair (x,y) [] = Nothing
transPair (x,y) ((dx,dy):ds) = if (y == dx) then Just (x,dy) else transPair (x,y) ds
 
-- "Перевод" словаря
 
transDict :: [(String,String)] -> [(String,String)] -> [(String,String)]
transDict [] _     = []
transDict (q:qs) d | (tqd) == Nothing = transDict qs d
                   | otherwise = (fromJust tqd) : transDict qs d 
                     where tqd=transPair q d                    
 
-- Проверка
 
Main> transDict [("a","aa"),("b","bb"),("c","cc")] [("aa","11"),("cc","77")]
[("a","11"),("c","77")]
1
Эксперт по математике/физике
4153 / 2056 / 423
Регистрация: 19.07.2009
Сообщений: 3,113
Записей в блоге: 24
09.10.2013, 10:36 3
По-другому, но тоже некрасиво
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type Dict a = [(a,a)]
 
pp :: Eq a => Dict a -> Dict a -> Dict a
pp d1 d2 = nub' $ do
    (x,y) <- d1
    (y',z) <- d2
    if y' == y then return (x,z) else []
 
nub' d = map (flip value d) (map fst d)
 
-- value k ~(e@(x,_):d) = if x==k then e else value k d
value k = foldr (\ ~e@(x,_) v -> if x==k then e else v) undefined
-- небезопасная реализация, что с принуждённым паттерном, что с конечным undefined
 
add d1 d2 = nub' (d1 ++ d2)
addAll :: Eq a => [Dict a] -> Dict a
addAll = foldl add []
 
qq :: Eq a => Dict a -> Dict a
qq d = nub' $ addAll $ take (length d) (iterate pp' d)
    where pp' d' = pp d' d
2
0 / 0 / 0
Регистрация: 08.10.2013
Сообщений: 5
09.10.2013, 14:02  [ТС] 4
Mysterious Light - просто в условиях было написано, что нельзя использовать функцию nub

Исправление:
Вместо:
Цитата Сообщение от fifa11 Посмотреть сообщение
Формально обозначаем Ai как A1 =A и Ai+1 =A o Ai .
А транзитивное замыкание А* тогда является  { Ai | i N }.
Надо:
Формально обозначаем Ai как A1 =A и Ai+1 =A o Ai .
А транзитивное замыкание А* тогда является U { Ai | i эN }.
0
Эксперт по математике/физике
4153 / 2056 / 423
Регистрация: 19.07.2009
Сообщений: 3,113
Записей в блоге: 24
09.10.2013, 17:57 5
Цитата Сообщение от fifa11 Посмотреть сообщение
Mysterious Light - просто в условиях было написано, что нельзя использовать функцию nub
А я и не использовал
Обратите внимание, что nub' в моём коде действует не так, как nub в общем случае; даже типы различаются. Тем не менее, можно nub' заменить на nub и программа останется работоспособной, только, может быть, чуть более медленной, потому что (повторю ещё раз) nub' учитывает, что перед нами словарь, т.е. элемент списка — пара и ключ этой пары уникален, а nub работает без этих предположений.
Цитата Сообщение от fifa11 Посмотреть сообщение
Формально обозначаем Ai как A1 =A и Ai+1 =A o Ai .
А транзитивное замыкание А* тогда является U { Ai | i эN }.
Используйте LaTeX. Вы имели в виду так?
https://www.cyberforum.ru/cgi-bin/latex.cgi?A^* = \bigcup \{ A_i | i\in\mathbb{N}\} = \bigcup_{i=1}^\infty A_i, \;\;\; A_1 = A, \; A_{k+1} = A\circ A_k
Кстати,
https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{k+1} = A\circ A_k = A_k\circ A
в силу ассоциативности (https://www.cyberforum.ru/cgi-bin/latex.cgi?\circ).
У меня, например, использовался второй вариант, но можно поменять местами:
Haskell
1
2
3
4
pp' d' = pp d' d
-- здесь pp — это композиция, pp' переводит A_k в A_{k+1}, d=A, d'=Ak
(iterate pp' d) -- это описанное множество { Ai | iєN }, бесконечное,
-- но начиная с (length d) оно заведомо стационарное
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.10.2013, 17:57

Мониторинг входа/выхода пользователей
Нужно написать скрипт,который записывал бы время,дату и имя компьютера в txt файл,сразу же после...

Реализация входа выхода пользователя
Уважаемые веб дела мастера, помагите пажалуста. Начнем с самого начала. Я пишу сайт тело и...

Звуки входа и выхода в win 8
Как настроить звуковые сопровождения? в частности звук приветствия?

Замена надписей на экранах входа и выхода
Здравствуйте все! Есть у меня такая ситуация: Установлена скачанная с интернета &quot;Windows 7 SP1...

Нет звука входа и выхода в Windows 8
изначально после установки отсутствовал звук приветствия и завершения работы системы... во вкладке...

Не проигрываются звуки входа, выхода, блокировки
Здравствуйте! Уже несколько дней мучаюсь с такой проблемой: не проигрываются звуки входа, выхода,...


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

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

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