Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
lfin
2 / 2 / 0
Регистрация: 11.10.2009
Сообщений: 31
#1

Задача Парсона - C++

11.10.2009, 18:50. Просмотров 508. Ответов 6
Метки нет (Все метки)

Доброго времени суток. Прошу пожалуйста написать программу на С++.

Задача Парсона (1982 РЖМат 11В682) Пусть G - конечный неориентированный связный граф. Предположим, что он представляет собой систему тоннелей, в которых может прятаться беглец. Группа из S полицейских, двигаясь по туннелям,
стремится схватить этого беглеца, который может двигаться с любой скоростью, стремясь избежать поимки. Требуется определить минимальное количество полицейских S, гарантирующих поимку беглеца.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
11.10.2009, 19:42     Задача Парсона #2
как вы сам понимаете эту задачу?
что значить поимка беглеца?
если беглец может двигаться с любой скоростью, то никто его никогда не поймает

какие начальные позиции? какая скорость у полицейских?

задача думаю не простая...
.::.DIMA.::.
143 / 143 / 4
Регистрация: 26.10.2008
Сообщений: 782
11.10.2009, 19:46     Задача Парсона #3
А главное, как задавать этот граф - ввод с клавиатуры или из файла, или, может быть, значения не вводятся, а сразу задаются?
Rumus
6 / 6 / 0
Регистрация: 29.09.2009
Сообщений: 91
11.10.2009, 19:55     Задача Парсона #4
Задача, что то вроде поиска крадчайшего пути....
lfin
2 / 2 / 0
Регистрация: 11.10.2009
Сообщений: 31
11.10.2009, 20:02  [ТС]     Задача Парсона #5
Цитата Сообщение от TanT Посмотреть сообщение
если беглец может двигаться с любой скоростью, то никто его никогда не поймает
Вот в этом как раз задача и состоит.
Цитата Сообщение от lfin Посмотреть сообщение
Требуется определить минимальное количество полицейских S, гарантирующих поимку беглеца
Ребят, сделайте хотя бы как нибудь...
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
11.10.2009, 20:04     Задача Парсона #6
Цитата Сообщение от lfin Посмотреть сообщение
Ребят, сделайте хотя бы как нибудь...
никогда так не говори, а то сделают

чтобы сделать, что-то надо понять что делать, а у нас исходных данных нет ...
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.10.2009, 21:19     Задача Парсона #7
Беглец в туннеле пойман, если с двух сторон туннеля его окружают полицейские.
Беглец в вершине пойман, если все туннели из этой вершины заняты полицейскими.
Граф задается стандартно - матрицей связности.
На самом деле скорость полицейских совершенно не важна. Важно то что беглец при движении по туннелю не может пройти мимо полицейского. А если двое полицейских окажутся от беглеца с двух сторон, то они будут сближаться и зажмут беглеца (то есть поймают его).
Задача на самом деле типичная задача на графы.
Yandex
Объявления
11.10.2009, 21:19     Задача Парсона
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru