основы_программирования_на_языке_python. Министерство образования и науки российской федерации федеральное государственное бюджетное образовательное учреждение высшего
 Скачать 208.8 Kb.
|
|
Задача 16: Медиана списка Ограничение по времени работы программы: 1 секунда Дан список целых чисел. Найдите в нем “медианный” элемент, то есть то число, которое будет ровно посередине списка, если список отсортировать. ВХОДНЫЕ ДАННЫЕ Программа получает на вход n целых чисел, записанных через пробел в одной строке, 1≤n≤100, значение n — нечетное. Сами числа по модулю не превосходят 109 ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно число — медианный элемент данного списка. ПРИМЕР
РЕШЕНИЕ Считаем файл, создадим список из считанных чисел. Отсортируем его при помощи любого из алгоритмов сортировки. Выведем элемент с индексом n//2. def InsertionSort(A): for i in range(1, len(A)): new_elem = A[i] j = i - 1 while j >= 0 and A[j] > new_elem: A[j + 1] = A[j] j -= 1 A[j + 1] = new_elem A = list(map(int, input().split())) InsertionSort(A) print(A[len(A) // 2]) Задача 17: Постфиксная запись Ограничение по времени работы программы: 1 секунда В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A+B записывается как «A B + ». Запись «B C + D * » обозначает привычное нам (B+C)*D, а запись «A B C + D * + » означает A+(B+C)*D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения. Дано выражение в обратной польской записи. Определите его значение. ВХОДНЫЕ ДАННЫЕ В единственной строке записано выражение в постфиксной записи, содержащее однозначные числа и операции +, −, *. Строка содержит не более 100 чисел и операций. ВЫХОДНЫЕ ДАННЫЕ Необходимо вывести значение записанного выражения. Гарантируется, что результат выражения, а также результаты всех промежуточных вычислений по модулю меньше 231. ПРИМЕР
РЕШЕНИЕ Обратная польская запись — это по сути последовательность действий над стеком. Заведем стек. Считываем входные данные. Если очередной элемент — это число (символ от «0» до «9»), то добавим его в стек. Если это операция — то извлечем из стека два последних элемента, применим к ним данную операцию и положим результат в стек. В конце выведем единственное число, которое будет находиться в стеке. stack = [] for elem in input().split(): if elem in '+-*': a = stack[-2] b = stack[-1] stack.pop() stack.pop() if elem == '+': result = a + b elif elem == '-': result = a - b else: result = a * b stack.append(result) else: stack.append(int(elem)) print(stack[0]) Задача 18: Правильная скобочная последовательность Ограничение по времени работы программы: 1 секунда Требуется определить, является ли правильной данная последовательность круглых, квадратных и фигурных скобок. ВХОДНЫЕ ДАННЫЕ В единственной строке входных данных записано подряд N скобок (1≤N≤105). ВЫХОДНЫЕ ДАННЫЕ Выведите «YES», если данная последовательность является правильной, и «NO» в противном случае. ПРИМЕР
РЕШЕНИЕ Задача решается с использованием стека. Заведем стек. Открывающиеся скобки кладем в стек. Если встречается закрывающаяся скобка, то проверяем, соответствует ли она скобке на вершине стека, если соответствует — удалим из стека верхнюю скобку, если нет — то последовательность неправильная. В конце работы алгоритма стек должен остаться пустым. Типичные ошибки: 1. При удалении скобки из стека не проверяется, что стек не пуст. 2. Не проверяется, что в конце работы алгоритма стек пуст. 3. Неправильная проверка скобок на парность (это удобно сделать отдельной функцией IsPair). import sys import sys Stack = [] def IsPair(left, right): return left + right in ["()", "[]", "{}"] for bracket in input(): if bracket in '([{': Stack.append(bracket) else: if len(Stack) == 0: print("NO") sys.exit(0) if not IsPair(Stack.pop(), bracket): print("NO") sys.exit(0) if len(Stack) == 0: print('YES') else: print('NO') Задача 19: Личные дела Ограничение по времени работы программы: 1 секунда Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных записано число N (1≤N≤1000) – количество личных дел. Далее записано N строк, каждая из которых состоит из фамилии учащегося (строка без пробелов) и номера класса (целое число от 1 до 11). ВЫХОДНЫЕ ДАННЫЕ Нужно вывести список всех учащихся, сначала выводя номер класса, затем — фамилию учащегося. Список должен быть отсортирован по классу, а затем по фамилии. ПРИМЕР
РЕШЕНИЕ Необходимо отсортировать личные дела, которые представляют собой пару из класса и фамилии. Удобно так и хранить информацию о личных делах — в виде кортежа из двух элементов. Если создать список, элементами которого будут кортежи из номера класса и фамилии, то стандартная сортировка их отсортирует правильно. Кортежи сравниваются в лексикографическом порядке — то есть сначала по первому полю, а если они равны — то по второму полю и т. д. n = int(input()) A = [] for i in range(n): name, form = input().split() A.append( (int(form), name) ) A.sort() for elem in A: print(elem[0], elem[1]) Задача 20: Скидки Ограничение по времени работы программы: 1 секунда В супермаркете проводится беспрецедентная акция — “Покупая два любых товара, третий получаешь бесплатно*”, а внизу мелким шрифтом приписано “* - из трех выбранных вами товаров оплачиваются два наиболее дорогих”. Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят. Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров. ВХОДНЫЕ ДАННЫЕ Программа получает на вход число N (1≤N≤1000), а затем N чисел — стоимости выбранных Васей товаров. Все стоимости — натуральные числа, не превышающие 10000. ВЫХОДНЫЕ ДАННЫЕ Выведите одно число — сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную). ПРИМЕР
РЕШЕНИЕ Сначала отсортируем список всех товаров, которые хочет приобрести Вася. Теперь будем выбирать товары в порядке убывания стоимости. Два самых дорогих товара Вася должен приобрести, после чего третий по стоимости товар он получит бесплатно. Далее продолжим, пока не будут перебраны все товары. В приведенном ниже решении используются срезы для выбора тех товаров, которые оплатит Вася. n = int(input()) A = list(map(int, input().split())) A.sort(reverse=True) print(sum(A[::3]) + sum(A[1::3])) Задача 21: Двоичный поиск Ограничение по времени работы программы: 2 секунды Даны два списка чисел. В первом списке содержится N чисел, отсортированных по не убыванию. Во втором списке находится M других чисел. Для каждого числа из второго списка найдите его первое и последнее вхождение в первый список. ВХОДНЫЕ ДАННЫЕ В первой строке входных данных записано N упорядоченных по не убыванию целых неотрицательных чисел — элементы первого списка. Во второй строке записаны M целых неотрицательных чисел. Количество чисел в каждом списке не превосходит 20.000. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести индекс его первого и последнего вхождения в первый список. Если число не входит в первый список, нужно вывести одно число −1. ПРИМЕР
РЕШЕНИЕ Считаем первый список A. Переберем в переменной key все элементы второго списка. Для каждого элемента key второго списка вызовем функции UpperBound и LowerBound, запишем их результат в переменные upper и lower. Проверим, есть ли элемент key в списке A (например, по условию lower < len(A) and A[lower] == key). Если есть — выведем lower и upper - 1, иначе выведем -1. def UpperBound(A, key): left = -1 right = len(A) while right - left > 1: middle = (left + right) // 2 if A[middle] <= key: left = middle else: right = middle return right def LowerBound(A, key): left = -1 right = len(A) while right - left > 1: middle = (left + right) // 2 if A[middle] < key: left = middle else: right = middle return right A = list(map(int, input().split())) for key in input().split(): key = int(key) lower = LowerBound(A, key) upper = UpperBound(A, key) if lower < len(A) and A[lower] == key: print(lower, upper - 1) else: print(-1) Задача 22: Корень кубического уравнения Ограничение по времени работы программы: 1 секунда Дано кубическое уравнение ax3+bx2+cx+d=0 (a≠0). Известно, что у этого уравнения ровно один корень. Требуется его найти с точностью до 10−4. ВХОДНЫЕ ДАННЫЕ Программа получает на вход четыре целых числа a, b, c, d, по модулю не превосходящие 1000, a≠0. Числа записаны в одной строке через пробел. ВЫХОДНЫЕ ДАННЫЕ Выведите единственный корень уравнения с точностью до 10−4 (то есть ваш ответ должен отличаться от правильного не больше, чем на 10−4). ПРИМЕР
РЕШЕНИЕ Будем использовать вещественный двоичный поиск — рассмотрим интервал, на концах которого функция имеет разные знаки, будем сокращать интервал в два раза, пока его длина не станет меньше, чем 10−4. Необходимо правильно изолировать корни — выбрать начальный интервал так, чтобы значение функции было разных знаков на концах этого интервала. В качестве такого интервала можно взять [−2000,2000]. Также необходимо рассмотреть два случая - a>0 и a<0. Они отличаются знаками функции на концах интервала. Проще всего свести второй случай к первому, умножив все коэффициенты на -1. EPS = 0.0000001 def f(x): return a * x ** 3 + b * x ** 2 + c * x + d def root(): left = -2000 right = 2000 while right - left > EPS : middle = (right + left) / 2 if f(middle) > 0: right = middle else : left = middle return (left + right) / 2 a, b, c, d = map(float, input().split()) if a < 0: a = -a b = -b c = -c d = -d print(root()) Задача 23: k-кузнечик Ограничение по времени работы программы: 1 секунда Кузнечик умеет прыгать на расстояние 1, 2, … , k клеток (то есть длина прыжка кузнечика не превышает k). Определите, каким числом способов кузнечик может попасть из точки 0 в точку n. ВХОДНЫЕ ДАННЫЕ Программа получает на вход два числа, записанных в одной строке — n и k (0≤n≤30, 1≤k≤10). ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно число — искомое количество способов. ПРИМЕР
РЕШЕНИЕ Воспользуемся динамическим программированием. Целевая функция: F(i) — количество способов попасть в точку номер i. Рекуррентное соотношение: F[i]=F[i−k]+F[i−k+1]+…+F[i−1]. Начальное значение - F[0]=0. Необходимо также аккуратно обработать случай вычисления F(i), когда i n, k = map(int, input().split()) F = [0 ] * (n + 1) F[0 ] = 1 for i in range(1, n + 1): F[i] = sum(F[max(0, i - k):i]) print(F[n]) Задача 24: Калькулятор Ограничение по времени работы программы: 4 секунды Исполнитель «Калькулятор» может с заданным числом X выполнить одну из трех операций и получить новое число. Возможные операции: Прибавить к числу X единицу. Умножить число X на 2. Умножить число X на 3. Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно число N, не превосходящее 106. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно число — наименьшее количество операций, необходимых для получения из числа 1 числа N. ПРИМЕР
РЕШЕНИЕ Решим задачу методом динамического программирования. Целевая функция: F(i) — наименьшее число операций, при помощи которых можно получить число i. Число i можно получить за одну операцию из числа i−1, i/2 (для языка Pascal i div 2) (если i делится на 2) и i/3 (для языка Pascal i div 2) (если i делится на 3). Рекуррентное соотношение — F[i]=min(F[i−1],F[i/2],F[i/3])+1 (для языка Pascal: F[i] = min(F[i-1], F[i div 2], F[i div 3]) + 1), при этом значение F[i/2] (для языка Pascal F[i div 2]) нужно учитывать, только если i делится на 2, а значение F[i/3] (для языка Pascal F[i div 3]) — только если i делится на 3. Начальное значение — F[1]=0. N = int(input()) F = [0 ] * (N + 1) F[1 ] = 0 for i in range(2, N + 1): F[i] = F[i - 1] if i % 2 == 0 and F[i // 2] < F[i]: F[i] = F[i // 2] if i % 3 == 0 and F[i // 3] < F[i]: F[i] = F[i // 3] F[i] += 1 print(F[N]) |