Занятие 4

Практическое занятие 4: Обработка числовых последовательностей в Python

Цель: Рассмотреть основы языка Python на примере задач обработки числовых последовательностей

Задачи:

  1. Рассмотреть встроенные функции min() и max()
  2. Рассмотреть статистические функции mean(), median() и stdev() библиотеки statistics
  3. Познакомиться с понятием редукция последовательности
  4. Познакомиться с примерами задач обработки числовых данных в потоке

Встроенные функции max() и min()

Во второй практической работе мы уже использовали встроенную функцию max() для нахождения большего из двух чисел. Сегодня мы более подробно рассмотрим эту функцию, а также функцию для нахождения минимума - min(). Функция max() возвращает наибольшее значение элемента итерируемого объекта или наибольшее из двух или более переданных позиционных аргументов:

In [ ]:
x = [1, 5, -8]
print(max(x))
In [ ]:
print(max(1, 5, -8))

В качестве ключевого аргумента key может быть использована функция одного аргумента, которая будет применяться к каждому из сравниваемых значений.

Поясните результат функции max() из примера ниже:

In [ ]:
print(max(x, key=abs))

Задача 1: с помощью функции max() вычислите наибольшее значение списка x, применяя к элементам списка следующие функции:

— взведение в квадрат;

— добавление константы 10;

— вычисление остатка от деления на число 2.

Проанализируйте результаты.

In [ ]:
In [ ]:
In [ ]:

Формат вызова функции min() аналогичен рассмотренной ранее функции max():

In [ ]:
print(min(x))
In [ ]:
print(min(x, key=abs))

Задача 2: с помощью функции min() вычислите наименьшее значение списка x, применяя к элементам списка следующие функции:

— возведение в степень 3;

— добавление константы 10;

— вычисление остатка от деления на число 2.

Проанализируйте результаты.

In [ ]:

Статистические функции mean(), median() и stdev() библиотеки statistics

В библитеке statistics собраны функции статистической обработки числовых последовательностей. Мы рассмотрим три из них:

— поиска среднего арифметического: mean();

— поиска медианы: median();

— поиска среднеквадратического отклонения: stdev().

In [ ]:
import statistics
print(statistics.mean(x))
In [ ]:
print(statistics.median(x))
In [ ]:
print(statistics.median([1, 5, -8, 10]))
In [ ]:
print(statistics.stdev(x))

Редукция последовательности чисел

Когда на вход алгоритму поступает последовательность чисел произвольной длины, а результат — некоторое интегральное число, например сумма всех чисел или произведение всех чисел или даже просто их количество, то это называется редукцией последовательности.

In [ ]:
A = [1, 2, 3, 4, 5]
print(sum(A))
In [ ]:
import functools
In [ ]:
functools.reduce((lambda s, x: s + x), A)

Функцию для редукции последовательности можно взять произвольную:

In [ ]:
functools.reduce((lambda p, x: p * x), A)
In [ ]:
functools.reduce((lambda xor, x: xor ^ x), A)

Но не обязательно уже иметь все данные в списке или другом контейнере. Поскольку редукция происходит индуктивно, мы можем получать поток чисел с клавиатуры. Чтобы сигнализировать алгоритму, что поток чисел закончился, нужно либо изначально знать их количество, либо задать значение терминального элемента. Допустим, это -1.

Поскольку редукция будет осуществляться за один проход, такой алгоритм может быть назван однопроходным:

In [ ]:
n = 0
s = 0
p = 1
# ввод первого числа:
x = int(input())
# проверка, что очередное число не является терминатором последовательности:
while x != -1:
    # учёт нового числа:
    n = n + 1
    s = s + x
    p = p * x
    # ввод нового числа:
    x = int(input())
print(n, s, p)

На вход алгоритма, редуцирующего последовательность, мы можем подавать не оригинальную, а отфильтрованную последовательность — через некий критерий отбора.

In [ ]:
n = 0
s = 0
p = 1
# ввод первого числа:
x = int(input())
# проверка, что очередное число не является терминатором последовательности:
while x != -1:
    # учёт нового числа, если оно чётное:
    if x % 2 == 0:
        n = n + 1
        s = s + x
        p = p * x
    # ввод нового числа:
    x = int(input())
print(n, s, p)

Поиск максимального или минимального элемента также является редукцией:

