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

@fifa11 · Регистрация: 08.10.2013

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

Добрый вечер. Вот такая задачка: Словарь в задании - список пар значений с одинаковым типом (например пара слов, пара символов, или другие типы, которые можно сравнивать). Например, в словаре есть список [(„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 }.

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

@Catstail · 09.10.2013, 08:41

Первое задание (примитивное решение):

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")]

@Mysterious Light · 09.10.2013, 10:36

По-другому, но тоже некрасиво

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

@fifa11 · 09.10.2013, 14:02 **[ТС]**

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 }.

@Mysterious Light · 09.10.2013, 17:57

Сообщение от 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) оно заведомо стационарное

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

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

	Список входа -> выхода 08.10.2013, 23:25. Показов 1544. Ответов 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