Списки и около того

Разбор позапрошлого Д/З.

Понятие «протокола» или «что такое утка?»:

• Iterator protocol: __next__() и StopIteration (необязательно)

• Sequence Protocol: __getitem__() и много необязательного (сложение-умножение, изменение и т. п.)

• для цикла for: __iter__() или __getitem__()

• Number protocol: множество операций (например, __add__()/...)

  • правое умножение строки на число, NotImplemented

• ...

Списки

• Это последовательности (всё действия над ними, включая распаковку)
• Это динамические массивы (точнее, таблицы связей)
  • …с автоувеличением/автоуменьшением
  • ⇒ быстродействие
    • поиска
    • индексирования
    • удаления/вставки в начало/конец/середину
    • worst case (попало на изменение размера)
• Это модифицируемые последовательности
  • изменение элемента
  • изменение сечения
  • методы
  • ⇒ объект не меняется, содержимое меняется

  • ⇒ например, +=

• Список и стек
  • быстрые операции

• Имитация двумерного массива списком списков, pprint

• Список и очередь

  • ⇒ collections.deque

• Циклический конструктор списка
  • …с фильтром
  • …вложенный

(если успеем) Замещение рекурсии стеком

• Анализ рекурсивного алгоритма:
  • объём контекста
  • объём сохраняемого контекста (что видно при выходе из рекурсивного вызова)
• Сохраняемый контекст = ячейка стека
• Остальное — цикл:
  • Цикл — пока стек не пуст
  • Вход в рекурсивный вызов — заполнение стека связанными переменными, выход — восстановление предпоследнего контекста
  • Фрагменты кода перед и после каждого рекурсивного вызова надо уметь различать

    • ⇒ в понятие контекста входит стадия

• …профит!

Пример: НОД

   1 def nod(a,b):
   2     '''Рекурсивный вариант'''
   3     return nod(b, a%b) if b else a
   4 
   5 def nodC(a,b):
   6     '''Нерекурсвный вариант
   7     Стек не нужен!'''
   8     while b:
   9         a, b = b, a%b
  10     return a

Пример: черепашка

   1 import turtle
   2 
   3 def spyro(size, minsize, angle):
   4     '''Рекрсивный вариант'''
   5     turtle.forward(size)              # действия до вызова
   6     turtle.left(angle)
   7     if(size>minsize):
   8         spyro(size-2, minsize, angle) # size = size-2 ⇒ в контекст
   9     turtle.right(angle)               # действия после вызова
  10     turtle.back(size)
  11 
  12 def spyro2(size, minsize, angle):
  13     '''Нерекурсивный вариант'''
  14     stack = [[size, "forward"]] # размер и стадия
  15     while stack:
  16         if stack[-1][1] == "forward":
  17             turtle.forward(stack[-1][0])
  18             turtle.left(angle)
  19             stack[-1][1] = "backward"
  20             if(stack[-1][0]>minsize):
  21                 stack.append([stack[-1][0]-2, "forward"])
  22                 continue
  23         elif stack[-1][1] == "backward":
  24             turtle.right(angle)
  25             turtle.back(stack[-1][0])
  26             stack.pop()

Д/З

0. Прочитать и прощёлкать десятую главу учебника и в Tutorial

1. EJudge: SortedSin 'Сортировка по синусам'

   Ввести список вещественных чисел и отсортировать его по возрастанию синусов этих чисел.

   Input:

   [.1,1,2,3,4,5,6,7,8,9,10]

   Output:

   [5, 4, 10, 6, 0.1, 3, 9, 7, 1, 2, 8]

   • Кому не лень, попробуйте сделать решение в две строки (понадобится немного Python-читерства) или даже в одну (вот тут побольше )

1. EJudge: LinearLab 'Линейный Лабиринт'

   Лабиринт задан списком целых чисел A. Правила обхода следующие: находясь над ячейкой № k, путешественник может передвинуться на A[k] ячеек вперёд или на одну ячейку назад, если это позволяют границы списка. Ввести список и вывести YES, если из A[0] можно таки образом попасть в A[-1], и NO, если нельзя.

   Input:

   [1,2,6,2,8,2,10,2,11,2,13,2]

   Output:

   YES

2. EJudge: SpiralDigits 'Цифры по спирали'

   Ввести целые M и N, вывести последовательность 0 1 2 3 4 5 6 7 8 9 0 1 2 3 … в виде спирально (по часовой стрелке, из верхнего левого угла) заполненной таблицы N×M (N строк, M столбцов). Не забываем про то, что M и N могут быть чётными, нечётными и неизвестно, какое больше.

   Input:

   6,5

   Output:

   0 1 2 3 4 5
   7 8 9 0 1 6
   6 7 8 9 2 7
   5 6 5 4 3 8
   4 3 2 1 0 9

3. EJudge: LookSay 'Прочти это вслух'

   Написать генератор LookSay() цифр последовательности Конвея «Look and Say». (Сама последовательность Конвея). Описание в Википедии

   Input:

   for i,l in enumerate(LookSay()):
       print(f"{i}: {l}")
       if i>10:
           break

   Output:

   0: 1
   1: 1
   2: 1
   3: 2
   4: 1
   5: 1
   6: 2
   7: 1
   8: 1
   9: 1
   10: 1
   11: 1