In [ ]:
A = [1, 2, 3, 4, 5, 5, 3, 2]
functools.reduce((lambda m, x: max(m, x)), A)

Без контейнера простым циклом это делается так:

In [ ]:
# ввод первого числа:
x = m = int(input())
# проверка, что очередное число не является терминатором последовательности:
while x != -1:
    # учёт нового числа:
    m = max(m, x)
    # ввод нового числа:
    x = int(input())
print(m)

Можно избавиться от вызова встроенной функции max, да ещё и добавить дополнительную функциональность — запоминать местоположение первого числа среди равных максимальному:

In [ ]:
# ввод первого числа:
x = m = int(input())
index = 0
# проверка, что очередное число не является терминатором последовательности:
while x != -1:
    # учёт нового числа -- если оно больше ранее найденного максимума -- обновить:
    if x > m:
        m = x
        m_index = index
    # ввод нового числа:
    x = int(input())
    index += 1  # счётчик позиции числа во входной последовательности
print(m, m_index)

Пример 1 однопроходного алгоритма (взят с сайта Константина Полякова):

Имеется список учеников разных школ, сдававших экзамен по информатике, с указанием их фамилии, имени, школы и набранного балла. Необходимо написать программу, которая будет определять двух учеников школы № 50, которые лучше всех сдали информатику, и выводить на экран их фамилии и имена.

Если наибольший балл набрали более двух человек, нужно вывести только их количество. Если наибольший балл набрал один человек, а следующий балл набрало несколько человек, нужно вывести только фамилию и имя лучшего. Известно, что информатику сдавали не менее 5 учеников школы № 50.

На вход программе в первой строке подается количество учеников списке N. В каждой из последующих N строк находится информация в следующем формате:

<Фамилия> <Имя> <Школа> <Балл>

где <Фамилия> — строка, состоящая не более, чем из 20 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Школа> — целое число от 1 до 99, <Балл> — целое число от 1 до 100.

Пример входной строки:

Иванов Сергей 50 87

Пример выходных данных, когда найдено два лучших:

Иванов Сергей Сергеев Иван

Если больше двух учеников набрали высший балл, то программа должна вывести их количество. Пример вывода в этом случае:

8

Если высший балл набрал один человек, а следующий балл набрало несколько человек, то про-грамма должна вывести только фамилию и имя лучшего. Пример вывода в этом случае:

Иванов Сергей

Для выполнения примера необходимо разместить файл students.txt в директории с ноутбуком практической работы.

Решение

Вначале необходимо определить, как обрабатывать данные. Запоминать все данные не нужно, так как • количество учеников неизвестно • нас интересуют только фамилии двух лучших, то есть достаточно ввести всего две переменных (name1 и name2) Две переменных max1 и max2 будут использоваться для хранения баллов, которые набрали два лучших ученика. Кроме того, нужно считать, сколько учеников набрали высший балл. Для этого используются счетчики count1 и count2.

In [ ]:
# инициируем значения переменных, хранящих значение наибольшего и следующего балла
max1 = -1
max2 = -1

# инициируем значения переменных, хранящих число учеников с наибольшим и следующим баллом
count1 = 0
count2 = 0

# инициируем значением пустой строки имена учеников с наибольшим и следующим баллом
name1 = ''
name2 = ''

Предположим, что мы прочитали данные очередного ученика (и он из школы № 50): его имя находится в переменной name, набранные баллы – в переменной mark. Если балл ученика больше, чем max1, нужно запомнить нового лидера (записать его имя и балл в переменные max1 и name1, в счетчик count1 – единицу), но предварительно записать данные по старому лидеру в переменные max2, name2 и count2.

Если балл равен максимальному, нужно увеличить счетчик count1 и запомнить данные нового ученика в переменных max2 и name2 (теперь он второй).

Если балл находится между max1 и max2, нужно сохранить новые данные по второму ученику (пока он один, поэтому в count2 записываем 1).

Если mark = max2, мы нашли еще одного ученика, имеющего второй результат, нужно его посчитать.

