Лекция №1. Олимпиадные задачи по программированию

Хорошевич Павел Александрович

Дорожная карта

Темы

Олимпиадные задачи по программированию

Решите известную задачу из области информатики за кратчайшее время.

В соревновательном программировании задачи не носят исследовательский характер. Эти задачи были решены, как минимум их составителями.

Решить олимпиадную задачу - значит активизировать все свои познания в области информатики для получения кода программы, способного пройти тесты, подготовленные авторами задачи.

Соревновательный компонент олимпиады - необходимость решить предложенные задачи за ограниченное время.

Решение задач - не самоцель.

Основная задача олимпиадного программирования - раскрыть творческий потенциал учащегося, расширить их зону ближайшего развития.

Структура олимпиадной задачи

Зачастую олимпиадная задача по программированию состоит из следующих частей:

• Художественное описание - история, служащая мотивацией к решению задачи. Задача учащегося: отфильтровать лишнее, выделить главное.

• Описание входных и выходных данных - формат ввода/вывода, ограничения.

• Примеры тестовых данных - авторы задач приводят примеры тривиальных тестовых данных. Пограничные случаи должен обнаружить участник.

Практика решения задач

Используйте архивы прошедших олимпиад для тренировки. Такие задачи могут содержать примеры решений или туториалы - теорию, необходимую для решения задачи.

Используйте архивы задач с автоматической проверкой отправленных решений:

• acm.timus.ru
• codeforces.com/problemset
• open.kattis.com
• codewars.com

Этапы решения задач по информатике

Этапы решения задачи по программированию

1. Постановка задачи

1. Определить, что дано и что нужно найти.

2. Определить типы входных и выходных данных и как эти данные будут представлены в программе.

2. Конкретные примеры

1. Подобрать конкретные входные данные и найти способ получить для них выходные значения.

2. Обстрагироваться от конкретных данных и обобщить алгоритм решения для произвольных значений.

3. При необходимости уточнить типы данных, выбранные на этапе постановки задачи.

3. Проектирование алгоритма

1. Описать алгоритм решения задачи на естественном языке: перечислить шаги, благодаря которым были получены выходные значения для каждого конкретного примера.

2. Обратить внимание на общие для каждого примера шаги - повторяющиеся шаблоны.

3. Обобщённый алгоритм записать на естественном языке, псевдокоде или в форме блок-схемы.

4. Уделяем особое внимание фразам-маякам в описании алгоритма: “для каждого элемента …”, “сложить значения …”, “найти сумму …” и т.д.

4. Реализация

Закодировать алгоритм решения на языке программирования. 

5. Тестирование

Тестирование: выполняется ли программа так, как задумывалось и верен ли результат её выполнения.

Отладка программы: исправление найденных на этапе тестирования ошибок.

Пример решения задачи

Дан список температур за неделю. Подсчитать количество дней с отрицательной температурой и сумму модулей отрицательных значений температур.

Определим входные и выходные данные:

• входные данные: список вещественных чисел temps;

• выходные данные: количество дней с отрицательной температурой count - целое число, сумма модулей отрицательных температур summ - вещественное число.

“Черный ящик”

Конкретный пример: список [5, -2, 0, -5, 3, 1, -1].

В этом случае количество равно 3, а сумма модулей температур равна 8.0.

Спроектируем алгоритм.

1. В начале счётчик и сумма равны нулю.

2. Чтобы посчитать количество и сумму, нужно перебрать все элементы списка.

3. Для каждого элемента проверяем, меньше ли он 0.

4. Если это так, то к счётчику прибавим 1, а к сумме прибавим модуль значения этого элемента.

5. Выведем значения счётчика и суммы на экран. 

заполнить список temps значениями

count = 0
summ = 0

для каждого элемента из списка temps
    если элемент меньше нуля то
        увеличить count на 1
        увеличить summ на модуль элемента
        
вывести count
вывести summ

Блок-схема

Реализуем алгоритм на Python:

temps = [5, -2, 0, -5, 3, 1, -1]

count = 0      # счётчик
summa = 0.0    # аккумулятор

for t in temps:
    if t < 0:
        count += 1
        summa += abs(t)

print(f"Дней с отрицательной температурой: {count}")
print(f"Сумма модулей отрицательных температур: {summa} C")

Введение в Python

Установка. Среда программирования

Скачивание с официального сайта python.org.

Среды программирования:

• IDLE: Встроенная среда разработки, поставляемая с Python.
• Jupyter Lab: Интерактивная среда для выполнения кода, особенно полезна для научных вычислений.
• PyCharm: Мощная профессиональная среда разработки от JetBrains.
• Visual Studio Code: Легкая и гибкая среда с поддержкой множества расширений для Python.

Python

Python - интерпретируемый язык программирования. В Python не нужно указывать тип переменной (объекта) при её инициализации.

