Имеется железнодорожная сеть (набор станций и линий).
Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях).
Длины линий — целые числа. Станции идентифицируются номерами. Сеть
задаётся тройками — ID станции, ID станции, Длина линии.
Одновременно с равными постоянными скоростями стартуют по
заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций.
Требуется определить, не сталкиваются ли какие-то паровозики.
Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке:
— на одной линии, следуя в противоположные стороны,
— на одной станции.
Здравствуйте, ANMNS, Вы писали:
ANM>У кого-нибудь есть решение?
Прошу прощения за резкость — а работать Вы так же собираетесь? Публиковать в форуме ТЗ и спрашивать "у кого-нибудь есть реализация?" Или просто хотите сравнить свое решение с чьим-либо еще?
[ posted via RSDN@Home 1.1.4 stable SR1 r568, accompanied by Sodom — Fields Of Honour ]
Здравствуйте, ANMNS, Вы писали:
ANM>У кого-нибудь есть решение?
Чначало выборуой сортируем порядок посещения станций. Получаем один список, где записаны прибытия и отбытия, упорядоченный по времени, при равном времение — сначала прибытия, потом отбытия. Потом эмулируем движение. Шаг эмуляции — отправление/прибытия поезда на станцию. При выезде со станции помечаем для нее, что с нее едет поезд в направлении такой-то станции и вычеркиваем его из списка находящихся на станции. По прибытии вычеркиваем из списка находящихся в пути для предыдущей, на той, куда прибыли, записываем в список находящихся на станции. Проверяем по списку, нет ли на станции еще паровозов и не едет ли в данный момент поезд с этой станции туда, откуда мы выехали.
Примерно так.
PS. "Список находящихся на станции" состоит из не более одного элемента
Здравствуйте, ANMNS, Вы писали:
ANM>Всем привет! ANM>Описание тестового задания:
ANM>Имеется железнодорожная сеть (набор станций и линий). ANM>Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях). ANM>Длины линий — целые числа. Станции идентифицируются номерами. Сеть ANM>задаётся тройками — ID станции, ID станции, Длина линии. ANM>Одновременно с равными постоянными скоростями стартуют по ANM>заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций. ANM>Требуется определить, не сталкиваются ли какие-то паровозики. ANM>Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке: ANM>- на одной линии, следуя в противоположные стороны, ANM>- на одной станции.
Здравствуйте, ANMNS, Вы писали:
ANM>Описание тестового задания:
... ANM>Использовать C++. ANM>У кого-нибудь есть решение?
А вам не приходило в голову, что тестовое задание дается для того, чтобы вы его решили сами?
И если вы не можете его решить, значит ваш уровень слишком низкий для работы в этой фирме.
Да забей
Всё равно ему решения сюда никто не напишет.
А вопросов типа "а у кого есть реализация" или "как мне сделать то-то и то-то" в этом форуме навалом, кстати.
Хотя чувак конечно всех переплюнул Думаю, если тот работодатель, кто дал ему задание, читает этот форум — работы чуваку не видать.
"SchweinDeBurg" <10117@users.rsdn.ru> wrote in message news:1476406@news.rsdn.ru... > Здравствуйте, ANMNS, Вы писали: > > ANM>У кого-нибудь есть решение? > > Прошу прощения за резкость — а работать Вы так же собираетесь? Публиковать в форуме ТЗ и спрашивать "у кого-нибудь есть реализация?" Или просто хотите сравнить свое решение с чьим-либо еще?
Ха-ха!
Эт тебе че, в аккорд-софте дали? судя по рассказам в этом форуме — как раз их специализация
"ANMNS" <47897@users.rsdn.ru> wrote in message news:1476391@news.rsdn.ru... > Всем привет! > Описание тестового задания: > > Имеется железнодорожная сеть (набор станций и линий). > Линии – одноколейные, но позволяющие движение в обе стороны. Между собой линии не пересекаются (кроме как на станциях). > Длины линий — целые числа. Станции идентифицируются номерами. Сеть > задаётся тройками — ID станции, ID станции, Длина линии. > Одновременно с равными постоянными скоростями стартуют по > заданным маршрутам несколько паровозиков. Маршрут каждого паровозика задаётся последовательностью номеров проходимых станций. > Требуется определить, не сталкиваются ли какие-то паровозики. > Столкновением считается ситуация, когда два паровозика одновременно находятся в одной точке: > — на одной линии, следуя в противоположные стороны, > — на одной станции. > > Использовать C++. > > У кого-нибудь есть решение? > > ANMNS
Встречал я как-то это тестовое задание.
А вакансия эта предлагалась через RSDN.
Так что, вероятность, что ваше сообщение будет прочитано тем, кто предложил задание весьма велика
Если вам в голову не приходит ни одного варианта решения этой задачи, то идти туда работать наверное не стоит.
ANM>У кого-нибудь есть решение?
Хех.
Да он даж язык вон в просьбе написал.
То есть ему нужно ужо всё написанное. А не ввиде примерных набросков на естественном языке.
"mihoshi" <14832@users.rsdn.ru> wrote in message news:1476461@news.rsdn.ru... > Здравствуйте, vs_, Вы писали: > > vs_>Да забей > vs_>Всё равно ему решения сюда никто не напишет. > Упс. Рефлекс
Есть математики, есть програмисты. Первые специализируются на решении математических задач (в том числе и численными методами). Вторые умеют правильно закодировать алгоритм, чтобы "компьютер" смог решать задачу.
Вот что мне непонятно, зачем тратить время программиста на решение математических задач. Что, C++ даёт преимущества перед другими языками с точки зрения решения данной задачи???
Единственное объяснение (не оправдание!) — это то, что компании требуются математики-програмисты. Хотя и это странно, поскольку если компания занимается решением такого рода задач, то должен быть специализированный математик.
Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
Здравствуйте, Spidola, Вы писали:
S>ИМХО: странная компания Поясню.
S>Есть математики, есть програмисты. Первые специализируются на решении математических задач (в том числе и численными методами). Вторые умеют правильно закодировать алгоритм, чтобы "компьютер" смог решать задачу.
S>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
Проверка, может ли кандидат мыслить и находить решения.
ИМХО, программист должен не только уметь кодировать готовый алгоритм, но и придумать свой (по крайней мере для таких простых случаев).
И я бы не сказал, что это математическая задачка.
Здравствуйте, valmond, Вы писали:
S>>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
V>Ну можен хочет понять общую эрудированность и сообразительность? V>типа как перевести эту задачу на мат язык, найти алгориты и реализовать.
V>я конечно в графах не силен, но что-то мне подсказывает, что есть готовые кирпичики из которых решение этой задачи складывается достаточно просто.
Конечно есть кирпичики Открывается учебник, смотрится алгоритм и алгоритмизируется. В чём смысл заставлять человека решать задачу, которая уже оптимально решена математиками? Единственное объяснение, которое я вижу, это посмотреть, насколько быстро человек НАЙДЁТ решение задачи, а не придумает его (ведь работодателю, по большому счёту, наплевать, как будет решена задача — главное, чтобы она была решена корректно, в нужный срок и заминимальную стоимость).
В свете этого пост автора можно рассматривать как шаг правильный и корректный
S>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
Соображалку проверить? Все не хуже, чем задача про открытый холодильник в ABBYY?
Здравствуйте, olen33, Вы писали:
O>Здравствуйте, Spidola, Вы писали:
S>>ИМХО: странная компания Поясню.
S>>Есть математики, есть програмисты. Первые специализируются на решении математических задач (в том числе и численными методами). Вторые умеют правильно закодировать алгоритм, чтобы "компьютер" смог решать задачу.
S>>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
O>Проверка, может ли кандидат мыслить и находить решения. O>ИМХО, программист должен не только уметь кодировать готовый алгоритм, но и придумать свой (по крайней мере для таких простых случаев). O>И я бы не сказал, что это математическая задачка.
Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и выверенные алгоритмы, и навык их поиска и использования на порядок важнее, нежели умение придумывать свои, которые будут содержать потенциальные ошибки, будут неоптимальны и т.п.
Здравствуйте, Spidola, Вы писали:
S>Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая такие задания?
имхо Вы неправы. Задание нормальное, и с его помощью работодатель может очень многое узнать о человеке. Конечно, разработка новых алгоритмов работы на графах — не задание тестового уровня. Но такого задания никто и не давал, ведь скорее всего соответствующие алгоритмы уже изобретены, и от программиста требуется только найти адекватный алгоритм и правильно его применить.
Работодатель в этом случае видит многое — понимает ли тестируемый сложность задачи, видит предложенный способ решения (если изобретается очередной "brute force" велосипед, скорее всего тестируемый плохо знаком с алгоритмами). Плюс, культура кодирования, владение конкретным языком. Может С++ и не дает преимуществ, но компании нужны С++ программисты — так что давать задание на Паскале?
+, каждый уважающий себя программист должен быть знаком с теоретической частью, не зря же будущим программистам преподают теорию вероятности, графов, комбинаторику и т.д., хотя они и не собираются стать теоретиками?
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. > Так что, вероятность, что ваше сообщение будет прочитано тем, кто > предложил задание весьма велика > > Если вам в голову не приходит ни одного варианта решения этой задачи, то > идти туда работать наверное не стоит.
Работодателю надо будет каким-нибудь образом узнать, кто именно решил
задачу, и взять на работу именно этого человека
Spidola wrote: > > ИМХО: странная компания Поясню. > > Есть математики, есть програмисты. Первые специализируются на решении > математических задач (в том числе и численными методами). Вторые умеют > правильно закодировать алгоритм, чтобы "компьютер" смог решать задачу.
. . . . > Вот объясните мне, пожалуйста, какую цель приследует работодатель, давая > такие задания?
Посмотрев на решение, можно очень многое узнать о человеке.
Например, если человек погонится за оптимальным алгоритмом, но при этом
не будет обрабатывать ошибки во входных данных, я бы такого человека не
взял. Его программы будут (наверное) хорошо работать в некоторых
стерильных условиях, взятых из идеального мира, но в жизни работать не
будут.
Если же человек выберет пусть и не самый оптимальный, но приемлимый в
реальной жизни алгоритм, но закодирует его надежно, с таким человеком
можно работать. В конце концов, элегантные алгоритмы встречаются в
реальных программах нечасто, а надежное кодирование необходимо всегда.
Хорошо бы так же понять, как человек собирается отлаживать такую
програмку. Например, assert'ы и/или отладочная печать в ключевых местах,
это плюс. Отсутствие этого, или бессмысленная отладочная печать на
каждом углу, по которой ничего не поймешь, это минус.
И наконец, чтобы отсечь кандидатов, которые не сами придумали решение,
есть смысл прямо на собеседовании слегка изменить условия задачи, и
попросить человека подкрутить програмку.
Spidola wrote: > > O>Проверка, может ли кандидат мыслить и находить решения. > O>ИМХО, программист должен не только уметь кодировать готовый алгоритм, > но и придумать свой (по крайней мере для таких простых случаев). > O>И я бы не сказал, что это математическая задачка. > > Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и > выверенные алгоритмы, и навык их поиска и использования на порядок > важнее, нежели умение придумывать свои, которые будут содержать > потенциальные ошибки, будут неоптимальны и т.п.
Ну это тоже довольно спорная позиция. Чтобы ориентироваться в готовых
алгоритмах, надо уметь придумывать свои. По крайней мере, простые. Никто
ведь не ждет от простого программиста, что он самостоятельно придумает,
как из регулярного выражения построить детерменированный конечный
автомат. Но вещи попроще программист вполне может придумать сам.
Что же касается идеи, что самодельный алгоритм всегда хуже/менее
надежен/менее оптимален, чем готовый, с этим тоже можно поспорить.
Во-первых, Вы тем самым предполагаете, что хорошие алгоритмы придумывают
некие богоподобные существа, к которым Вы точно не относитесь.
Во-вторых, ошибка в готовом алгоритме (или боги не ошибаются?) должна
повергнуть Вас в состояние полного ступора, ведь Вы не просто не
понимаете, как этот алгоритм работает, Вы еще и считаете это непонимание
своим достоинством.
На самом деле, готовые библиотеки пишут такие же средненькие
программисты, как и мы с Вами, и ошибок и неоптимальностей там ничуть не
меньше, чем в наших программах. Конечно, готовая библиотека немного
получше оттестирована и отлажена, чем мы с Вами можем себе позволить, но
даже из оттестированных програм время от времени вылезают разные
интересные сюрпризы...
olen33 wrote: > > S>Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и > выверенные алгоритмы, и навык их поиска и использования на порядок > важнее, нежели умение придумывать свои, которые будут содержать > потенциальные ошибки, будут неоптимальны и т.п. > > Вы серьезно думаете, что на все задачи существуют готовые алгоритмы??? В > таком случае должен вас огорчить: это не так. > Я не люблю придумывать велосипед и, если решение существует, предпочитаю > использовать готовое, но, к сожалению (или счастью?), для большинства > задач решения, по крайней мере, не опубликованы (а, следовательно, не > существует).
А я люблю (хотя менеджерам про это лучше не говорить). Именно это
доставляет наибольшее удовольствие от работы, не так ли?
BishopMorton wrote: > > Я бы на твоем месте, взял бы и нарисовал всю эту сеть, каждый паровозик > своим цветом, рельсы отличным от цвета паровозиков, развязки цветом, > отличным от остальных, действующих лиц... Все объек-ты точки. > Запускаешь много разноцветных точек и двигаешь их в указанных > направлениях, если по ходу движения увидел цвет, отличный от цвета > рельсов и цвета станций, все рисуй красочный взрыв. ( Можно ввести еще > случайный фактор, переодически появляющиеся точки, цвета, отличного от > предыдущих объектов — это будут коровы, например , или пешеходы , > переходящие через рельсы.... )
Еще лучше прийти на собеседование с разноцветными паровозиками, и со
словами "сейчас-сейчас, я все объясню", начать увлеченно двигать ими
перед носом изумленных работодателей.
Здравствуйте, Pzz, Вы писали:
>> Я не люблю придумывать велосипед и, если решение существует, предпочитаю >> использовать готовое, но, к сожалению (или счастью?), для большинства >> задач решения, по крайней мере, не опубликованы (а, следовательно, не >> существует).
Pzz>А я люблю (хотя менеджерам про это лучше не говорить). Именно это Pzz>доставляет наибольшее удовольствие от работы, не так ли?
Придумывать велосипед? Не думаю, что вы пишите быструю сортировку сами, даже там, где ее нет (VB).
А вот придумать что-то умное и новое (хотя бы в маленькой предметной области) всегда приятно
olen33 wrote: > > Pzz>А я люблю (хотя менеджерам про это лучше не говорить). Именно это > Pzz>доставляет наибольшее удовольствие от работы, не так ли? > > Придумывать велосипед? Не думаю, что вы пишите быструю сортировку сами, > даже там, где ее нет (VB).
Иногда и сортировку приходится писать. Особенно там, где ее нет
> А вот придумать что-то умное и новое (хотя бы в маленькой предметной > области) всегда приятно
Это да. Вообще, приятно, когда программа не сводится к "взять данные в
одном месте, положить в другое и сделать это вовремя".
Здравствуйте, Pzz, Вы писали:
Pzz>Spidola wrote: >> >> O>Проверка, может ли кандидат мыслить и находить решения. >> O>ИМХО, программист должен не только уметь кодировать готовый алгоритм, >> но и придумать свой (по крайней мере для таких простых случаев). >> O>И я бы не сказал, что это математическая задачка. >> >> Зачем??? Зачем придумывать свой алгоритм??? Есть проверенные и >> выверенные алгоритмы, и навык их поиска и использования на порядок >> важнее, нежели умение придумывать свои, которые будут содержать >> потенциальные ошибки, будут неоптимальны и т.п.
Pzz>Ну это тоже довольно спорная позиция. Чтобы ориентироваться в готовых Pzz>алгоритмах, надо уметь придумывать свои. По крайней мере, простые.
Вот это действительно спорно.
Pzz> Никто ведь не ждет от простого программиста, что он самостоятельно придумает, Pzz>как из регулярного выражения построить детерменированный конечный Pzz>автомат. Но вещи попроще программист вполне может придумать сам.
Может, но зачем. Если это действительно алгоритм, который описан, то самому его
придумывать не нужно. Можно воспользоваться готовым. Вообще речь идёт о
разных алгоритмах у нас с вами. Я имею ввиду алгоритмы решения задач типа
транспортных и т.п.
Pzz>Что же касается идеи, что самодельный алгоритм всегда хуже/менее Pzz>надежен/менее оптимален, чем готовый, с этим тоже можно поспорить.
Вероятность наличия ошибок и неоптимальности самопридуманного алгоритма значительно
выше. Почему? Вроде очевидно — существующий алгоритм уже не раз использован
и проверен.
Pzz>Во-первых, Вы тем самым предполагаете, что хорошие алгоритмы придумывают Pzz>некие богоподобные существа, к которым Вы точно не относитесь. Я всегда так думал, честно говоря. Инопланетяне
Pzz>Во-вторых, ошибка в готовом алгоритме (или боги не ошибаются?) должна Pzz>повергнуть Вас в состояние полного ступора, ведь Вы не просто не Pzz>понимаете, как этот алгоритм работает, Вы еще и считаете это непонимание Pzz>своим достоинством.
Так в этих алгоритмах практически нет ошибок — они же ВЫВЕРЕННЫЕ И ОТЛАЖЕННЫЕ
в большинстве своём!!!
Pzz>На самом деле, готовые библиотеки пишут такие же средненькие Pzz>программисты, как и мы с Вами, и ошибок и неоптимальностей там ничуть не Pzz>меньше, чем в наших программах.
Вы опять говорите о готовых библиотеках с программным кодом. Я говорю об алгоритмах
как таковых в математическом понимании. Безотносительно к языкам программирования.
Численные методы, к примеру.
Pzz>Конечно, готовая библиотека немного Pzz>получше оттестирована и отлажена, чем мы с Вами можем себе позволить, но Pzz>даже из оттестированных програм время от времени вылезают разные Pzz>интересные сюрпризы...
Да уж. Windows ЖЖЁТ.
Давным-давно, в далёкой-далёкой стране у самых Синих гор жил один молодой человек, который очень хотел стать Мастером Меча. А по обычаям той земли, настоящим Мастером Меча мог стать только тот, у кого был настоящий Меч Мастера.
Молодой человек очень хотел стать Мастером, и он отправился по городам далёкой страны у самых Синих гор. Он хотел прийти к одному из старых Мастеров Меча и попросить его:
— Великий Мастер! Слава о твоих подвигах идёт по всей стране. Ты сражался во всех больших сражениях. Ты всегда побеждал, заслужил славу и почёт. Но теперь ты живёшь в покое, у тебя есть всё, что ты хочешь, и тебе больше не нужен твой Меч — Меч Мастера. Продай его мне, или подари.
Молодой человек очень надеялся, что кто-то из старых Мастеров откликнется на его просьбу, и он отправился в путь и долго шёл, направляясь к одному из больших городов, где, как он знал, жил престарелый Мастер Меча. Он шёл долго и вошёл в ворота. Он у всех спрашивал дорогу, и каждый с готовностью показывал ему дом, в котором жил этот человек — великий Мастер Меча, ушедший на покой. И юноша пришёл в его дом и обратился к нему:
— Великий Мастер! Слава о твоих подвигах идёт по всей стране. Ты сражался во всех больших сражениях. Ты всегда побеждал, заслужил славу и почёт. Но теперь ты живёшь в покое, у тебя всё есть, и тебе больше не нужен твой Меч — Меч Мастера. Подари его мне, или продай.
Мастер Меча выслушал юношу, улыбнулся и ответил ему:
— Я бы с радостью, но ты знаешь, этот меч тебе не подойдёт.
Молодой человек поклонился Мастеру и снова отправился в путь.
Он поднимался в горы, спускался в долины, он плыл по рекам, переправлялся через них и шёл дальше. Он пришёл в другой город, нашёл дом старого Мастера Меча. Он вошёл в этот дом и обратился к Мастеру:
— Великий Мастер! Слава о твоих подвигах идёт по всей стране. Ты сражался во всех больших сражениях. Ты всегда побеждал и заслужил славу и почёт. Ты — настоящий Мастер, это все знают. Но теперь ты живёшь в покое, у тебя есть всё, и тебе больше не нужен твой Меч — Меч Мастера. Продай его мне, или подари.
И старый Мастер Меча выслушал юношу, улыбнулся ему и ответил:
— Я бы с радостью, но ты знаешь, этот меч тебе не подойдёт.
И вновь отправился в путь юноша, который очень хотел стать настоящим Мастером Меча. Он шёл всё дальше, находил старых Мастеров и обращался к ним с одной и той же просьбой:
— Великий Мастер! Слава о твоих подвигах идёт по всей стране. Ты сражался во всех больших сражениях. Ты всегда побеждал и заслужил славу и почёт. И вот теперь, великий Мастер, ты живёшь в покое, у тебя есть всё, о чём можно только мечтать, и тебе больше не нужен твой Меч — настоящий Меч Мастера. Продай его мне, или подари.
И раз за разом, выслушав юношу, старые мудрые Мастера улыбались и отвечали одно и то же:
— Я бы отдал, но ты знаешь, этот меч тебе не подойдёт.
И тогда молодой человек решил отправиться в горы, на поиски тайных кузнецов. Он шёл дни и ночи. Вставал с восходом, ложился спать, когда солнце уже давно село. Он спал мало, и всё шёл и шёл далеко в горы. И наконец он нашёл далеко в Синих горах тайных кузнецов и рассказал о своём положении. Он попросил выковать ему меч, который бы казался настоящим Мечом Мастера. Кузнецы выслушали его и ответили:
— Ты хочешь стать Мастером, и тебе нужен Меч. Хорошо.
И они выковали ему меч, который так же сверкал благородной сталью, легко рассекал железо, шёлк или волос, был великолепно сбалансирован, покрыт сложной замысловатой чеканкой и выглядел как самый настоящий Меч Мастера. Юноша с радостью и благодарностью принял свой новый меч, поклонился тайным кузнецам и отправился в путь.
Он сражался во многих битвах и побеждал. Слава о нём разносилась всё дальше по далёкой стране, опережала его появление, приводила в восторг друзей, вселяла уважение в сердца противников. Он прожил богатую, достойную жизнь и однажды, наконец, ушёл на покой, поселился в одном городе далёкой страны и много лет жил спокойно и счастливо. И лишь иногда, когда гости восхваляли его, настоящего Мастера Меча, ему становилось неловко. Ведь он-то знал, что у него так и не было настоящего Меча Мастера.
И как-то раз к нему пришёл незнакомый юноша. Он поклонился и сказал:
— Великий Мастер! Слава о твоих подвигах идёт по всей стране. Ты сражался во всех больших сражениях. Ты всегда побеждал и заслужил славу и почёт. Ты — настоящий Мастер, все это знают. И вот теперь ты живёшь на покое, у тебя есть всё, и тебе больше не нужен твой Меч — Меч Мастера. Продай его мне, или подари.
Здравствуйте, Pzz, Вы писали:
Pzz>Еще лучше прийти на собеседование с разноцветными паровозиками, и со Pzz>словами "сейчас-сейчас, я все объясню", начать увлеченно двигать ими Pzz>перед носом изумленных работодателей.
"А давайте сыграем в интересную игру? В паровоз!" (С)мультик
Здравствуйте, Disciplester, Вы писали:
D>- Великий Мастер! Слава о твоих подвигах идёт по всей стране. Ты сражался во всех больших сражениях. Ты всегда побеждал и заслужил славу и почёт. Ты — настоящий Мастер, все это знают. И вот теперь ты живёшь на покое, у тебя есть всё, и тебе больше не нужен твой Меч — Меч Мастера. Продай его мне, или подари.
Россия. Новости. Черезвычайные происшествия.
— Вчера был пойман подозреваемый в убийстве Мастера Меча, ушедшего на покой. Подозреваемый объяснил своё деяние тем, что ему нужен был Меч, а Мастер Меча его не отдавал.
SDB>Прошу прощения за резкость — а работать Вы так же собираетесь? Публиковать в форуме ТЗ и спрашивать "у кого-нибудь есть >реализация?" Или просто хотите сравнить свое решение с чьим-либо еще?
Это тестовое задание компании Trancas из SPb. Мне такое же прислали недели полторы назад. Я его сделал в лоб. Судя потому, что от них до сих пор нет вестей они ищут человека, который не будет решать данную задачу в лоб.
Здравствуйте, Dair, Вы писали:
SM>>Это тестовое задание компании Transas из SPb.
D>Прости пожалуйста, а на какую вакансию (и за какие деньги ) такое тестовое задание?
Насколько я помню С# программист на 1200 у.е. Заявка в соседнем форуме. От этой компании посмотри.
Или просто хотите сравнить свое решение с чьим-либо еще?
(.
) такое тестовое задание?