In [ ]:
# читаем данные из файла с потоковой обработкой данных
with open('students.txt', 'r', encoding='utf8') as F:
    # число учеников - не требуется далее
    N = F.readline()

    # считываем строку за строкой - со второй до последней - из файла
    for line in F:
        # разбиваем строку на составляющие
        s = line.split()

        # запоминаем имя
        name = s[0] + ' ' + s[1]
        # запоминаем номер школы
        school = int(s[2])
        #запоминаем набранный балл
        mark = int(s[3])
        # выделяем ученика только из 50-й школы
        if school == 50:
            # выделяем ученика с наибольшим баллом
            if mark > max1:
                # теперь данный ученик с наибольшим баллом (name1), а предыдущий становится name2
                name2 = name1
                max2 = max1
                count2 = count1
                name1 = name
                max1 = mark
                count1 = 1
            # если нашли еще одного ученика с наибольшим баллом
            elif mark == max1:
                count1 += 1
                max2 = mark
                name2 = name
            # если нашли ученика с новым значением следующего балла
            elif mark > max2:
                count2 = 1
                max2 = mark
                name2 = name
            # если нашли еще одного ученика со следующим баллом
            elif mark == max2:
                count2 += 1

При выводе результата нужно учесть три варианта:

  1. Если count1 = 2 или count1+count2 = 2, выводим фамилии первых двух учеников.
  2. Если count1 = 1 и count2 > 1, выводим только фамилию и имя лидера.
  3. Если count1 > 2, выводим только count1.
In [ ]:
# вывод результатов
if (count1 == 2) or (count1 + count2 == 2):
    print(name1, name2, sep='\n')
elif (count1 == 1) and (count2 > 1):
    print(name1)
else:
    print(count1) # count1 > 2

Когда редукция не работает

Есть задачи, котоыре принципиально не могут быть решены за один проход по числам, но обязательно требуется запомнить их все. Например, реверс послеловательности чисел или циклический сдвиг вправо. Или вывод на экран всех чисел, которые больше среднего арифметического всех чисел в последовательности.

Пример 2 (взят с сайта Константина Полякова):

На вход программы подается 366 строк, которые содержат информацию о среднесуточной температуре всех дней 2008 года. Формат каждой из строк следующий: сначала записана дата в виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два символа, день от месяца отделен точкой), затем через пробел записано значение температуры — число со знаком плюс или минус, с точностью до 1 цифры после десятичной точки. Данная информация отсортирована по значению температуры, то есть хронологический порядок нарушен.

Требуется написать программу, которая будет выводить на экран информацию о месяце (месяцах), среднемесячная температура у которого (которых) наименее отклоняется от среднегодовой. В первой строке вывести среднегодовую температуру. Найденные значения для каждого из месяцев следует выводить в отдельной строке в виде: номер месяца, значение среднемесячной температуры, отклонение от среднегодовой температуры.

Для выполнения примера необходимо разместить файл weather2008.txt в директории с ноутбуком практической работы.

Решение

В этой задаче не нужно хранить в памяти все отсчеты, нас интересуют только средние значения температуры по каждому месяцу и по году. В начале программы не забываем обнулить ячейки, где будут накапливаться суммарные величины (month_av и year_av). Также введем массив констант – дней в каждом месяце (month_days).

In [ ]:
N_days = 366
month_days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
month_av = 12*[0]
year_av = 0

При вводе данных в каждой строке сначала пропускаем все символы до точки (с помощью метода find() и среза строки), затем читаем номер месяца (целое число) и температуру (вещественное число). Температуру добавляем к сумме нужного месяца и к годовой сумме:

In [ ]:
with open('weather2008.txt', 'r') as F:
    for line in F:
        s = line.split()
        month = int(s[0][s[0].find('.')+1:])
        t = float(s[1])
        #накапливаем сумму по месяцу и по году
        month_av[month - 1] += t
        year_av += t

Далее находим средние по каждому месяцу и по году:

In [ ]:
#считаем средние по месяцам и по году
for i in range(12):
    month_av[i] /= month_days[i]
year_av /= N_days

Теперь можно искать минимальное отклонение среднемесячной температуры от среднегодовой :

In [ ]:
#находим минимальное отклонения от среднегодовой
min_dev = abs(month_av[0] - year_av)
for i in range(1, 12):
    if abs(month_av[i] - year_av) < min_dev:
        min_dev = abs(month_av[i] - year_av)

Выводим результат. При выводе результата мы используем метод format():

In [ ]:
#Выводим результат
print('{0:.3f}'.format(year_av))
for i in range(0, 12):
    if abs(month_av[i] - year_av) == min_dev:
        print('{0:d}, {1:.3f}, {2:.3f}'.format(i+1, month_av[i], min_dev))