Необходимо написать точно такую же прогу file.qip.ru/file/LiW3B1Iu... Обучающая программа на нахождение кратчайшего пути.
Как именно ей пользоваться написано в окне правом верхнем углу. Теперь как искать путь. Возьмем к примеру вот такой график из первого примера отсюда ru.wikipedia.org/wiki/%D0... Предположим, что тот кружочек, где цифра 5-начало, где 1-конец. В нашей задачи, цифр в кружочках нет, мы должны их проставить сами, те цифры, что надо дугами-называются весами. Итак, движение осуществляется от конца к началу, смотрим как добраться до кружочка где внутри стоит 3, можно со стороны где 9, а можно где 6, но, мы выбираем тот путь где сумма весов меньше, т.е. 9+2=11, а 6+11=17 значит в кружочке где 3 пишем 11, т.к. оно наименьшее, дальше, где кружочек с номером 2 там либо 5+15=21 либо опять 11+10= 21, ставим где кружосчек 2- 21, до кружочка где 1 мы можем добраться двумя способами: из 3 в первый, 11+9=20 и из второго 21+7=28, В КРУЖОЧКЕ где 1 выбираем наименьшее, т.е. 20, кратчайший путь найден. Таким способом должны быть заполнены все кружочки графика.
Бюджет: т.к. я студентка 300 руб.
Среда, желательно билдер или плюсы..
Опубликован 25.05.2011 в 19:11