основы_программирования_на_языке_python. Министерство образования и науки российской федерации федеральное государственное бюджетное образовательное учреждение высшего
 Скачать 208.8 Kb.
|
|
Задача 45: Простой Флойд Ограничение по времени работы программы: 5 секунд Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса. ВХОДНЫЕ ДАННЫЕ В первой строке вводится единственное число N (1≤N≤100) – количество вершин графа. В следующих N строках по N чисел задается матрица смежности графа (j-е число в i-й строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы стоят нули. ВЫХОДНЫЕ ДАННЫЕ Выведите N строк по N чисел – матрицу кратчайших расстояний между парами вершин. j-е число в i-й строке должно быть равно весу кратчайшего пути из вершины i в вершину j. ПРИМЕР
РЕШЕНИЕ Сначала нужно считать матрицу смежности, потом реализовать алгоритм Флойда и вывести полученную матрицу кратчайших путей. n = int(input()) A = [list(map(int, input().split())) for i in range(n)] for k in range(n): for i in range(n): for j in range(n): A[i][j] = min(A[i][j], A[i][k] + A[k][j]) for line in A: print(" ".join(map(str, line))) Задача 46: Форд-Беллман Ограничение по времени работы программы: 3 секунды Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют. Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных записано число N (1≤N≤100) – количество вершин графа и число M (0≤M≤10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100). ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000. ПРИМЕР
РЕШЕНИЕ Необходимо реализовать алгоритм Форда-Беллмана. При этом если для какой-то вершины i значение расстояния D[i] было равно INF, то оно может уменьшиться, например, в результате релаксации ребра отрицательного веса. Поэтому при релаксации будем проверять, что расстояние до вершины, являющейся началом ребра, не равно INF. import sys N, M = map(int, input().split()) INF = 30000 D = [INF] * (N + 1) D[1] = 0 Edges = [] for i in range(M): Edges.append(list(map(int, input().split()))) for i in range(N - 1): for start, end, weight in Edges: if D[start] != INF and D[start] + weight < D[end]: D[end] = D[start] + weight print(" ".join(map(str, D[1:]))) Задача 47: Минимальное остовное дерево Ограничение по времени работы программы: 1 секунда Дан неориентированный взвешенный граф без кратных рёбер с N вершинами и M рёбрами, требуется найти каркас минимального веса. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных записаны числа N (1≤N≤100) и M. В следующих M строках идёт описание рёбер графа. Каждое ребро задаётся тремя числами. Первые два числа — номера вершин, соединённых этим ребром, третье число — вес ребра. Все веса рёбер положительны и не превосходят 10000. ВЫХОДНЫЕ ДАННЫЕ Если каркас минимального веса существует, то нужно выведите его вес в первой строке, а в следующих N−1 строках вывести номера ребер, которые составляют минимальное остовное дерево. Если каркаса минимального веса не существует, выведите число -1. Вершины и ребра графа нумеруются начиная с 1. ПРИМЕР
РЕШЕНИЕ Используем алгоритм Краскала. При считывании ребра помимо номеров начала и конца ребра и его веса сохраняем его номер. При добавлении ребра к каркасу номер ребра добавляем к списку, в котором хранится ответ. Если после окончания алгоритма в списке меньше, чем N−1 ребро, значит, исходный граф был несвязным и каркаса не существует, иначе выведем сначала суммарный вес каркаса а затем номера ребер, вошедших в каркас. N, M = map(int, input().split()) Edges = [] for i in range(M): start, end, weight = map(int, input().split()) Edges.append([weight, start - 1, end - 1, i + 1]) Edges.sort() Comp = [i for i in range(N)] Ans_len = 0 Ans = [] for weight, start, end, num in Edges: if Comp[start] != Comp[end]: Ans_len += weight Ans.append(num) a = Comp[start] b = Comp[end] for i in range(N): if Comp[i] == b: Comp[i] = a if len(Ans) != N - 1: print(-1) else: print(Ans_len) print(" ".join(map(str, Ans))) Задача 48: Длина отрезка Ограничение по времени работы программы: 1 секунда Даны две точки A и B. Вычислите длину отрезка AB. ВХОДНЫЕ ДАННЫЕ В первой строке записаны координаты точки A через пробел, во второй строке — координаты точки Bчерез пробел. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно число — длину отрезка AB. ПРИМЕР
РЕШЕНИЕ Расстояние между двумя точками A1(x1,y1) и A2(x2,y2) равно √(x2−x1)2+(y2−y1)2. x1, y1 = map(float, input().split()) x2, y2 = map(float, input().split()) print(((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5) Задача 49: Полярный угол Ограничение по времени работы программы: 1 секунда Вычислите полярный угол данной точки. ВХОДНЫЕ ДАННЫЕ Даны два действительных числа – координаты точки, не совпадающей с началом координат. ВЫХОДНЫЕ ДАННЫЕ Выведите полярный угол данной точки в радианах (число на интервале [0,2π)). ПРИМЕР
РЕШЕНИЕ Необходимо использовать функцию atan2(y, x). Функция atan2 возвращает ответ на интервале (−π.π], а необходимо вывести ответ на интервале [0,2π), поэтому к отрицательным углам необходимо прибавить 2π. import math x, y = map(float, input().split()) phi = math.atan2(y, x) if phi < 0: phi += 2 * math.pi print(phi) Задача 50: Классификация векторов Ограничение по времени работы программы: 1 секунда Даны два вектора. Определите, являются ли они коллинеарными (параллельными), перпендикулярными или имеют общее положение. ВХОДНЫЕ ДАННЫЕ В двух строках записаны координаты двух ненулевых векторов (два целых числа в каждой строке через пробел). ВЫХОДНЫЕ ДАННЫЕ Если данные вектора коллинеарны, выведите 1. Если вектора перпендикулярны, выведите 2. Иначе выведите 0. ПРИМЕР
РЕШЕНИЕ Нужно вывести 1, если векторное произведение данных векторов равно 0, нужно вывести 2, если скалярное произведение векторов равно 0 и вывести 0 в остальных случаях. В приведенном ниже решении для экономии места не приведена реализация классов Point и Vector. v1 = Vector(input()) v2 = Vector(input()) if v1.CrossProduct(v2) == 0: print(1) elif v1.DotProduct(v2) == 0: print(2) else: print(0) Задача 51: Принадлежит ли точка отрезку Ограничение по времени работы программы: 1 секунда Определите, принадлежит ли точка данному отрезку. ВХОДНЫЕ ДАННЫЕ Программа получает на вход шесть чисел: координаты точки P и координаты концов отрезка AB. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести YES, если точка принадлежит отрезку, или NO в противном случае. ПРИМЕР
РЕШЕНИЕ Условия принадлежности точки P отрезку AB: [AP,AB]=0, (AB,AP)≥0, (BA,BP)≥0. В приведенном ниже решении для экономии места не приведена реализация классов Point и Vector. P = Point(input()) A = Point(input()) B = Point(input()) AB = Vector(A, B) BA = Vector(B, A) AP = Vector(A, P) BP = Vector(B, P) if AB.CrossProduct(AP) == 0 and AB.DotProduct(AP) >= 0 and BA.DotProduct(BP) >= 0: print("YES") else: print("NO") Задача 52: Основание перпендикуляра Ограничение по времени работы программы: 1 секунда Найдите основание перпендикуляра, опущенного из данной точки на прямую, заданную уравнением. ВХОДНЫЕ ДАННЫЕ В первой строке записано два числа — координаты точки. Во второй строке записано три числа — коэффициенты уравнения прямой. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести два действительных числа: координаты основания перпендикуляра, опущенного из данной точки на данную прямую ПРИМЕР
РЕШЕНИЕ Необходимо взять вектор нормали к прямой, пронормировать его (т. е. сделать его единичной длины, поделив на длину вектора), умножить на расстояние от точки до прямой, умножить на -1 и отложить от данной точки полученный вектор. В приведенном ниже решении для экономии места не приведена реализация классов Point и Vector. P = Point(input()) A, B, C = map(int, input().split()) n = Vector(A, B) n = n / n.len() n = n * (A * P.x + B * P.y + C) / math.hypot(A, B) n = n * (-1) print(P + n) Задача 53: Поворот прямой Ограничение по времени работы программы: 1 секунда Дана прямая, заданная уравнением, и значение угла поворота. Постройте прямую, полученную из данной прямой поворотом на данный угол. ВХОДНЫЕ ДАННЫЕ Даны четыре числа: коэффициенты нормального уравнения прямой (в первой строке) и угол (в радианах, задан в виде действительного числа) во второй строке. ВЫХОДНЫЕ ДАННЫЕ Выведите три числа: коэффициенты нормального уравнения прямой, полученной поворотом данной прямой вокруг начала координат на данный угол в положительном направлении. Можно вывести любое из возможных уравнений прямой. Значения выводимых действительных чисел могут незначительно отличаться от правильных (например, можно выводить 0.9999999999999999 вместо 1.0). ПРИМЕР
РЕШЕНИЕ При повороте прямой вектор нормали поворачивается на заданный угол, а свободный член уравнения, задающий расстояние от начала координат до прямой, не меняется. from math import * a, b, c = map(float, input().split()) phi = float(input()) a, b = a * cos(phi) - b * sin(phi), a * sin(phi) + b * cos(phi) print(a, b, c) Задача 54: Площадь многоугольника Ограничение по времени работы программы: 1 секунда На плоскости задан многоугольник координатами вершин в порядке их обхода. Многоугольник не обязательно выпуклый. Найдите площадь данного многоугольника. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных записано количество вершин многоугольника N (3≤N≤100). В следующих N строчках записаны координаты вершин многоугольника (по два вещественных числа в одной строке). ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно вещественное число -— площадь многоугольника. ПРИМЕР
РЕШЕНИЕ Площадь многоугольника вычисляется по формуле SP0P1…PN−1=|SOP0P1+SOP1P2+…+SOPN−1P0|, где SOAB=12[OA,OA] - ориентированная площадь треугольника OAB. n = int(input()) P = [] for i in range(n): P.append(tuple(map(float, input().split()))) S = 0 for i in range(n): x1 = P[i][0] y1 = P[i][1] x2 = P[(i + 1) % n][0] y2 = P[(i + 1) % n][1] S += x1 * y2 - x2 * y1 print(abs(S) / 2) Задача 55: Выпуклость многоугольника Ограничение по времени работы программы: 3 секунды На плоскости задан многоугольник координатами вершин в порядке их обхода. Проверьте, является ли он выпуклым. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных записано количество вершин многоугольника N (3≤N≤100000). В следующих N строчках записаны координаты вершин многоугольника (по два целых числа в одной строке). Возможно, что три и более соседних вершин в порядке обхода лежат на одной прямой (то есть одна сторона многоугольника является продолжением другой стороны). ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести слово YES, если многоугольник является выпуклыми и слово NO, в противном случае. ПРИМЕР
РЕШЕНИЕ Считав многоугольник, пройдем по всем парам соседних сторон (не забывая про зацикливание) и посмотрим на знаки векторного произведения [PiPi+1,Pi+1Pi+2],. Будем отмечать, какие по знаку векторные произведения встречались: положительные (переменная PosAngle) и отрицательные (переменная NegAngle), нулевые произведения игнорируются. Если после просмотра всех пар соседних сторон встретились как положительные, так и отрицательные векторные произведения, то многоугольник не является выпуклым и программа выводит NO, иначе программа выводит YES. n = int(input()) P = [] for i in range(n): P.append(tuple(map(float, input().split()))) PosAngle = False NegAngle = False for i in range(n): x1 = P[i][0] y1 = P[i][1] x2 = P[(i + 1) % n][0] y2 = P[(i + 1) % n][1] x3 = P[(i + 2) % n][0] y3 = P[(i + 2) % n][1] d = (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2) if d > 0: PosAngle = True elif d < 0: NegAngle = True if PosAngle and NegAngle: print("NO") else: print("YES") |