ПЗ №3. Алгоритмы обработки данных структурированного типа «Список»

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

Типовые задачи обработки списков

  • Заполнение списка (клавиатура, случайные числа, по формуле).

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

  • Последовательная обработка всех элементов списка.

  • Поиск.

  • Сортировка.

Заполнение списка

Ввод с клавиатуры

Используем цикл for и шаблон с переменной-аккумулятором.

Вариант № 1 - количество элементов известно заранее.

n = int(input("Количество > "))

lst = [] # пустой список

for i in range(n):
    item = input("Элемент списка > ")
    lst = lst + [item] # [] скобки обязательны!

print(lst)

Вариант № 2 - ввод элементов до значения-часового.

Используем шаблон Цикл с выходом.

lst = [] # пустой список

while True:
    item = input("Элемент списка > ")
    if item == "": # пустое значение прерывает цикл
        break
    lst = lst + [item] # [] скобки обязательны!

print(lst)

Оптимизация

Для лучшей производительности, при добавлении нового элемента в список нужно использовать метод append(<элемент>):

n = int(input("Количество > "))

lst = [] # пустой список

for i in range(n):
    item = input("Элемент списка > ")
    lst.append(item)

print(lst)

Заполнение по формуле

Значение очередного элемента списка определено с помощью функции от его индекса.

Пример

\(A\) - список, \(i\)-ый элемент которого равен \(i^2\):

\[ A_i=i^2 \]

A = []

for i in range(10):
    A.append(i ** 2)

print(A)

Если следующее значение элемента зависит от одного или нескольких предыдущих элементов, то такое соотношение называется рекуррентным.

Пример - факториал числа \(n\):

\[ n! = n \cdot (n-1)!, при\ n \ge 1 \\ 0! = 1 \]

F = [1]
for i in range(1, 10):
    fact = i * F[i - 1]
    F.append(fact)

print(F)

✍🏻 Задание № 1 - Заполнение списка

Заполните список согласно указанным правилам. Во всех задачах используется список под именем lst:

Список содержит 10 чисел. Элемент списка равен удвоенному индексу элемента:

for i in range(____1):
    lst.append(____2)

Список содержит 15 чисел. Элемент списка равен остатку от деления индекса на 10:

for i in range(_____3):
    lst.append(_____4)

Список содержит 8 чисел. Первый элемент списка равен 2. Каждый следующий элемент равен предыдущему, умноженному на 3:

lst.append(___5)
for i in ______6:
    ___________7

Линейный поиск

Поиск элементов

Линейный поиск подразумевает последовательный перебор всех элементов списка.

После обнаружения наилучшего значения выполняются действия, зависящие от условия задачи:

  • остановка обхода списка - “найти индекс первого элемента, который…”;

  • изменение значения переменной - “найти мин./макс. значение”, “определить есть ли …”, “посчитать количество …”;

  • вывод элемента на экран - “вывести все элементы, которые …”.

Обход элементов vs обход индексов списка

lst = [10, -3, 15, 0, -7]

Если по условию задачи не нужно искать индекс подходящих элементов:

for el in lst:
    print(el)

Результат:

10
-3
15
0
-7

Если по условию нужно найти индекс подходящих элементов:

# количество элементов в списке
col = len(lst) 
for i in range(col):
    print(i,"-->", lst[i])

Результат:

0 --> 10
1 --> -3
2 --> 15
3 --> 0
4 --> -7

✍🏻 Задание № 2 - Линейный поиск

Во всех задачах используется следующий список:

lst = [10, -3, 15, 0, -7].

Выведите на экран все отрицательные числа из списка lst.

for el in lst:
    if ________1:
        print(_____2)

Найдите значение первого нечётного числа в списке lst.

for el in lst:
    if _______3:
        print(el)
        ______4

Найдите количество положительных чисел в списке lst и сохраните ответ в переменной pos.

pos = ____5
for el in lst:
    if ______6:
        pos = _______7

Выведите на экран индексы всех чётных чисел в списке lst.

for ______________8:
    if _________9:
        print(____10)

Сортировка. Функция sorted()

Сортировка элементов массива

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

  • 3, 6, 7, 10, 11, 12, 20, 24

    • a[i] < a[i+1]

  • «a», «an», «the», «then», «image», «window»

    • длина a[i] < длина a[i+1]

  • «at», «bat», «cat», «dog», «mouse», «rat»

    • алфавитный порядок

Алгоритмы сортировки

  • Сортировка простым обменом (пузырьковая сортировка)

  • Сортировка выбором

  • Сортировка вставками

  • Сортировка подсчётом

  • Быстрая сортировка

  • …

Сортировка в Python

В языке Python есть встроенная функция для сортировки последовательностей - sorted().

Функция может принимать в качестве аргумента любую последовательность и возвращает список отсортированных элементов.

lst = [4, 6, 2, 7, 1]
s = sorted(lst)
print(s)

Функция-ключ

Кроме последовательности, функция sorted() может принимать аргумент с именем key - функцию-ключ.

Функция применяется к каждому элементу последовательности перед началом сортировки.

st_list = ['блок-схема', 'код', 'программа']
print(sorted(st_list))

print(sorted(st_list, key=len))

Задача

Названия групп в электронном расписании сортируются в алфавитном порядке. Организовать сортировку групп по году поступления.

groups = ['240122', '240124', '240125', '240222', '240223', '240224', '240225', '240323', '240325', '240422', '240423', '240424', '240425', '240523', '240524', '240525']
print(sorted(groups))

Опишем функцию-компаратор, которая переставит в названии группы её номер и год поступления местами:

def convert(g):
    return g[:2] + g[4:] + g[2:4]
print(convert('240122'))

Используем функцию в качестве ключа сортировки:

print(sorted(groups, key=convert))

primer.py

primer.py