Первая дуэль. , Наичистейший С++ vs С++ + stl + boost

[trainer]

Предлагаю вспомнить, как проходили задачи в C/C++: есть условие, есть автор условия. Если есть уточняющие задачу вопросы - спрашивайте. Вопросов нет - поехали.

[Sazabis]

Поиск оптимального алгоритма в какой-то степени важен, ИМХО. Вот посмотрел код Flex Ferrum'a что то с трудом идет
много чего не понятно, а в частности, как это вообще работает

[Flex Ferrum]

Цитата Sazabis @ 21.09.05, 08:48

много чего не понятно, а в частности, как это вообще работает

Комментарии добавить?

[Sazabis]

Цитата Flex Ferrum @ 21.09.05, 08:55

Комментарии добавить?

конечно. Желательно еще обосновать выбор. Почему например используеться list а не stack(deque) ? а как вообще с тестами которые я выложил, работает верно ?

[nvm]

Цитата Flex Ferrum @ 21.09.05, 08:25

Я ссылок на возможность присутствия колец в условии задачи не нашел.

Ограничения принято указывать явно. А если ограничение не описано, то подразумевается, что его нет.
Никаких намеков на то, что нельзя проезжать один перекресток дважды, не было.

Цитата

Мне кажется (что по этому поводу думают остальные?), что детали наподобия колец и возможности возврата в данном случае не существенны.

Несущественны, если не требуют существенного изменения алгоритма.
Но может быть, эта деталь меняет полиномиальность на неполиномиальность.

Кстати, ты можешь доказать, что в отсутствии циклов твой алгоритм гарантирует находжение решения? Может статься, что Дейкстра тут вообще неприменим.

Прицепи экзешник - попробую найти контрпример без циклов.

[Flex Ferrum]

Цитата nvm @ 21.09.05, 13:12

Ограничения принято указывать явно. А если ограничение не описано, то подразумевается, что его нет.

Совершенно необязательно. Как правильно скзал trainer, если текст задания недоконца ясен - неясные моменты уточняют вопросами. В нашем случае на вопрос "обрабатывать ли кольца" и "обрабатывать ли возвраты" был получен ответ - "нет, не надо".

[nvm]

Цитата Flex Ferrum @ 21.09.05, 14:23

Цитата nvm @ 21.09.05, 13:12

Ограничения принято указывать явно. А если ограничение не описано, то подразумевается, что его нет.

Совершенно необязательно. Как правильно скзал trainer, если текст задания недоконца ясен - неясные моменты уточняют вопросами. В нашем случае на вопрос "обрабатывать ли кольца" и "обрабатывать ли возвраты" был получен ответ - "нет, не надо".

Совершенно обязательно - это основополагающее соглашение, которое обязано соблюдаться в любом строгом изложении, в т. ч. в постановках задач.

Текст задачи вполне ясен, и из него следует, что кольца допускаются.

Здесь невозможны другие трактовки.

Сообщение отредактировано: nvm - 21.09.05, 15:14

[Flex Ferrum]

Цитата nvm @ 21.09.05, 15:07

Текст задачи вполне ясен, и из него следует, что кольца допускаются.

Из какой фразы это следует?

[nvm]

Цитата Flex Ferrum @ 21.09.05, 15:10

Цитата nvm @ 21.09.05, 15:07

Текст задачи вполне ясен, и из него следует, что кольца допускаются.

Из какой фразы это следует?

Из отсутствия обратного утверждения.

[trainer]

Цитата nvm @ 21.09.05, 13:12

Ограничения принято указывать явно. А если ограничение не описано, то подразумевается, что его нет.

Ограничения - вещь относительная. Например, ограничение скорости в 100 км/ч - это снизу или сверху?
Если не уточнил - будь уверен, ситуацию истолкуют не в твою пользу. Суровая правда жизни.

[nvm]

Может в ТЗ и спецификациях сейчас и принято не оговаривать ограничения, но задачи должны соблюдать академическую культуру изложения.

[Flex Ferrum]

Цитата nvm @ 21.09.05, 15:15

Из отсутствия обратного утверждения.

В таком случае я склонен с тобою несогласиться. Ибо в этом случае я могу сказать: "в задаче не сказано, что нужно обрабатывать кольца. По этому я не буду их обрабатывать". И что будем делать? Правильно - спрашивать постановщика.

Добавлено 21.09.05, 15:19

Цитата nvm @ 21.09.05, 15:16

Может в ТЗ и спецификациях сейчас и принято не оговаривать ограничения, но задачи должны соблюдать академическую культуру изложения.

nvm, извини, ты слишком сильно заморочился. По твоей логике задачу "напишите мне программу, выводящую на экран строку "Hello World!"" надо начинать с разработки собственной ОС. Ибо в задаче не сказано обратного.

Добавлено 21.09.05, 15:26

Цитата Sazabis @ 21.09.05, 09:09

а как вообще с тестами которые я выложил, работает верно

Верно то оно верно, только вот speed4.in колбасила 10598406 msecs - почти 3 часа (правда, надо учесть, что с приоритетом "Low", т. к. паралельно и другими делами компьютер приходилось занимать). На ночь запущу speed8.in, а покуда подумаю над оптимизацией и сужением пространства поиска. Блин, ну нельзя так - задача превратилась в чисто алгоритмическую .

[nvm]

Цитата Flex Ferrum @ 21.09.05, 15:17

Добавлено 21.09.05, 15:19

Цитата nvm @ 21.09.05, 15:16

Может в ТЗ и спецификациях сейчас и принято не оговаривать ограничения, но задачи должны соблюдать академическую культуру изложения.

nvm, извини, ты слишком сильно заморочился. По твоей логике задачу "напишите мне программу, выводящую на экран строку "Hello World!"" надо начинать с разработки собственной ОС. Ибо в задаче не сказано обратного.

Видно, что программисты хорошо насобачились истолковывать постановки в свою пользу..

Если в ТЗ сказано напечатать целые числа от 0 до 10, а заказчик, оказывается, имел в виду только четные - он должен принять работу, так как это доп. ограничение он в ТЗ не вписывал.

Если в задаче говорится найти самый быстрый путь, то с какой стати ты предлагаешь не самый быстрый, утверждая, что именно это и имелось в виду?!

[Flex Ferrum]

Цитата nvm @ 21.09.05, 15:29

Если в задаче говорится найти самый быстрый путь, то с какой стати ты предлагаешь не самый быстрый, утверждая, что именно это и имелось в виду?!

Никто не мешает использовать дополнительные знания о предметной области. Нам с тобой известно, что в тестовых файлах будут графы без колец и возвратов. Так зачем усложнять себе жизнь?

Добавлено 21.09.05, 15:34

Цитата nvm @ 21.09.05, 15:29

Видно, что программисты хорошо насобачились истолковывать постановки в свою пользу..

Естественно. Ибо время - деньги. Можно потратить месяц на разработку программы, решающей общий случай и неделю - на программу, решающую частный случай. Если точно известно, что будут только частные случаи (и других не будет) - "зачем платить больше"?

[trainer]

Цитата nvm @ 21.09.05, 15:29

Если в ТЗ сказано напечатать целые числа от 0 до 10, а заказчик, оказывается, имел в виду только четные - он должен принять работу, так как это доп. ограничение он в ТЗ не вписывал.

Это ты перегибаешь. Заказчик хочет, чтобы были целые числа от 0 до 10, но не оговорил последовательность, то он может взять твою работу, а может и не взять, т.к. ему надо в виде 10-9-..-1-0. Для него это естественно, а для тебя - ограничение.

В общем, фальстарт получился