Циклические алгоритмы. Сечение последовательностей

Разбор Д/З

Практика показала, что те, кто просто делает домашние задания, справляются с заданиями по новым темам, а кто не делает — нет.

Секционирование списков

Суть

Идея секционирования проста: вы можете взять из последовательности подпоследовательность.

Делается это с помощью таких же квадратных скобок, как при операции индексирования, только синтаксис выглядит иначе:

    имя_последовательности[индекс_начала:индекс_конца:шаг]

Нюансы

Шаг вместе с предшествующим ему двоеточием можно не указывать, тогда шаг принимается равным 1. А вот первое двоеточие придётся указать в любом случае.

Элемент, индекс которого совпадает с индексом_конца, в срез уже не попадает (можно провести аналогию с range).

Если не указать индекс_начала, то по умолчанию он будет соответствовать нулевому элементу (если шаг положительный) или последнему (если шаг отрицательный).

Если не указать индекс_конца, то по умолчанию он будет соответствовать последнему элементу плюс один (если шаг положительный) или элементу, стоящему перед нулевым (не минус первому!) (если шаг отрицательный).

Как известно, лучше один раз увидеть, чем тысячу раз услышать:

   1 >>> s = list(range(10,60,6))    # Для примера будем брать срезы (подпоследовательности) списка
   2 >>> s
   3 [10, 16, 22, 28, 34, 40, 46, 52, 58]
   4 >>> s[1:3]    # Срез списка (тоже список): элементы с первого (нумерация с нуля) до второго включительно
   5 [16, 22]
   6 >>> s[5:8]    # Элементы с пятого до седьмого включительно (опять-таки, нумерация с нуля)
   7 [40, 46, 52]
   8 >>> s[4:4]    # Элемент с индексом, совпадающим с индексом конца среза, в срез не попадает
   9 []
  10 >>> s[:3]    # Все элементы от начала списка до третьего элемента, не включая его
  11 [10, 16, 22]
  12 >>> s[6:]    # Все элементы, начиная с шестого и до конца
  13 [46, 52, 58]
  14 >>> s[:]    # список из всех элементов данного
  15 [10, 16, 22, 28, 34, 40, 46, 52, 58]
  16 >>> s is s[:]    #  Для кортежей такая операция взятия среза вернёт тот же самый кортеж, поскольку кортеж - неизменяемый тип данных, и нет смысла заводить вторую его копию в памяти. А вот, скажем, для списков будет возвращён новый объект; этим часто пользуются, например, для чтобы обнуления списка:
  17 False
  18 >>> s == s[:]
  19 True
  20 >>> s[0:6:2]    # Срез из элементов, имеющих индекс из диапазона 0-6, не включая правую границу, взятых с шагом 2
  21 [10, 22, 34]
  22 

И индексы начала и конца, и шаг могут быть отрицательными:

   1 >>> s    # Напоминаю, с какой последовательностью мы работаем
   2 [10, 16, 22, 28, 34, 40, 46, 52, 58]
   3 >>> s[-1:0]    # Срез "от последнего элемента до нулевого" всегда будет пустым
   4 []
   5 >>> s[-4:6]    # Срез "от четвёртого элемента с конца до шестого" (обратите внимание на повисшую запятую (trailing comma) в конце списка)
   6 [40,]
   7 >>> s[0:-3]    # Срез "от нулевого элемента до третьего с конца"
   8 [10, 16, 22, 28, 34, 40]
   9 >>> s[0::-2]    # Интересный пример: срез "от нулевого элемента до стоящего перед нулевым с шагом -2"
  10 [10,]
  11 >>> s[6::-2]    # Иногда проще думать о срезах не в терминах индексов: срез из элементов от нулевого до седьмого включительно, взятых в обратном порядке с шагом 2, начиная с шестого
  12 [46, 34, 22, 10]
  13 >>> s[6:0:-2]    # Обратите внимание, что, если не указывать индекс конца при отрицательном шаге, как в примере выше, срез берётся не до нулевого элемента, а как бы до элемента перед нулевым (называть его "минус первым" будет некорректно, поскольку элемент с индексом -1 существует  и обозначает совсем другое)
  14 [46, 34, 22]
  15 >>> s[::-2]    # Снова, не будем думать об индексах: "срез из элементов списка, взятых в обратном порядке с шагом два, начиная с последнего"
  16 [58, 46, 34, 22, 10]
  17 

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

   1 >>> s[-500:-100]    # Задаваемый диапазон вообще не пересекается с диапазоном индексов нашего списка
   2 []
   3 >>> s[6:1024]    # Частично пересекается
   4 [46, 52, 58]
   5 >>> s[-42:42]    # Диапазон индексов списка целиком содержится в том диапазоне, по которому мы хотим взять срез
   6 [10, 16, 22, 28, 34, 40, 46, 52, 58]
   7 

