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

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

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

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

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

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

Задача Парсона (1982 РЖМат 11В682) Пусть G - конечный неориентированный связный граф. Предположим, что он представляет собой систему тоннелей, в которых может прятаться беглец. Группа из S полицейских, двигаясь по туннелям,
стремится схватить этого беглеца, который может двигаться с любой скоростью, стремясь избежать поимки. Требуется определить минимальное количество полицейских S, гарантирующих поимку беглеца.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2009, 18:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача Парсона (C++):

Задача: В некотором государстве ввели компьютерный паспорт гражданина.(задача) - Pascal
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных голов. Задача: В некотором...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника - PascalABC.NET
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Задача на k-тую цифру последовательности, задача на схему Горнера. - Pascal
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности 1234567891011121314…, в которой выписаны подряд...

Первая смешанная задача для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье - Дифференциальные уравнения
Решить первую смешанную задачу для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье ...

Задача о размещении весов по ящикам (задача о рюкзаках) - Delphi
Есть упорядоченный по невозрастанию набор весов предметов w1..wn, которые необходимо распределить по ящикам способным выдержать вес V,...

Задача на файл и задача на создание очереди - Pascal
1 Дан символьный файл, содержащий, по крайней мере, один символ пробела. Удалить из файла все символы, предшествующие пробелу 2 ...

6
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
11.10.2009, 19:42 #2
как вы сам понимаете эту задачу?
что значить поимка беглеца?
если беглец может двигаться с любой скоростью, то никто его никогда не поймает

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

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

чтобы сделать, что-то надо понять что делать, а у нас исходных данных нет ...
0
odip
Эксперт С++
7157 / 3219 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.10.2009, 21:19 #7
Беглец в туннеле пойман, если с двух сторон туннеля его окружают полицейские.
Беглец в вершине пойман, если все туннели из этой вершины заняты полицейскими.
Граф задается стандартно - матрицей связности.
На самом деле скорость полицейских совершенно не важна. Важно то что беглец при движении по туннелю не может пройти мимо полицейского. А если двое полицейских окажутся от беглеца с двух сторон, то они будут сближаться и зажмут беглеца (то есть поймают его).
Задача на самом деле типичная задача на графы.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2009, 21:19
Привет! Вот еще темы с ответами:

Задача линейного программирования, транспортная задача - Методы оптимизации
Всем привет. сижу на экзамене, помогите пожалуйста решить,сроно!!! заранее спасибо.

Задача Дам или задача Восьми - Алгоритмы
помогите найти ошибку в алгоритме. не находит ответ подозреваю ошибку в k, i, j package com.company; import java.util.Arrays;...

задача Коши и краевая задача - Matlab
Помогите кто чем может))

Задача работы с массивом и задача работы с формой - C#
Помогите пожалуйста. Никак не могу разобраться с решением 2х задач: 1. Напишите приложение, которое в заголовке формы выводит ее...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Yandex
Объявления
11.10.2009, 21:19
Ответ Создать тему
Опции темы

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