Разное

На рисунке (во вложении) показана сеть дорог одного из районов города. Мусоросборщик должен пройти по всем дорогам, чтобы собрать мусор. Число на каждой стороне показывает время, которое должен потратить мусоровоз, чтобы проехать этот интервал. На перекрестках мусорка ожидает время, которое равно количеству пересекающихся дорог.
Нужно составить программу, показывающую как выбрать необходимый путь для сбора мусора в кратчайшее время.
Есть 11 остановок.
от 1 до 2 путь 10 мин.
от 1 до 3 путь 4 мин.
от 1 до 4 путь 8 мин.
от 2 до 3 путь 8 мин.
от 2 до 5 путь 6 мин.
от 3 до 4 путь 4 мин.
от 3 до 5 путь 7 мин.
от 4 до 7 путь 7 мин.
от 4 до 6 путь 10 мин.
от 4 до 8 путь 7 мин.
от 8 до 6 путь 7 мин.
от 8 до 10 путь 6 мин.
от 10 до 6 путь 11 мин.
от 6 до 9 путь 4 мин.
от 10 до 9 путь 12 мин.
от 6 до 11 путь 5 мин.
от 6 до 4 путь 8 мин.
от 5 до 4 путь 8 мин.
от 4 до 11 путь 13 мин.
от 9 до 11 путь 5 мин.

Запутанно.
>от 1 до 2 путь 10 мин.
Вот это что? И как это относится к тому, что на рисунке?

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

>>от 1 до 2 путь 10 мин.
>Вот это что? И как это относится к тому, что на рисунке?

Тебе может ответ сразу сказать?

ps Кому интересно, пускай помыслят. А ты сайтостроительством руководи :)
Но задача, вообще говоря, сильное прикладное значение имеет. Много где. В тех или иных вариациях. Это мы для олимпиады по программированию придумывали. И примерно такое я вот на собеседованиях спрашиваю.

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

>>надо будет вечерком залезть в старые вузовские конспекты

Ну всё... Все в вузовские конспекты полезли :)

>Ну всё... Все в вузовские конспекты полезли :)

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

и подобная задачка была... хотя нет, там что-то про мосты было.

> Ну всё... Все в вузовские конспекты полезли :)

Ну а как иначе? В голове хранится только название области знаний (графы) и ссылка на место где лежит конкретика ) А зачем помнить весь алгоритм, если не пользовался им 15 лет? При чем даже рядом ничего не было.

для начала, я так понимаю, предлагается расставить точки?

Нужно определить для начала взвешенный граф.

это да :(
не для меня, короче. Оставлю в закладках, вернусь через пару лет.

Это задача непростая. Могу попроще подкинуть. С той же Олимпиады.
Для решения этой задачи нужно знание теории графов. Но программист, не знающий теории графов, это поделка от профессии.
Это я ещё не самый сложный вариант привел. Вернее, просто выдернул когда-то кусок из схемы очень огромной. Так, чтоб школяры, увлекающиеся программированием, могли решить. Не обязательно код даже. Мне вполне было достаточно, чтобы сказали, что и как делать. А код то и дурак напишет. Это - самое простое. А вот такие задачки нужны для того, чтобы электросети проектировать, маршруты движения поездов и всего другого, что движется и т.д.д. Ведь программирование оно решает прикладные задачи, а не просто существует ради самого себя. Оно должно быть жизненным. Т.е. решать задачи, которые ставит жизнь.

>Т.е. решать задачи, которые ставит жизнь.

Вот информация с сайта http://soft.compulenta.ru/467882/

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

И наша Студия в первую голову занималась именно такими задачами. Их почти нет в портфолио. По разным причинам. Иногда - по идиотским. Это я про себя. Некоторые просто жалко выкладывать. Что, конечно, неверно, но. Вот жалко. Я их писал в очень сложной для себя ситуации. Оттого и.

Ожидал увидеть что-то связанное с темой "garbage collections"))

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

> Потом всю ночь снилось ужасть что)
:) Я еще ужасных снов подкину.

Я вот одного не понял... Зачем рисунок. Если для того чтобы по указанным "время, которое должен потратить мусоровоз" определить номера точек и учесть еще дополнительно задержку на перекрестках, то понятно. Но тогда рисунок не правильный. В смысле получается в любом случае рисунок не правильный. Если в цифрах дано полное время от точки до точки, то на рисунке должны быть цифры равные (время указанное в посте цифрами минус время на перекрестках встречающихся на этом отрезке). Этого не получится, т.к. например на отрезке слева внизу по горизонтали указано 12, плюс 3 на перекрестке = 15. А таких больших цифр в условии нет. Если на рисунке указано то же время что и в условии (общее), то справа внизу по горизонтали указано 9, чего в условии тоже нет. Условие тоже туманно сформулировано. Если цифрами дано полное время от точки до точки, то перекрестки и рисунок вообще не нужны. Да и "На перекрестках мусорка ожидает время, которое равно количеству пересекающихся дорог" не корректно, т.к. дорог везде пересекается 2. Скорее всего имелось ввиду "сколько дорог сходится в этой точке". Вот. А по поводу решения ) Очень хотелось решить. Пришлось вспоминать аж 3ий курс института ) Даже вспомнил что это задача комивояжера. Что нужно составить граф, затем матрицу расстояний..... А вот дальше.... Выяснилось, что в суть самого алгоритма нас так и не погрузили. Что понятно, т.к. ВУЗ строительный а не IT. Но обидно ( Т.е. нас научили составлять результирующий граф, матрицу для расчета, а дальше.... Забить полученные данные в программу trasal.exe =( В общем облом.
_______
А что с сайтом было? Я ночью 2 часа пробиться не мог! =(

______
>А что с сайтом было? Я ночью 2 часа пробиться не мог! =(

А у мастерхоста чего-то по ночам трындец часто бывает... С чем связано не знаю. У самого такое же.

> А у мастерхоста чего-то по ночам трындец часто бывает...
Ааа.... А то я уж подумал опять какой-то школьник ломает )

>> А у мастерхоста чего-то по ночам трындец часто бывает...
>Ааа.... А то я уж подумал опять какой-то школьник ломает )

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

Теория Графов меня преследует :) Надо поскорее сдать этот зачёт...
Но вообще интересно, надо будет посмотреть...