С учётом всех тонкостей операции взятия среза, не лишним будет проиллюстрировать, как определить нужный индекс:

Замена секций

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

   1 >>> s = [10, 16, 22, 28, 34, 40, 46, 52, 58]
   2 >>> s[2:5] = "QQ", "QKRQ", "Yeah", "Nah"
   3 >>> s
   4 [10, 16, 'QQ', 'QKRQ', 'Yeah', 'Nah', 40, 46, 52, 58]
   5 

Например, можно вставить секцию взамен пустой (т. е. просто после определённого элемента), или вставить пустую секцию вместо непустой (т. е. удалить):

   1 >>> s[4:6] = []
   2 >>> s
   3 [10, 16, 'QQ', 'QKRQ', 2, 1, 'Nah', 40, 46, 52, 58]
   4 >>> del s[-5:-3]
   5 >>> s
   6 [10, 16, 'QQ', 'QKRQ', 2, 1, 46, 52, 58]
   7 

В правой части может стоять любая последовательность (в примере выше был кортеж, но может быть, например, и диапазон, и строка).

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

   1 >>> s[1:8:2]
   2 [16, 'QKRQ', 1, 52]
   3 >>> s[1:8:2] = 1,2,3,4
   4 >>> s
   5 [10, 1, 'QQ', 2, 2, 3, 46, 4, 58]
   6 >>> s[1:8:2] = 1,2,3,4,5
   7 Traceback (most recent call last):
   8   File "<stdin>", line 1, in <module>
   9 ValueError: attempt to assign sequence of size 5 to extended slice of size 4
  10 >>> del s[1:8:2]
  11 >>> s
  12 [10, 'QQ', 2, 46, 58]
  13 

Циклические алгоритмы

Несколько примеров шаблонного использования циклов и последовательностей.

Ввод до маркера

Пользователь вводит данные, которые тут же обрабатываются или помещаются в список. Ввод заканчивается, когда пользователь вводит специальное значение-маркер (в наших задачах был 0). Маркер не попадает в список.

Это цикл, количество шагов которого заранее неизвестно. Данные добавляются в список при помощи append().

   1 Lst = []
   2 n = int(input())        # Инициализация
   3 while n>=0:             # Проверка условия
   4     Lst.append(n)       # Тело
   5     n = int(input())    # Изменение

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

Поиск первого

Пройти по последовательности (или вводить до маркера) и найти в ней первый элемент, отвечающий определённым критериям. Сделать что-то иное, если такого нет.

Смысл этого алгоритма — в двух условиях завершения. Первое — что последовательность закончилась, второе — что элемент найден, и искать больше не надо. Типичный случай применения else к циклу (while и for)

   1 # Найти в списке положительное чётное число и вывести его.
   2 # Если такого нет, вывести "NO"
   3 for e in Lst:               # Три секции цикла в for объединены (кроме тела)
   4     if e>0 and e%2 == 0:    # Условие поиска
   5         print(e)            # Действие успешного поиска
   6         break               # Выход без else
   7 else:                       # Цикл закончился, поиск всё ещё неуспешен
   8     print("NO")             # Действие неуспешного поиска

Аккумуляция

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

   1 # Посчитать количество непустых элементов списка
   2 count = 0                   # Счётчик. По умолчанию 0
   3 for e in Lst:               # Проход по всему списку
   4     if e:                   # Если элемент непуст
   5         count += 1          # Увеличиваем счётчик

Индексирование последовательности в этом и других похожих алгоритмах нужно только если внутреннее условие использует несколько элементов последовательности одновременно.

   1 # Посчитать количество непосредственных инверсий в числовом списке
   2 # (это когда меньший элемент стоит непосредственно после большего)
   3 inversions = 0              # По умолчанию 0
   4 for i in range(len(Lst)-1): # Проходим диапазон нужных индексов
   5     if Lst[i]>Lst[i+1]:     # Встретилась инверсия
   6         inversions += 1     # Увеличиваем счётчик
   7 # Например, в списке [1,6,3,7,2] две непосредственные инверсии — 6,3 и 7,2

