@AlexB_49
Студент

Как проверить есть ли заданное соответствие между элементами двух множеств правильно заданным отображением?

Написать программу, которая в качестве входных данных получает два конечные множества и соответствие между элементами этих множеств и определяет, есть ли заданное соотвествие правильно заданным отображением.
Отображение с множества Х в множество У - каждому элементу с множества Х ставит в соответствие некоторый элемент с множества У.
По сути надо проверить нету ли какого-то элемента с первого множества Х для которого нету пары с множества У. Если есть, то соответствие не является отображением. Если нету, то это правильно заданное отображение.
Подскажите как это можно сделать? Надо использовать массивы или что-то другое? Какой алгоритм проверки?
Буду искренне благодарен!
  • Вопрос задан
  • 220 просмотров
Пригласить эксперта
Ответы на вопрос 1
@AVKor
Вот код на Ruby:
#!/usr/bin/env ruby
# frozen_string_literal: true

require 'set'

def relation_is_func?(xset, yset, rset)
  x_is_correct = (rset.map(&:keys).flatten - xset.to_a).empty?
  y_is_correct = (rset.map(&:values).flatten - yset.to_a).empty?
  r_is_correct = rset.map(&:keys).flatten.sort == xset.to_a.sort
  x_is_correct && y_is_correct && r_is_correct ? 'Function.' : 'Not function.'
end

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 2 => 'b' }, { 1 => 'b' }, { 3 => 'b' }, { 4 => 'a' }]
relation_is_func?(x, y, r) #=> "Function."

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 1 => 'b' }, { 2 => 'b' }, { 3 => 'b' }, { 4 => 'b' }, { 2 => 'c' }]
relation_is_func?(x, y, r) #=> "Not function."

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 1 => 'c' }, { 2 => 'a' }, { 4 => 'b' }]
relation_is_func?(x, y, r) #=> "Not function."

Примечания:
  1. Заморачиваться с вводом данных я не стал, просто захардкодил три примера.
  2. Реализовать упорядоченные пары можно разными способами, я использовал хэши. Можно было реализовать и по-другому (Struct, например).
  3. Для множеств я использовал Set.
  4. Проверка корректности входных данных реализована частично. Можете подумать, что стоит добавить.
  5. В примерах: x - множество X; y - множество Y; r - отношение между X и Y (для которого надо выполнить проверку того, что это функция).
  6. Запустить на выполнение можно так: сохранить в файл, допустим, test.rb и в терминале выполнить команду: irb test.rb

На C++ реализуйте сами.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы