Информатика | ОГЭ | ЕГЭ | Жизнь, кофе и ЕГЭ по информатике

+1

Продолжим разговор о теории графов и рассмотрим один из самых известных алгоритмов. Алгоритм Дейкстры используется для нахождения кратчайших путей от одной вершины до всех остальных в ориентированном взвешенном графе, при условии, что все ребра в графе имеют неотрицательные веса. Алгоритм Дейкстры относится к так называемым «жадным» алгоритмам. Это значит, что он на каждом шаге принимает локально наилучшее (оптимальное) решение в надежде, что итоговое глобальное решение тоже окажется верным и оптимальным. В алгоритме Дейкстры есть условно неокрашенные и окрашенные вершины. Изначально все вершины неокрашенные. Если алгоритм Дейкстры покрасил вершину, то это означает, что найденное значение является кратчайшим расстоянием от начальной вершины до данной, оно уже не будет улучшаться. Если ж…

Маленькие приятности от коллег - это мои утренние чудеса 😍 Как хорошо, когда в офисе ждут не только задачи, но и улыбки, общение, кофе и друзья. Всем лёгкой недели и приятных сюрпризов!

+1

В демо-версии ЕГЭ 2027 появился новый прототип на графы. По сути, это задача на поиск кратчайшего пути от одной вершины графа до другой. Входные данные представлены файлом, в каждой строке которого три числа: целочисленные вершины и дробный вес ребра между этими вершинами. Разберем задачу из демо-версии, для решения используем алгоритм Беллмана-Форда. Да, он медленнее Дейкстры, но зато простой и понятный и работает даже с отрицательными весами. Алгоритм Беллмана-Форда находит в ориентированном графе кратчайшие пути из одной вершины до всех остальных.  Алгоритм начинается с инициализации: в самом начале мы задаем расстояние от исходной вершины до самой себя равным нулю, а до всех остальных вершин — бесконечности. Это необходимо для того, чтобы потом производить расчеты, основываясь на э…

Сегодня нашла этот старый, но по-своему прекрасный ребус. Он как бы намекает, что на выходных надо порешать задачку № 7 😁

В программировании, как и в математике, существует два основных вида чисел: 🔸 целые числа - это числа без дробной части: -3, 0, 71 🔸 вещественные числа (с плавающей точкой) - это числа с дробной частью: 3.14, -7.25, 2.0, 0.5 В python для записи дробей используется именно точка, а не запятая. При этом число, записанное с точкой, будет храниться как вещественное, даже если его дробная часть равна нулю: 5.0, -7.0, 0.0 #python #репетитор

Фото