Отображение

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

   1 # Выделить из вещественной последовательности только числа с нулевой дробной частью
   2 ints = []                   # Сюда будем складывать числа с нулевой дробной частью
   3 for e in Lst:               # Проходим по списку
   4     if int(e) == e:         # У целых дробная часть нулевая
   5         ints.append(e)      # e — не обязательно целое

Модификация

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

   1 # Заменить эелменты целочисленного списка их модулями
   2 for i in range(len(Lst)):   # Диапазон, соответствующий индексам списка
   3     if Lst[i]<0:            # Отрицетиельный элемент
   4         Lst[i] = -Lst[i]    # …теперь положительный!

Ещё вариант:

   1 # Переставить местами элементы, стоящие на чётных и на нечётных местах
   2 # Проходим диапазон, соответствующий чётным индексам списка
   3 for i in range(0,len(Lst),2):
   4     # Вот такое удобное множественное связывание!
   5     Lst[i], Lst[i+1] = Lst[i+1], Lst[i]

Пример, почему нельзя при модификации изменять длину списка:

   1 >>> a = [1,2,3,4,5,6,7,8]
   2 >>> for i in range(len(a)):
   3 ...     print(i, a)
   4 ...     if i%2:
   5 ...         del a[i]
   6 ...
   7 0 [1, 2, 3, 4, 5, 6, 7, 8]
   8 1 [1, 2, 3, 4, 5, 6, 7, 8]
   9 2 [1, 3, 4, 5, 6, 7, 8]
  10 3 [1, 3, 4, 5, 6, 7, 8]
  11 4 [1, 3, 4, 6, 7, 8]
  12 5 [1, 3, 4, 6, 7, 8]
  13 6 [1, 3, 4, 6, 7]
  14 7 [1, 3, 4, 6, 7]
  15 Traceback (most recent call last):
  16   File "<stdin>", line 4, in <module>
  17 IndexError: list assignment index out of range

Д/З

0. Прочитать и прощёлкать этот конспект!

1. EJudge: FixSum 'Ограниченная сумма'

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

   Input:

   2
   3
   4
   5
   6
   7
   8
   9
   10

   Output:

   27

2. EJudge: PairFind 'Найти пару'

   Ввести список (можно кортеж) чисел, найти в нём первые два одинаковых элемента, стоящие друг за другим. Вывести число, которому они равны или NO, если таких нет.

   Input:

   12, 34, 678, 234, 34, 12, 567, 23, 567, 42, 42, 678, 234, 34, 12, 567,

   Output:

   42

3. EJudge: SimpleSort 'Сортировка выбором'

   Ввести список и упорядочить его элементы по возрастанию. Можно воспользоваться следующей инструкцией: найти наименьший элемент списка и поменять его местами с нулевым; найти наименьший элемент без учёта нулевого и поменять его местами с первым; найти наименьший элемент без учёта первых двух и поменять его местами со вторым; ... Вывести полученный список. Описание алгоритма:

   • По всем индексам i элементов списка, начиная с 0 и заканчивая предпоследним

     • Найти наименьший элемент среди всех элементов, начиная с i-го, запомнить его индекс k

     • Поменять местами i-й и k-й элементы (таким образом на i-м месте окажется наименьший, а на k-м — тот, что стоял раньше на i-м)
   Input:

   [ 6, 9, 6, 8, 5, 7, 10, 7, 7, 9, 6, 8, 9, 5, 9, 8, 5, 6, 7, 8 ]

   Output:

   [5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 10]

4. EJudge: SumFour 'Суммы четвёрок'

   Ввести числовой список длиной не менее, чем 4. Сформировать и вывести список, в котором нулевой элемент равен сумме начальных 4 элементов исходного списка, первый — сумме четырёх элементов исходного списка, начиная с 1-го, второй — сумме четырёх элементов исходного списка, начиная со второго, и т. п. до четвёртого с конца элемента включительно.

   Input:

   [-2, 2, 5, 3, -1, -1, 3, -0, 1, 3, 0, 2, -5, -1, -3, -4, -4, -1, -4, -2]

   Output:

   [8, 9, 6, 4, 1, 3, 7, 4, 6, 0, -4, -7, -13, -12, -12, -13, -11]