Задача - Помощь студентам

sniper1794 · 05.04.2013, 19:22

Помогите решить задачу пожалуйста

Задача 1. Вводится последовательность, состоящая из N пар символов (ai,bi). Каждая пара определяет порядок предшествования символов, например, пара (b,с) означает, что символ "b" предшествует символу "с". Из порядка (b,с) и (с,a) следует порядок (b,a). Необходимо определить, является ли введенная последовательность:
а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку (A1,A2,...,As) в порядке предшествования;
б) противоречивой, т.е. для некоторых символов x,y можно получить одновременно порядок как (x,y) так и (y,x);

Abstraction · 05.04.2013, 19:44

Речь идёт о направленном графе, вершины которого - символы. б) тогда - вопрос о наличии циклов в таком графе; а) не вполне понятен (скажем, полна ли последовательность (1,2), (1,3)?) - это либо вопрос связности графа, либо существования эйлерова пути в нём. Для всего перечисленного (равно как и представления направленного графа в виде программных структур) уже разработаны алгоритмы, поищите.

05.04.2013, 19:22	#1
sniper1794 Новичок Джуниор Регистрация: 05.04.2013 Сообщений: 1	Задача Помогите решить задачу пожалуйста Задача 1. Вводится последовательность, состоящая из N пар символов (ai,bi). Каждая пара определяет порядок предшествования символов, например, пара (b,с) означает, что символ "b" предшествует символу "с". Из порядка (b,с) и (с,a) следует порядок (b,a). Необходимо определить, является ли введенная последовательность: а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку (A1,A2,...,As) в порядке предшествования; б) противоречивой, т.е. для некоторых символов x,y можно получить одновременно порядок как (x,y) так и (y,x);

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
задача на зачёт. проблема Задача на нобелевскую премию!	Sabotage5	Паскаль, Turbo Pascal, PascalABC.NET	2	18.03.2013 15:18
Задача по подсчёту статистики использования букв. Другая задача - по длинной арифметике Pascal ABC	kimberly	Паскаль, Turbo Pascal, PascalABC.NET	3	24.12.2012 17:03
задача на структуру(struct)/задача на работу с файлом	SevenArth	Помощь студентам	0	26.04.2012 19:06
Задача на оптимальный расчет маршрута (задача в презентации) в табличном процессоре Excel	Toofed	Помощь студентам	0	30.11.2011 01:12
Задача минимизации дисбаланса на линии сборки (задача минимакса)	LenZab	Microsoft Office Excel	13	13.03.2011 22:51

05.04.2013, 19:44	#2
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	Речь идёт о направленном графе, вершины которого - символы. б) тогда - вопрос о наличии циклов в таком графе; а) не вполне понятен (скажем, полна ли последовательность (1,2), (1,3)?) - это либо вопрос связности графа, либо существования эйлерова пути в нём. Для всего перечисленного (равно как и представления направленного графа в виде программных структур) уже разработаны алгоритмы, поищите.