Динамическая типизация – тип значения определяется автоматически при создании этого значения (объекта).

Сильная типизация – над значением можно выполнять только те операции, которые допустимы для его типа.

Встроенные типы данных

Данные в языке Python представлены в виде объектов стандартного либо описанного программистом типа.

• Целые числа int: -2, -1, 0, 1
• Вещественные числа float: 0.5, 1.0, 1.25
• Строки str: 'Суббота', "Привет!", """2026 год"""
• Списки list: [0, 1, 1, 2, 3, "пять"]
• и другие…

Операторы и операнды

Операторы по приоритету выполнения:

1. () скобки: 3 * (4 - 1) = 9
2. Вызов функции.
3. ** возведение в степень : 2 ** 3 = 8
4. * умножение, / деление, // целочисленное деление , % остаток от деления
5. + сложение , - вычитание

Остаток от деления и целочисленное деление

% - остаток от деления.

10 % 2 # = 0
10 % 3 # = 1

// - целочисленное деление.

10 / 2     # = 5.0 - вещественное число
10 // 2    # = 5   - целое число
10 // 4    # = 2
10 // 4.0  # = 2.0 - вещественное число!

Переменные

Переменная - это имя, которое ссылается на значение.

Имена в Python регистрозависимые. student и Student для Python разные имена.

Правила именования переменных:

1. не содержит пробелов;
2. состоит только из букв, цифр и символа подчёркивания _ ;
3. не начинается с цифры.

Оператор присваивания = связывает имя переменной с её значением.

message = "Как дела?"   # переменная строка
n = 17                  # переменная с целым числом
pi = 3.14159            # переменная с вещественным числом

В Python не нужно заранее указывать тип переменной. Значения обладают типом, имена переменных - нет.

Формы инструкции присваивания

• Стандартная:

  st = "Python"

• Позиционное:

  a, b = "Один", "Два"

• Групповое:

  x = y = z = 10

• Комбинированное:

  age += 1
  proc /= 2

Математические выражения. Модуль math

Импорт модуля в скрипт:

import math

Обращение к функциям происходит через оператор-точку:

math.pi         # Приблизительное значение числа Пи
math.sqrt(x)    # Корень квадратный из x
math.sin(a)     # Синус угла a в радианах
math.exp(x)     # e^x

Вывод значений. Функция print()

Формы записи функции print:

print(<выр>, <выр>, … <выр>)
print() 

Вывод выражения закончится пробелом:

print(<выр>, end=" ")

Пример:

print(3 + 5 - 7)
print(3, 6, 6 * 2)
print()
print("Ответ равен ", 4 * 5)
print("Ответ равен", end=" ")
print(4 * 5)

Форматированный вывод

Для форматированого вывода используются f-строки:

f"Тест сообщения {<выражение>}"

Пример:

name = "Python"
year = 1991
answer = f"{name}, вам примерно {2026 - year} лет."
print(answer)

f-строка

Ввод значений. Функция input()

Для ввода значений используется функция input():

x = input("Приглашение к вводу...")

Функция input() всегда возвращает значение строкового типа str.

Функций для преобразования значения одного типа в другой:

• в целое число: int()
• в вещественное число: float()
• в строку: str()

Задача

Вычислите среднее арифметическое двух чисел.

print("Среднее арифметическое двух чисел")
# ввод первого числа
num1 = float(input("Введите первое число "))
# ввод второго числа
num2 = float(input("Введите второе число "))
'''
вычисление среднего арифметического
чтобы сложение выполнилось раньше деления
слагаемые помещены в скобки
'''
average = (num1 + num2) / 2

print(f"Ответ: {average}")

Описание собственных функций

Объявление функции с параметрами:

def <имя функции>(<параметры>):
    <блок инструкций>

Вызов функции с аргументами:

<имя функции>(<аргументы>)

Пример:

def formatDate(day, month, year):
    """Выводим дату в красивом формате"""
    print(f"Сегодня {day}.{month} {year} года")

formatDate(22, 11, 2024)
formatDate(11, 2024, 22) # аргументы перепутаны

Оформление блока инструкций

В Python вложенность инструкций определяется отступами. Блок инструкций начинается после двоеточия :

• Блок связанных инструкций должен иметь одинаковый отступ.
• Размер отступа может быть произвольным (рекомендовано 4 пробела).
• Для создания отступов можно использовать пробелы или табуляцию.
• Нельзя смешивать пробелы и символы табуляции при оформлении одного блока.

Дополнительная информация по оформлению кода - PEP8

Возвращаем значение

Чтобы вернуть значение из функции используется инструкция return.

Пример:

def square(x):
    y = x * x
    return y  # возвращаем результат из функции

n = 10
result = square(n) # вызов функции
print(f"Результат: {result}")

primer.py