основы_программирования_на_языке_python. Министерство образования и науки российской федерации федеральное государственное бюджетное образовательное учреждение высшего
 Скачать 208.8 Kb.
|
|
Задача 35: Без трех единиц подряд Ограничение по времени работы программы: 1 секунда По данному натуральному n определите число двоичных последовательностей длины n, не содержащих трех единиц подряд. ВХОДНЫЕ ДАННЫЕ Программа получает на вход число n<30. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести число искомых последовательностей. ПРИМЕР
РЕШЕНИЕ Решим задачу методом динамического программирования. Целевая функция: F(k,n) - количество искомых последовательностей длины n, заканчивающихся на k единиц (0≤k≤2). Рекуррентные соотношения: F(0,n)=F(0,n−1)+F(1,n−1)+F(2,n−1), F(1,n)=F(0,n−1), F(2,n)=F(1,n−1). Начальные значения - F(0,1)=1, F(1,1)=1. n = int(input()) F = [[0] * (n + 1) for i in range(3)] F[0][1] = 1 F[1][1] = 1 for i in range(2, n + 1): F[0][i] = F[0][i - 1] + F[1][i - 1] + F[2][i - 1] F[1][i] = F[0][i - 1] F[2][i] = F[1][i - 1] print(F[0][n] + F[1][n] + F[2][n]) Задача 36: Без двух единиц и двух двоек подряд Ограничение по времени работы программы: 1 секунда По данному натуральному n определите число последовательностей длины n, составленных из чисел 0, 1 и 2, не содержащих двух единиц и двух двоек подряд (нулей подряд может быть сколько угодно). ВХОДНЫЕ ДАННЫЕ Программа получает на вход число n<24. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести число искомых последовательностей. ПРИМЕР
РЕШЕНИЕ Решим задачу методом динамического программирования. Целевая функция: F(k,n) - количество искомых последовательностей длины n, заканчивающихся на символ k (0≤k≤2). Рекуррентные соотношения: F(0,n)=F(0,n−1)+F(1,n−1)+F(2,n−1), F(1,n)=F(0,n−1)+F(2,n−1), F(2,n)=F(0,n−1)+F(1,n−1). Начальные значения - F(0,1)=1, F(1,1)=1, F(2,1)=1. n = int(input()) F = [[0] * (n + 1) for i in range(3)] F[0][1] = 1 F[1][1] = 1 F[2][1] = 1 for i in range(2, n + 1): F[0][i] = F[0][i - 1] + F[1][i - 1] + F[2][i - 1] F[1][i] = F[0][i - 1] + F[2][i - 1] F[2][i] = F[0][i - 1] + F[1][i - 1] print(F[0][n] + F[1][n] + F[2][n]) Задача 37: Проверка корректности кучи Ограничение по времени работы программы: 1 секунда Дан список чисел. Проверьте, является ли он корректно организованной кучей, в вершине которой находится наибольший элемент. ВХОДНЫЕ ДАННЫЕ Первая строка входных данных содержит натуральное число n≤10000. Вторая строка содержит n-натуральных чисел, не превосходящих 109 каждое. ВЫХОДНЫЕ ДАННЫЕ Если данные числа записаны в порядке, образующим корректную кучу, программа должна вывести слово "YES", иначе программа должна вывести слово "NO". ПРИМЕР
РЕШЕНИЕ Добавил для удобства индексации в начало списка фиктивный элемент, тогда элементы списка будут иметь индексы от 1 до n. Пройдем по всем элементами списка начиная с элемента 2 до элемента n. Родителем i-го элемента будет элемент с индексом i//2. Если текущий элемент оказался больше своего родителя, то выведем NO, если же таких элементов не обнаружено, то выведем YES. n = int(input()) A = ["#"] + list(map(int, input().split())) for i in range(2, n + 1): if A[i] > A[i // 2]: print("NO") break else: print("YES") Задача 38: Создание кучи Ограничение по времени работы программы: 1 секунда Дан список чисел. Создайте из него кучу, то есть переставьте элементы списка так, чтобы они образовывали правильную кучу (в начале кучи стоит наибольший элемент). ВХОДНЫЕ ДАННЫЕ Первая строка входных данных содержит натуральное число n≤10000. Вторая строка содержит nнатуральных чисел, не превосходящих 109 каждое. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести данные числа в порядке, соответствующем корректной куче. Нужно вывести только один (любой) из возможных порядков. ПРИМЕР
РЕШЕНИЕ Сформируем новый список (кучу), затем будем добавлять в него по одному данные числа. В конце выведем весь список. Новый элемент добавляется в конец кучи, затем выполняется "подъем" исходного элемента вверх. def add(Heap, elem): Heap.append(elem) i = len(Heap) - 1 while i > 1 and Heap[i // 2] < elem: Heap[i] = Heap[i // 2] i //= 2 Heap[i] = elem n = int(input()) H = ["#"] for elem in map(int, input().split()): add(H, elem) print(" ".join(map(str, H[1:]))) Задача 39: От списков смежности к матрице смежности Ограничение по времени работы программы: 1 секунда Постройте матрицу смежности по заданным спискам смежности. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных содержится число N - количество вершин (1≤N≤100). Далее идут N строк. В i-й строке содержится описание всех ребер, исходящих из i-й вершины. Описание начинается количеством исходящих ребер. Далее следуют номера вершин, в которые эти ребра идут. Все вершины нумеруются натуральными числами от 1 до N. ВЫХОДНЫЕ ДАННЫЕ Выведите N строк, содержащих по N чисел, равных 0 или 1, разделенных пробелами — матрицу смежности данного ориентированного графа. ПРИМЕР
РЕШЕНИЕ Будем считывать списки смежности по одному, строя матрицу смежности. Для каждого значения j из списка смежности i-й вершины необходимо сделать пометку A[i][j] = 1. Удобно вычитать из номеров вершины число 1 сразу же при построении матрицы смежности. n = int(input()) A = [[0] * n for i in range(n)] for i in range(n): for j in list(map(int, input().split()))[1:]: A[i][j - 1] = 1 for line in A: print(" ".join(map(str, line))) Задача 40: От матрицы смежности к спискам смежности Ограничение по времени работы программы: 1 секунда Простой ориентированный граф задан матрицей смежности. Выведите его представление в виде списков смежности. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных находится число N — количество вершин графа (1≤N≤100). Далее идет N строк по N чисел в каждой, равных 0 или 1, содержащих матрицу смежности ориентированного графа из N вершин. ВЫХОДНЫЕ ДАННЫЕ Выведите N строк — списки смежности графа. В i-й строке сначала выведите количество исходящих из i-й вершины ребер, а затем — номера вершин, в которые эти ребра идут, упорядоченные по возрастанию. Нумерация вершин начинается с числа 1. ПРИМЕР
РЕШЕНИЕ Сначала считайте матрицу смежности, потом постройте списки смежности по очереди для всех вершин. Список смежности для вершины i состоит из таких j, что A[i][j] == 1. n = int(input()) A = [None] for i in range(n): A.append([0] + list(map(int, input().split()))) for i in range(1, n + 1): V = [] for j in range(1, n + 1): if A[i][j] == 1: V.append(j) print(len(V), " ".join(map(str, V))) Задача 41: Компоненты связности Ограничение по времени работы программы: 1 секунда Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности. ВХОДНЫЕ ДАННЫЕ В первой строке входного файла содержится одно натуральное число N (N≤100) — количество вершин в графе. Далее в N строках по N чисел — матрица смежности графа: в i-й строке на j-м месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали. ВЫХОДНЫЕ ДАННЫЕ Вывести одно целое число — количество компонент связности данного графа. ПРИМЕР
РЕШЕНИЕ Граф задан матрицей смежности, поэтому нужно использовать поиск в глубину на матрице смежности - в функции DFS перебирать все вершины и проверять, соединены ли две вершины ребром. n = int(input()) A = [] Visited = [False] * n for i in range(n): A.append([int(x) for x in input().split()]) def DFS(v): Visited[v] = 1 for i in range(n): if A[v][i] == 1 and not Visited[i]: DFS(i) Ans = 0 for i in range(n): if not Visited[i]: Ans += 1 DFS(i) print(Ans) Задача 42: Дерево Ограничение по времени работы программы: 1 секунда Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных содержится одно натуральное число N (N≤100) - количество вершин в графе. Далее в N строках по N чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести YES, если граф является деревом, NO иначе. ПРИМЕР
РЕШЕНИЕ Для проверки того, что граф - дерево, можно проверить, что он связный и содержит N−1 ребро. Для проверки связности графа запустим DFS из первой вершины - в результате должны быть посещены все вершины графа. В конце выводим NO, если граф содержит не N−1 ребро или если после запуска DFS осталась не посещённая вершина, иначе выводим YES. n = int(input()) A = [] Visited = [False] * n for i in range(n): A.append([int(x) for x in input().split()]) def DFS(v): Visited[v] = 1 for i in range(n): if A[v][i] == 1 and not Visited[i]: DFS(i) Edges = 0 for i in range(n): for j in range(i): Edges += A[i][j] DFS(0) if Edges != n - 1 or (False in Visited): print("NO") else: print("YES") Задача 43: Дейкстра Ограничение по времени работы программы: 1 секунда Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой. ВХОДНЫЕ ДАННЫЕ В первой строке содержатся три числа: N, S и F (1≤N≤100, 1≤S,F≤N), где N — количество вершин графа, S — начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100 — матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы записаны нули. ВЫХОДНЫЕ ДАННЫЕ Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует. ПРИМЕР
РЕШЕНИЕ Найдем кратчайшее расстояние при помощи алгоритма Дейкстры. Обратите внимание, что отсутствие ребра между вершинами i и j задается числом -1, при релаксации ребра i-j нужно проверить дополнительное условие W[i][j] != -1. При отсутствии пути также необходимо выводить значение -1, а не INF. N, S, F = map(int, input().split()) S -= 1 F -= 1 W = [] for i in range(N): W.append(list(map(int, input().split()))) INF = 10 ** 10 D = [INF] * N D[S] = 0 Colored = [False] * N while True: min_dist = INF for i in range(N): if not Colored[i] and D[i] < min_dist: min_dist = D[i] min_vertex = i if min_dist == INF: break i = min_vertex Colored[i] = True for j in range(N): if D[i] + W[i][j] < D[j] and W[i][j] != -1: D[j] = D[i] + W[i][j] if D[F] == INF: print(-1) else: print(D[F]) Задача 44: Кратчайший путь Ограничение по времени работы программы: 1 секунда Ориентированный взвешенный граф задан так же, как в предыдущей задаче. Найдите кратчайший путь из вершины S в вершину F. ВХОДНЫЕ ДАННЫЕ В первой строке содержатся три числа: N, S и F (1≤N≤100, 1≤S,F≤N), где N — количество вершин графа, S — начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100 — матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы записаны нули. ВЫХОДНЫЕ ДАННЫЕ Требуется вывести последовательно все вершины одного (любого) из кратчайших путей, или одно число -1, если пути между указанными вершинами не существует. ПРИМЕР
РЕШЕНИЕ Для восстановления ответа необходимо хранить для каждой вершины ее предка в отдельном списке Prev. После завершения алгоритма Дейкстры либо выводится число -1, если путь не найден, либо необходимо идти от каждой вершины к ее предшественнику, восстанавливая путь «с конца». В этом решении в алгоритме Дейкстры вершины нумеруются с нуля, поэтому при считывании вершин из значений S и F нужно вычесть 1, а при выводе результата к каждой вершине добавить 1. N, S, F = map(int, input().split()) S -= 1 F -= 1 W = [] for i in range(N): W.append(list(map(int, input().split()))) INF = 10 ** 10 D = [INF] * N D[S] = 0 Colored = [False] * N Prev = [None] * N while True: min_dist = INF for i in range(N): if not Colored[i] and D[i] < min_dist: min_dist = D[i] min_vertex = i if min_dist == INF: break i = min_vertex Colored[i] = True for j in range(N): if D[i] + W[i][j] < D[j] and W[i][j] != -1: D[j] = D[i] + W[i][j] Prev[j] = i if D[F] == INF: print(-1) else: Path = [] while F is not None: Path.append(F + 1) F = Prev[F] print(" ".join(map(str, Path[::-1]))) |