S>>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания? dmz>Соображалку проверить? Все не хуже, чем задача про открытый холодильник в ABBYY?
А что за задача? что-нибуть про скорость нагревания комнаты?
Есть много вариантов решения. Самый простой для реализации (но не самый оптимальный по объему вычислений):
1. Каждому перегону между станциями присваивается уникальный ID,
присваивается 2 направления (из A в B и из B в A)
2. Каждому паровозу присваивается описание, в котором задается ID
линии, на которой он в данный момент находится, направление
движения по этой линии, текущее расстояние от точки A линии
(0 — на станции A, длина линии — настанции B)
3. Инициируем список описаний паровозов начальными состояниями.
4. Перебираем список описаний паровозов, проверяем условие:
4.1. Если два паровоза находятся на одной линии и едут в
направлении друг друга — столкновение
4.2. Если два паровоза находятся в одной точке одной линии —
столкновение
5. Перебираем описание паровозов и для каждого паровоза изменяем
положение на линии в соответствии с его маршрутом. При этом
положение меняется на единицу измерения длины линии
(тоесть если длина линии в метрах — то каждый паровоз смещается
на один метр, если в километрах — то на километр итд.)
6. Повторяем шаг 4 достаточно большое количество итераций. Если
нужно точное решение — то пока не будет достигнуто начальное или
устойчивое состояние (проверка на устойчивость состояния
достаточно сложная, лениво писать .
Это самое-самое простейшее решение "в лоб". Можно намного
эффективнее — но уже думать надо, а у меня столько времени нету .
Здравствуйте, Spidola, Вы писали:
S>Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и выверенные алгоритмы, и навык их поиска и использования на порядок важнее, нежели умение придумывать свои, которые будут содержать потенциальные ошибки, будут неоптимальны и т.п.
Вы серьезно думаете, что на все задачи существуют готовые алгоритмы??? В таком случае должен вас огорчить: это не так.
Я не люблю придумывать велосипед и, если решение существует, предпочитаю использовать готовое, но, к сожалению (или счастью?), для большинства задач решения, по крайней мере, не опубликованы (а, следовательно, не существует).
Согласен, навык поиска очень важен, но навык умения мыслить намного важнее.
Здравствуйте, ANMNS, Вы писали:
ANM>Всем привет! ANM>Описание тестового задания:
ANM>Имеется железнодорожная сеть (набор станций и линий). ANM>Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях). ANM>Длины линий — целые числа. Станции идентифицируются номерами. Сеть ANM>задаётся тройками — ID станции, ID станции, Длина линии. ANM>Одновременно с равными постоянными скоростями стартуют по ANM>заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций. ANM>Требуется определить, не сталкиваются ли какие-то паровозики. ANM>Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке: ANM>- на одной линии, следуя в противоположные стороны, ANM>- на одной станции.
ANM>Использовать C++.
ANM>У кого-нибудь есть решение?
Направление мысли
Две ситуации — столкновение на станциях и столкновение на линиях.
Столкновения на станциях.
Скорость не важна, поэтому возьмём её за единицу. Есть длины линий и маршрут каждого паровозика, поэтому можно вычислить время прибытия каждого паровозика на каждую станцию его маршрута. Строится таблица:
ID паровозика, ID станции, T прибытия на станцию
Ищутся совпадения по ID станции и T прибытия.
Столкновения на линиях.
Принцип тот же, но построит нужно таблицу типа:
ID паровозика, ID станции откуда, ID станции куда, ID отбытия от станции откуда, ID прибытия на станции куда
Далее опять ищутся совпадения по диапазонам времени, только станции надо переворачивать (искать совпадения ID1-ID2 и ID2-ID1).
Ну и можно пооптимизировать немного для ускорения алгоритма (поиски всякие и т.п.)
Здравствуйте, v.v.m., Вы писали:
VVM>+, каждый уважающий себя программист должен быть знаком с теоретической частью, не зря же будущим программистам преподают теорию вероятности, графов, комбинаторику и т.д., хотя они и не собираются стать теоретиками?
Этот вопрос уже поднимался, так что можно его отнести к священным войнам... Однако, я всё равно за специализацию, тем более если решаемые задачи требуют математической подготовки. Ведь согласитесь, почему-то при решении финансовых задач, например, привлекаются финансисты, а не только программисты. Почему не иметь математика? Конечно, математика менее специализированная дисциплина, но всё-таки...
Здравствуйте, Spidola, Вы писали:
S>Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и выверенные алгоритмы, и навык их поиска и использования на порядок важнее, нежели умение придумывать свои, которые будут содержать потенциальные ошибки, будут неоптимальны и т.п.
В данном конкретном случае — да. Но речь идёт именно, чтобы посмотреть, КАК ты придумываешь алгоритмы.
Здравствуйте, olen33, Вы писали:
O>Здравствуйте, Spidola, Вы писали:
S>>Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и выверенные алгоритмы, и навык их поиска и использования на порядок важнее, нежели умение придумывать свои, которые будут содержать потенциальные ошибки, будут неоптимальны и т.п.
O>Вы серьезно думаете, что на все задачи существуют готовые алгоритмы??? В таком случае должен вас огорчить: это не так. O>Я не люблю придумывать велосипед и, если решение существует, предпочитаю использовать готовое, но, к сожалению (или счастью?), для большинства задач решения, по крайней мере, не опубликованы (а, следовательно, не существует).
Я считаю, что очень многие задачи можно свести к уже решённым. Поэтому, знать, что существуют решения типовых задач и саму постановку этих задач действительно хорошо бы знать, а вот подробности алгоритма решения знать можно, но необходимости нет.
O>Согласен, навык поиска очень важен, но навык умения мыслить намного важнее.
Умение мыслить, конечно, вешь немаловажная, здесь трудно не согласиться Однако, есть задачи, где мыслить не нужно, а нужно просто делать, поскольку уже промыслили всё давным-давно.
Работодатель в этом случае видит многое — понимает ли тестируемый сложность задачи, видит предложенный способ решения (если изобретается очередной "brute force" велосипед, скорее всего тестируемый плохо знаком с алгоритмами)
Еще как вариант — просто проверка умения программиста решать конкретные задачи и писать на C++ . Бо многие не решат или решат неправильно.
Если бы я получил такое задание — написал бы "brute force" велосипед с проверкой устойчивых состояний. Бо никто же не задавал условий оптимизации .
По поводу решения эффективными алгоритмами... Тут все не так посто. Я сам не математик (тоесть вышка конечно есть, что такое графы знаю итд. — просто не пользуюсь), но, ИМХО, подобная задача требует некоторого времени для создания математической модели. Если берут программиста-математика, то имеет смысл посидеть и написать. Если системного/прикладного программиста — то стоит ли заморачиваться?
В общем, от конкретного случая зависит . Если берут не математика — то скорее всего просто хотят посмотреть как человек умеет пользоваться C++ для решения прикладных задач. И сколько ошибок он допускает при их решении .
O>>Согласен, навык поиска очень важен, но навык умения мыслить намного важнее.
S>Умение мыслить, конечно, вешь немаловажная, здесь трудно не согласиться Однако, есть задачи, где мыслить не нужно, а нужно просто делать, поскольку уже промыслили всё давным-давно.
Вот, кстати, в институте мне именно такую политику и вдалбливали...что помнить надо все о небольшой предметной области и немного обо всем остальном
Но при этом четко значть где что есть и как найти детальное писание.
Здравствуйте, bopka_, Вы писали:
_>Здравствуйте, Spidola, Вы писали:
S>>Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и выверенные алгоритмы, и навык их поиска и использования на порядок важнее, нежели умение придумывать свои, которые будут содержать потенциальные ошибки, будут неоптимальны и т.п.
_>В данном конкретном случае — да. Но речь идёт именно, чтобы посмотреть, КАК ты придумываешь алгоритмы.
Сам подход к решению действительно может быть любопытен. Особенно если человеку придётся работать в команде. Согласен.
Здравствуйте, valmond, Вы писали:
O>>>Согласен, навык поиска очень важен, но навык умения мыслить намного важнее.
S>>Умение мыслить, конечно, вешь немаловажная, здесь трудно не согласиться Однако, есть задачи, где мыслить не нужно, а нужно просто делать, поскольку уже промыслили всё давным-давно.
V>Вот, кстати, в институте мне именно такую политику и вдалбливали...что помнить надо все о небольшой предметной области и немного обо всем остальном V>Но при этом четко значть где что есть и как найти детальное писание.
Повезло. Раньше в институте пытались вдолбить обратное Надо же! Хоть что-то к лучшему меняется.
Здравствуйте, ANMNS, Вы писали:
ANM>Имеется железнодорожная сеть (набор станций и линий). ANM>Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях). ANM>Длины линий — целые числа. Станции идентифицируются номерами. Сеть ANM>задаётся тройками — ID станции, ID станции, Длина линии. ANM>Одновременно с равными постоянными скоростями стартуют по ANM>заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций. ANM>Требуется определить, не сталкиваются ли какие-то паровозики. ANM>Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке: ANM>- на одной линии, следуя в противоположные стороны, ANM>- на одной станции.
Я бы на твоем месте, взял бы и нарисовал всю эту сеть, каждый паровозик своим цветом, рельсы отличным от цвета паровозиков, развязки цветом, отличным от остальных, действующих лиц... Все объек-ты точки.
Запускаешь много разноцветных точек и двигаешь их в указанных направлениях, если по ходу движения увидел цвет, отличный от цвета рельсов и цвета станций, все рисуй красочный взрыв. ( Можно ввести еще случайный фактор, переодически появляющиеся точки, цвета, отличного от предыдущих объектов — это будут коровы, например , или пешеходы , переходящие через рельсы.... )
Рисуешь всю эту железнодорожную сеть и прямо в реалтайме двигаешь паровозы
Эффектно
Ну конечно нужно учитывать погрешность, допустимых упрощений.
Идея родилась спонтанно, сам не проверял... Но как вариант...
Если бы мне такое принесли бы, как тестовое задание... (там можно и ООП накрутить, и черта в ступе... ) я бы оценил....
Скорость не важна, поэтому возьмём её за единицу. Есть длины линий и маршрут каждого паровозика, поэтому можно вычислить время прибытия каждого паровозика на каждую станцию его маршрута. Строится таблица:
Тут есть нюанс — не факт, что паровозики пересекуться во время первой итерации. Представим себе две кольцевые линии разной длины, пересекающиеся в одной точке — пересечься паровозики могут на 100-м проезде через станцию пересечения. Так что придется задавать не только время, но и интервалы. И считать эти интервалы на N шагов вперед... А так как у нас float очень ограниченной точности, то есть шанс на N-м проходе получить расхождение и ошибку (.
... а представьте, каково пасажирам в автоматизированном по Вашему алгоритму поезде? ^_^.
EOH>Скорость не важна, поэтому возьмём её за единицу. Есть длины линий и маршрут каждого паровозика, поэтому можно вычислить время прибытия каждого паровозика на каждую станцию его маршрута. Строится таблица:
EOH>Тут есть нюанс — не факт, что паровозики пересекуться во время первой итерации. Представим себе две кольцевые линии разной длины, пересекающиеся в одной точке — пересечься паровозики могут на 100-м проезде через станцию пересечения. Так что придется задавать не только время, но и интервалы. И считать эти интервалы на N шагов вперед... А так как у нас float очень ограниченной точности, то есть шанс на N-м проходе получить расхождение и ошибку (.
Не понял... Считаются ВСЕ перегоны для каждого поезда... Если поезд проходит через точку дважды, то это будет две записи второго типа...
И причём здесь float? По условию задачи "Длины линий — целые числа". Поскольку скорость не важна и можно взять её за единицу, тогда и времена будут целочисленные...
Не понял... Считаются ВСЕ перегоны для каждого поезда... Если поезд проходит через точку дважды, то это будет две записи второго типа...
Пути поездов обычно замкнутые. Если это не так — то задача решается brute force без вариантов . Для замкнутого пути поезд будет проходить через каждую точку потенциально бесконечно количество раз — поэтому и говорю, что придется задавать начальное время прибытия и интервал, когда он прибудет в следующий раз.
И причём здесь float? По условию задачи "Длины линий — целые числа". Поскольку скорость не важна и можно взять её за единицу, тогда и времена будут целочисленные...
Вообще да, мои извинения . В таком случае хорошее рещение, лучше моего простейшего — бо вычислений меньше.
mihoshi wrote: > > ANM>У кого-нибудь есть решение? > > Чначало выборуой сортируем порядок посещения станций. Получаем один > список, где записаны прибытия и отбытия, упорядоченный по времени, при > равном времение — сначала прибытия, потом отбытия. Потом эмулируем > движение. Шаг эмуляции — отправление/прибытия поезда на станцию. При > выезде со станции помечаем для нее, что с нее едет поезд в направлении > такой-то станции и вычеркиваем его из списка находящихся на станции. По > прибытии вычеркиваем из списка находящихся в пути для предыдущей, на > той, куда прибыли, записываем в список находящихся на станции. Проверяем > по списку, нет ли на станции еще паровозов и не едет ли в данный момент > поезд с этой станции туда, откуда мы выехали.
По-моему, если список событий правильно отсортировать (чтобы он был
отсортирован по времени, и одни и те же станции/перегоны оказались
рядом), то потом все коллизии можно будет найти в один проход по списку.
Такую сортировку тоже можно сделать в один прием, если правильно
составить функцию, упорядочивающую события (критерий сортировки).
Сложность получающегося решения будет N Log N, где N — число событий.
Основное время уйдет на сортировку списка. Я не думаю, что существует
более эффективное решение.
denis-b wrote: > > Встречал я как-то это тестовое задание. > А вакансия эта предлагалась через RSDN. > Так что, вероятность, что ваше сообщение будет прочитано тем, кто > предложил задание весьма велика > > Если вам в голову не приходит ни одного варианта решения этой задачи, то > идти туда работать наверное не стоит.
Работодателю надо будет каким-нибудь образом узнать, кто именно решил
задачу, и взять на работу именно этого человека
.
Однако, есть задачи, где мыслить не нужно, а нужно просто делать, поскольку уже промыслили всё давным-давно.
(.
