Как решать задачи и заниматься спортивным программированием?
Всем привет! Меня зовут Аргентум, или же Бронислав. На момент написания этой статьи мне 15 лет. Недавно я победил в школьном туре олимпиады по информатике, а скоро иду на муниципальный этап.
По нынешней системе всероссийских олимпиад, программирование на олимпиаде по информатике начинается с 8 класса. У нас в школе олимпиада проводилась в формате онлайн, на платформе «Сириус». Для решения задач по программированию можно было использовать Python, C++, C#, Java, Pascal и некоторые другие. Интересно, что я потратил ~20 минут олимпиадного времени на подключение стабильного интернета.
Я бы не сказал, что я гений программирования, второй Торвальдс, Страуструп, Столлман, Гвидо Ван Россум, Билл Гейтс, Цукерберг вместе взятые. Но я старался решать. За это время, пока велись расчеты победителя школьного тура, я решил изучить олимпиадное программирование и решение задач по программированию. И эти задачи могут касаться также других предметов — химии, физики, математики и так далее, т.к. я решил, что решая такие задачи, я также закрепляю пройденный материал других.
Но почему я решил написать статью на тему олимпиадного программирования и решения проблем? Как по мне, любому человеку важно постоянно тренировать свои навыки, будь то спортсмен или программист. Решение задач закрепляет материал, заставляет человека думать и постоянно развиваться.
Текста и кода будет много, постарался сделать как можно качественнее. Весь код и примеры я буду показывать преимущественно на Python.
Перечень моих репозиториев исходного кода
Наука и инжинерные вычисления
Это целая библиотека, которую я начал разрабатывать в первой моей статье на хабре
Общие задачи
В репозитории есть директория tasks, в ней несколько директорий — base, medium, pro и модуль тестирования задач. В них я складываю задачи по сложности — легкие в base, средние в medium, сложные в pro.
Также в репозитории есть файл olimp.py, через которого вы можете запустить решение той или иной задачи.
Предметные задачи (Химия) — относительная молекулярная масса
Начнем с простого и легкого — определение относительной молекулярной массы вещества. Эту тему обычно изучают первой в курсе по химии в школе.
Ниже я привел формулу для вычисления относительной молекулярной массы на примере NaCl (хлорид натрия, или же поваренная соль).
Для того, чтобы реализовать такой калькулятор, нам потребуется парсер химических функций и сам класс элемента. Герои не ищут простых путей, мы создадим все с нуля
import re # Импорт библиотеки для регулярных выражений
from collections import Counter # Импорт Counter из коллекцийСверху мы импортировали нужные нам модули. Они нужны для парсинга формулы.
class Element:
"""Класс химического элемента"""
def __init__(self, short_name: str, electronic_conf_of_outer_layer: str,
name: str, atomic_number: int, relative_atomic_mass: float,
group: str, period: int, row: int, group_num: int,
side_group: bool, is_metal: bool):
self.short_name = short_name # химический символ элемента
self.electronic_conf_of_outer_layer = electronic_conf_of_outer_layer # внешний электронный слой
self.name = name # название химического элемента
self.atomic_number = atomic_number # атомное число, заряд ядра
self.relative_atomic_mass = relative_atomic_mass # относитльная атомная масса
self.group = group # группа (A или B)
self.side_group = side_group # побочная ли группа (True, False), зависит от группы
self.is_metal = is_metal # металл ли элемент
self.period = period # период
self.row = row # ряд
self.group_num = group_num # номер группы (от 1 до 8)
# Словарь элементов с ключом в виде химического символа элемента
ELEMENTS = {
# Символ ЭлКонф Название АтомноеЧисло ОтносАтомМасса группа период ряд
# номерГруппы ЭтопобочнаяГруппа ЭтоМетал
'H': Element('H', '1s^1', 'Водород', 1, 1.00794, 'A', 1, 1, 1, False, False),
'He': Element('He', '1s^2', 'Гелий', 2, 4.002602, 'A', 8, 1, 1, False, False),
'Li': Element('Li', '2s^1', 'Литий', 3, 6.941, 'A', 1, 2, 2, False, True),
'Be': Element('Be', '2s^2', 'Бериллий', 4, 9.01218, 'A', 2, 2, 2, False, True),
'B': Element('B', '2s^2 2p^1', 'Бор', 5, 10.811, 'A', 3, 2, 2, False, False),
'C': Element('C', '2s^2 2p^2', 'Углерод', 6, 12.011, 'A', 4, 2, 2, False, False),
'N': Element('N', '2s^2 2p^3', 'Азот', 7, 14.0067, 'A', 5, 2, 2, False, False),
'O': Element('O', '2s^2 2p^4', 'Кислород', 8, 15.9994, 'A', 6, 2, 2, False, False),
'F': Element('F', '2s^2 2p^5', 'Фтор', 9, 18.998403, 'A', 7, 2, 2, False, False),
'Ne': Element('Ne', '2s^2 2p^6', 'Неон', 10, 20.179, 'A', 8, 2, 2, False, False),
'Na': Element('Na', '3s^1', 'Натрий', 11, 22.98977, 'A', 1, 3, 3, False, True),
# добавляйте другие элементы по надобности
}Сверху мы создали класс элемента и словарь элементов (я добавил не все элементы, а только с водорода до натрия включительно). Если вам нужно больше, создавайте по шаблону
def repl(m):
return m[1] * int(m[2] if m[2] else 1)
def parse_molecule(formula: str) -> dict:
while '(' in formula:
formula = re.sub(r'\((\w*)\)(\d*)', repl, formula)
while '[' in formula:
formula = re.sub(r'\[(\w*)\](\d*)', repl, formula)
formula = re.sub(r'([A-Z][a-z]?)(\d*)', repl, formula)
formula_dict = Counter(re.findall('[A-Z][a-z]*', formula))
return formula_dict
def get_element_mass(element):
return ELEMENTS[element].relative_atomic_mass
def calculate_relative_molecular_mass(formula):
result = parse_molecule(formula)
mass = 0
for i in result.items():
print(f'{i[1]} {ELEMENTS[i[0]].name} = {ELEMENTS[i[0]].relative_atomic_mass * i[1]}')
mass += get_element_mass(i[0]) * i[1]
return mass
def main():
formula = input('Введите формулу: ')
mass = calculate_relative_molecular_mass(formula)
if mass is not None:
print(f'Относительная молекулярная масса формулы {formula} = ~{mass}')
else:
print(f'Ошибка парсинга формулы {formula}')
if __name__ == "__main__":
main()Сверху конец кода, там мы вычисляем молекулярную массу формулы.
При запуске мы вводим свою формулу… И вуаля, все работает как часы. Весь код вы можете просмотреть в моем репозитории.
Предметные задачи (Химия) — массовая доля элемента в веществе
Пошли серьезные расчеты. Ниже вы видите, как рассчитать массовую долю водорода в формуле H2O (вода).
Мы делим атомную массу элемента на молекулярную массу формулы и умножаем на 100%, и получаем проценты. В итоге — массовая доля водорода равна 11.1%
Сама формула проста — делим атомную массу элемента и умножаем ее на количество элементов на относительную молекулярную массу всей формулы, после умножаем на 100% и получаем сколько процентов занимает элемент в формуле.
Реализуем это на Python, в добавок к предыдущему коду
def calculate_mass_fraction_of_element(formula, element):
formula = parse_molecule(formula) # парсим формулу
mass_fraction = 0 # массовая доля
mass = 0 # молекулярная масса
for i in formula.items(): # высчитываем молекулярную массу
mass += get_element_mass(i[0]) * i[1]
for i in formula.items(): # высчитываем массовую долю элемента
if ELEMENTS[i[0]].short_name == element:
mass_fraction = (get_element_mass(i[0]) * i[1] / mass) * 100
break
return mass_fractionВот и все. При запуске этой функции мы получим массовую долю в процентах
Решение простых задач
Из массива [2, 4, 19, 20, 40, 23, 45, 1000, 34, 23, 1, -3] найдите те, которые делятся на 2 без остатка и больше 5.
На выходе должно получиться
[20, 40, 1000, 34]
Решение
Существует много разных решений, но наиболее рациональным будет следующее:
print([i for i in [2, 4, 19, 20, 40, 23, 45, 1000, 34, 23, 1, -3] if i % 2 == 0 and i > 5])Найдите три ключа с самыми высокими значениями в словаре my_dict = {'a':500, 'b':5874, 'c': 560,'d':400, 'e':5874, 'f': 20}.
На выходе должно получиться ['b', 'e', 'c']
Решениие
mydict = {'a':500, 'b':5874, 'c': 560,'d':400, 'e':5874, 'f': 20}
print(sorted(mydict, key=mydict.get, reverse=True)[:3])Постройте числовой треугольник из 12 рядов, по типу:
1
22
333
4444
55555Решение
rows = 12
for i in range(rows):
for i in range(i):
print(i, end="")
print("")Выше представлено решение
Олимпиадное программирование
Большинство соревнований для программистов требует быстрой и качественной реализации решения проблемы. Программисты пытаются сделать код как можно короче, быстрее и тратить меньше ресурсов, жертвуя при этим читабельностью и стилем кода.
Любой спортивный программист выбрал бы нечитабельное решение за 1 строчку кода, чем такое же, но за две.
Принцип олимпиадного программирования — это участие в соревнованиях по решению нетривиальных алгоритмических задач. Программисту важно быстро решить задачу, не сделав ошибок (но их нет только в том коде, которого не существует). Жюри готовит описание задачи, формат входных и выходных данных, сколько максимум ресурсов может использовать программа.
Для того чтобы стать профессионалом в олимпиадном программировании, вам надо решать не только задачи на программирование, но и простые, логические задачи.
Также вам нужно будет изучить динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, которые выглядят как набор подзадач, сложность которых меньше исходной. В этом случае время вычислений по сравнению с «наивными» методами можно значительно сократить. Чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы.
Заключение
Олимпиадное программирование, решение задач — штука сложная, но полезная. Они заставляют думать и отметать неэффективные решения.
Можно начинать с Python, но постепенно переходить на C++, если хотите участвовать в более сложных олимпиадах.
Минимум для изучения в программировании — переменные, функции, операторы и логика, массивы, циклы, процедуры, классы, стандартные библиотеки.
Сайты для решения задач по программированию:
CodeWars (решение задач)
Kaggle (исследовательские задачи, связанные с Data Science и МО)
LeetCode (решение задач)
Codeforces (решение задач)
Exercism (решение задач)
All Cups (решение задач)
Задавайте вопросы и комментируйте, я рад услышать любое мнение. И конечно, ставьте плюсы!
