Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Порядок выполнения задания

  • 1.6.1. Изучить формулы расчета расстояний Хемминга, правила образования битовых шкал для основных теоретико-множественных операций и отношений. Реализовать их в виде программных процедур. Каждую из них оформить так, чтобы, с одной стороны, ее можно было автономно тестировать, а с другой - использовать при разработке программ решения задач. Оценить вычислительную сложность процедур по времени и используемой памяти в зависимости от п - длины битовых шкал (см. рекомендации в прил. 1).
  • 1.6.2. Разработать и отладить программу решения задач, связанных с почтовым индексом.

Варианты

О почтовом индексе. Для написания цифр почтового индекса принято использовать множество X из 9 элементов, которые обозначены буквами на рис. 1.1, а сами цифры изображены на рис. 1.2. Здесь множество X играет роль универсального множества. Будем считать, что его элементы перечисляются в алфавитном порядке:

Следует для каждой из десяти цифр записать множество Ак (к = 0, ..., 9), элементы которого образуют запись этой цифры, и найти соответствующую битовую шкалу. Так, цифре 0 отвечает множество А0 - {а, Ь, d,f h, i} и битовая шкала (1, 1,0, 1, 0, 1,0, 1, 1). Требуется разработать программу, которая позволяла бы по X и битовым шкалам множеств Ак (к = 0,..., 9) решить задачи, указанные в табл. 1.5.

Рис. 1.1

Рис. 1.2

Таблица 1.5

Номер

варианта

Задача

1

Найти среди Ак(к- 0,9) пары непересекающихся множеств.

Для заданной цифры найти все цифры, которые отстоят от нее не более чем на 1/3 (в смысле относительного расстояния Хемминга)

2

Найти среди Ак (к - 0,..., 9) пары равномощных множеств.

Для заданной цифры найти наиболее близкую ей цифру (в смысле расстояния Хемминга)

3

Найти среди Ак (к - 0,..., 9) пары множеств, для которых справедливо отношение включения.

Для заданного почтового индекса найти пару наименее близких цифр (в смысле расстояния Хемминга)

4

Найти среди Ак(к- 0,..., 9) множества, содержащие заданный элемент х g X.

Найти среди Ак (к - 0,..., 9) пару наиболее близких множеств (в смысле расстояния Хемминга)

5

Для каждого элемента х g X найти число множеств Ак, в которые он входит.

Найти среди Ак (к - 0,..., 9) пару наименее близких множеств (в смысле расстояния Хемминга)

6

Найти элемент х g X, который наиболее редко используется в Ак (к = 0,..., 9).

Для заданной цифры найти наименее близкую цифру (в смысле расстояния Хемминга)

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>