В статье приведены три задачи для иллюстрации в каких случаях использование множеств в программировании весьма уместны и удобны.
Поехали!
Полиглоты.
В школе каждый из N учеников знает Mᵢ языков. Узнайте, какими языками владеют все школьники и языки, которые знает хотя бы один из учащихся.
Во входных данных в первой строке записано количество школьников N. Затем идет N чисел Mᵢ, после каждого из чисел идет Mᵢ строк, в которых записаны названия языков, которые знает i-й ученик.
1≤N≤1000, 1≤Mᵢ≤500.
Выведите в первой строке количество языков, которые знают все учащиеся. Со второй строки выведите список этих языков. Далее запишите количество языков, которые знает хотя бы один школьник, на последующих строках выведите список названий этих языков.
Пример.
Входные данные: 3 \n 3 \n Russian \n English \n Japanese \n 2 \n Russian \n English \n 1 \n English , где \n - символ переноса строки.
Вывод программы: 1 \n English \n 3 \n Russian \n Japanese \n English
Решение.
inFile = open ( 'input.txt' , 'r' , encoding = 'utf8' )
n = int ( inFile.readline())
allLeng = set ()
generalLeng = set ()
for i in range ( n) :
....m = int ( inFile.readline())
....tmpSet = set ()
....for j in range ( m) :
........line = inFile.readline() .rstrip( ' \n ' )
........allLeng.add( line)
........tmpSet.add( line)
........if i == 0 :
............generalLeng.add( line)
....generalLeng &= tmpSet
inFile.close()
print (len( generalLeng) , *generalLeng, len(allLeng) , *allLeng, sep = '\n ')
Для решения задачи удобно воспользоваться множествами. Все языки просто записываются во множество allLeng. Для языков, которые знают все учащиеся, используется множество generalLeng. Оно формируется из пересечения .generalLeng &= tmpSet, где tmpSet - множество языков каждого школьника.
Пересадки.
На время закрытия станции метро для пассажиров было запущено два новых автобусных маршрута на разных участках проспекта. Конечные остановки каждого из дополнительных автобусов известны. Узнайте количество остановок, на которых можно сделать пересадку с одного автобуса на другой.
Во входных данных вводятся четыре числа, не превышающие 100, которые задают номера конечных остановок. Сначала для первого, затем второго автобуса (см. примеры и рисунок).
Программе нужно вывести одно число – количество остановок, на которых можно сделать пересадку с одного автобуса на другой.
Пример первый (см. рисунок): один автобус ходит с 3-й остановки по 6-ю и обратно, а другой с 2-й по 4-ю и обратно. Пересесть с первого автобуса на второй возможно на 3-й и 4-й остановках. Входные данные: 3 6 4 2. Ответ: 2. Пример второй: один автобус ходит с 1-й остановки по 3-ю и обратно, а другой с 5-й по 6-ю и обратно. Автобусы не имеют общих остановок. Входные данные: 1 3 5 6. Ответ: 0.
Решение.
n = list ( map ( int , input () .split()))
n1 = sorted ( [ n[ 0 ] , n[ 1 ]] )
n2 = sorted ( [ n[ 2 ] , n[ 3 ]] )
set1 = set ()
set2 = set ()
for i in range ( n1[ 0 ] , n1[ 1 ]+ 1 ) :
....set1.add( i)
for i in range ( n2[ 0 ] , n2[ 1 ]+ 1 ) :
....set2.add( i)
print ( len ( set1 & set2))
Создаются два списка с отсортированным номерами конечных остановок n1 и n2. С их помощью в цикле создаются два множества с наборами всех остановок каждого маршрута set1 и set2. Пересечение множеств дает ответ на задачу.
Забастовки.
В одной не очень далекой стране стране действует K политических партий. Каждая партия регулярно объявляет национальную забастовку. В выходные дни (субботу или воскресенье) забастовки не проводят. i-я партия проводит забастовки обязательно каждые bᵢ дней, начиная с дня под номером aᵢ. Получается, что i-я партия проводит забастовки в дни aᵢ, aᵢ+bᵢ, aᵢ+2bᵢ и т.д. Если в какой-то день сразу несколько партий проводят забастовки, тогда это считается одной общенациональной забастовкой. В календаре мы имеем N дней, пронумерованных от 1 до N. Первый день года это понедельник, шестой и седьмой дни в неделе — выходные, в неделе семь дней.
На вход программа получает количество дней в году N (1≤N≤10⁶) и количество политических партий K (1≤K≤100). Затем следует K строк для описания графиков проведения забастовок. В i-ой строке содержатся числа aᵢ и bᵢ (1≤aᵢ,bᵢ≤N).
Необходимо вывести число забастовок, произошедших в течение года.
Пример.
Партия номер один объявляет забастовки в дни 2, 5, 8, 11, 14, 17. Партия номер два объявляет забастовки в дни 3, 8, 13, 18. Партия номер три — в дни 9 и 17. Дни в календаре с номерами 6, 7, 13, 14 являются выходными. Значит забастовки будут проведены в дни 2, 3, 5, 8, 9, 11, 17, 18. Вывод программы - 8.
Решение.
inFile = open ( 'input.txt' , 'r' , encoding = 'utf8' )
n = list ( map ( int , inFile.readline() .split()))
calend = set ()
strikeSet = set ()
for i in range ( 1 , n[ 0 ]+ 1 ) :
....if i + 1 % 7 != 0 and i % 7 != 0 :
........calend.add(i)
for i in range (n[ 1 ]) :
....prt = list ( map ( int , inFile.readline() .split()))
....for j in range ( prt[ 0 ] , n[ 0 ]+ 1 , prt[ 1 ] ) :
........if j in calend:
............strikeSet.add( j)
print (len(strikeSet))
inFile.close()
Сначала в список n записываем n[0] - количество дней в году, а в n[1] - количество политических партий. Затем создаем календарь с помощью множества calend, каждый 6-ой и 7-ой день не включаем - это выходные дни. Делаем цикл по всем дням для каждой партии for j in range(prt[0], n[0]+1, prt[1]), где prt[0] - aᵢ число, с которого начинаются забастовки, prt[1] - bᵢ количество дней забастовки. В этом цикле если день есть в календаре, то записываем его во множество strikeSet. Количество дней в strikeSet будет ответом.
Заключение.
Множества - тема довольно сложная для начинающих, тем более если вы плохо знаете математику. Однако, поверьте на слово, использование множеств не редко существенно упрощает работу программиста, поэтому тема достойна пристального изучения.
Еще одна статья на эту тему:
5 примеров использования множеств в решении задач на Python.
Так же другие статьи:
Примеры решения задач на Python (кортежи, списки, for, split, join).
Решение задач по программированию на Python (часть 4, while)
Решение задач по программированию на языке Python для начинающих (2 часть, IF)
