Обсуждение:Семинар ДООМ. Решение комбинаторных задач с помощью графов

Версия 09:08, 15 ноября 2007

Здравствуйте, Ирина Владимировна!

Мне очень понравилось, что занятие Вашего кружка посвящено решению конкретного класса задач на применение графов, что задачи разбиты на блоки и внутри каждого блока приводится несколько вариантов заданий. Очень четко просматривается логика в изложении материала, его структура. Мне кажется, что именно такой подход формирует устойчивые навыки в решении задач, способствует полному усвоению знаний.

Не знаю, будет ли это уместным, но мне хочется предложить Вам еще один вид задач, которые, как мне кажется, созвучны теме Вашего занятия, может быть Вам это пригодиться. Это задачи, которые предлагались учащимся на централизованном тестировании по информатике. К сожалению, авторы тестов и после тестирования не публикуют оптимальных способов решения задач, информатики нашей школы при подготовке к ЦТ предлагают решать задачи такого типа с помощью графов.

Итак, задачи:

Задача1.

Алфавит племени Пиджен состоит из 4-ёх букв. Аборигены закодировали слово СDAB с использованием следующей таблицы:

и передали его не сделав промежутков, отделяющих одну букву от другой. Количество способов прочтения переданного сообщения равно?

Задача2.

Алфавит племени Пиджен состоит из 4-ёх букв. Аборигены закодировали слово DСAD с использованием следующей таблицы:

и передали его не сделав промежутков, отделяющих одну букву от другой. Количество способов прочтения переданного сообщения равно?

Задача3.

Алфавит племени Пиджен состоит из 4-ёх букв. Аборигены закодировали слово ВААС с использованием следующей таблицы:

и передали его не сделав промежутков, отделяющих одну букву от другой. Количество способов прочтения переданного сообщения равно?

Задача4.

Алфавит племени Пиджен состоит из 4-ёх букв. Аборигены закодировали слово DBAD с использованием следующей таблицы:

и передали его не сделав промежутков, отделяющих одну букву от другой. Количество способов прочтения переданного сообщения равно?

РЕШЕНИЕ ЗАДАЧИ №1

Алгоритм:

1. С помощью таблицы кодируем сообщение СDAB, получаем код 100101

2. Записываем код в вершину будущего графа

3. Анализируем: какая буква может стоять на первом месте? Есть два варианта. В или С. Значит, из нашей вершины будет выходить два ребра, в вершины, которыми они заканчиваются, пишем еще не расшифрованный код(т.е В кодируется 1, значит код 100101 мы трактуем как В00101, пишем 00101, С кодируется как 10, получаем С0101, пишем 0101)

4. Повторяем п.3 для всех вершин, пока не останется одна буква.

5. Количество листьев графа определяет количество вариантов декодирования (в нашем случае 10). Варианты декодирования также просматриваются.

Дальнейших Вам успехов, Ирина Владимировна!

--Иванова Елена 10:08, 15 ноября 2007 (UZT)