Алгоритм Locker Room

Примечание: для того, чтобы дать хедз-ап, это не задание для моей школы, так как я сам даже не знаю, какая школа написала этот вопрос. Надеюсь, не возникло недоразумений.Алгоритм Locker Room

Я нашел эти интересные вопросы о раздевалке:

Раздевалки в РЭЦ N шкафчики, которые помечены 1, 2,. , ., N.

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

Копии ключа к каждому шкафчику находятся в смежных шкафчиках; т.е. копия ключа в шкафчик i помещается в шкафчик i + 1 и i-1 (ключ в шкафчик 1 находится только в шкафчике 2, а ключ к шкафчику N находится только в шкафу N-1).

T теннисные мячи находятся внутри T-образных шкафчиков (и вы знаете, какие из шкафов они находятся). Вам даны ключи от M шкафчики, и ваша цель - собрать все теннисные мячи на , открыв наименьшее количество шкафчиков.

Для фотографий вы можете видеть это непосредственно на the file here.

Я должен дать эти вопросы первому новичкам, но сначала я хотел убедиться, что у меня уже есть правильный ответ заранее.

То, что я имею в виду, что:

Нужно проверить мяч один за другим. Таким образом, для каждого шара (игнорируйте другие шары) каждый ключ должен посещать, пройдя к обозначенному шару. Для каждого ключа вычислите шаги, необходимые для посещения мяча. Наименьший результат хранится в переменной, называемой «total steps».
Сделайте это точно для следующего шара, и когда я получу минимальные шаги для этого текущего шара. Я добавляю это значение в «общие шаги».
Специальное условие применяется, если существует шар над ключом, то кнопка запуска перемещения от я + 1 и я - 1.

Мой вопрос: я прав? Я не хочу делиться неправильным алгоритмом с другими, так как это непрофессионально. С нетерпением ждем комментариев, предложений и материалов.

источник

2016-01-19 MasAdam

+14

Как это может быть непонятно? Он представил проблему и предложил алгоритм. Он ясно заявил, что не ищет кода, просто проверяет. – nicomp

@ KeithNicholas OP предложил алгоритм и хочет проверить, что он правильный. Хотя тег C должен быть удален, вопрос действителен и ясен. Я не думаю, что он заслуживает того, чтобы быть закрытым или downvoted –

Как бы вы его оценили без внедрения и тестирования? –

Ваш алгоритм не приведет к минимальному количеству шагов. Вы не можете рассматривать шары самостоятельно. Давайте рассмотрим следующий случай: у вас есть только один ключ для шкафчика номер 1, а шарики - в шкафчиках 12, 10, 8, 6, 4, 2. Если вы рассмотрите шары в том порядке, который я дал вам, равным 11 + 9 + 7 + 5 + 3 + 1, в то время как вы можете решить проблему за один проход из 11 шагов. Вы не должны игнорировать поля, посещенные на предыдущих шагах.

источник

2016-01-19 08:47:23

Привет, поэтому вы имеете в виду разделить на два направления для каждой клавиши (goLeft и goRight), продолжая считать открытый шкафчик? – MasAdam

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

@MasAdam. Вы также должны учитывать ситуацию, когда у вас есть шары в дверях 1 и 6 и клавишах 4 и 8. Расстояние от 8 до 4 до 6 одинаково , но вам все равно нужно открыть дверь 4, чтобы добраться до 1, поэтому он не должен рассчитывать на открытие двери 6. Таким образом, вы должны включить в свой алгоритм также обратную трассировку. Возможно, вы захотите опубликовать эту загадку на «головоломках и кодовом гольф» .SE, но имейте в виду, чтобы это было правильно для сайта. –

Вот техника, которую вы можете использовать:

Рассмотрим каждый шкафчик (в котором есть шар, которого у вас есть ключ, и которые не имеют ни одного) быть узлом в графе.Узлы будут двух типов:

A) Lockers having balls 
B) Lockers of which you have keys. 
C) Lockers which have none

Рассмотрим все шкафчики типа-А быть закрыт и типа-B, чтобы быть открытым.

От всех открытых шкафчиков найдите дорожки ко всем закрытым шкафчикам (от шкафчика типа B) и откройте шкафчик A с минимальной длиной пути. Также откройте все шкафы типа C, которые попадают в этот минимальный путь и перемещают их из категории C в B.

Повторяйте выше шага до открытия всех шкафчиков в A. Сумма всех минимальных дорожек, которые вы встретили, будет вашим ответом.

источник

2016-01-19 09:57:53 vish4071

Алгоритм Locker Room

ответ

Смежные вопросы