Двумерные и многомерные структуры

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

Списки строк

Список бывает из чего угодно

• В том числе из объектов разного типа и размера
• Например, из функций!

Например, список строк

• Как обратиться к конкретной строке?
• Что с ней можно делать
  • (Вообще всё)
• Как обратиться к элементу или секции строки?

• Вот вам и A[i][j]

Метафора «текстового экрана»

• Как списка строк

  • Удобства, примеры и недостаток — строки константны

• Как списка списков односимвольных строк (не пугайтесь, это то же самое… почти)

  • Недостаток (временный): ввод (list(строка)) и вывод

    • Пример ручного вывода — проход вложенными циклами

Методы .split() и .join()

• Как работают и что делают

  • Почему .join() — это метод разделителя

• Примеры использования
  • В частности, для вывода «строки экрана» (списка односимвольных строк)

Отступление: страшные конструкции вида A[1](2)[3][4](5)…

Секрет: они не страшные ☺

• Каждая пара скобок — это операция над объектом, которая возвращает другой объект

  • …(): объект — это функция, её надо вызывать, и работать с результатом

  • …[]: объект — это индексируемая последовательность (список, кортеж, строка, …), от него надо взять элемент или сечение и работать с результатом

• ⇒ Цепочка скобок — это просто последовательные вызовы соответствующих операций над соответствующими объектами

«Двумерный массив»

Задача моделирования данных как подзадача формализации алгоритма.

• Структура данных IRL vs чем она будет представлена в программе на Python

• ∄ «правильного» типа на всякую хитрую структуру, но ∃ удобный для данного алгоритма

В частности, матрицы:

• В математической абстракции — прямоугольные таблицы, в которых у каждого элемента по две координаты (или больше, если многомерные)

Чем их моделировать?

• А зачем? ☺
  • Если ради доступа по координатам — список списков will do
  • Если ради эффективности доступа и преобразований — не совсем (двойная косвенность, неуважение к кешам из-за разброса по памяти и т. п.)
    • Нужно только математикам

⇒ Список списков, а-ля «экран», только вместо символов — числа

• Вывод вручную

• Вывод pprint

• Вывод с помощью циклического конструктора и .join()

О циклическом конструкторе списка

• Просто список: [элемент, элемент, …]

• Простой циклический конструктор: [выражение for переменная in последовательность]

     1 >>> s = [str(i) * 2 for i in range(6)]
     2 >>> print(s)
     3 ['00', '11', '22', '33', '44', '55']
     4 
  

  • Аналог:

       1 s = []
       2 for i in range(6):
       3     s.append(str(i) * 2)
    

• С фильтром: [выражение for переменная in последовательность if выражение]

     1 >>> s = [i * 2 + 1 for i in range(12) if i % 5 != 0]
     2 >>> print(s)
     3 [3, 5, 7, 9, 13, 15, 17, 19, 23]
     4 
  

  • Аналог:

       1 s = []
       2 for i in range(12):
       3     if i % 5 != 0:
       4         s.append(i * 2 + 1)
    

• Вложенные:

     1 >>> s = [a + b for a in "aeo" for b in "lmn" ]
     2 >>> print(s)
     3 ['al', 'am', 'an', 'el', 'em', 'en', 'ol', 'om', 'on']
     4 
  

  • Аналог (обратите внимание на то, какой цикл в какой вложен):

       1 s = []
       2 for a in "aeo:
       3     for b in "lmn":
       4         s.append(a + b)
    

• Вложенные с фильтром… ☺

Д/З

0. Прочитать и прощёлкать занятие про двумерные массивы на pythontutor.ru

TODO EJudge

1. EJudge: BackBack 'Всё наоборот'

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

   Input:

   -12:3-4:56-7:8-9:10-

   Output:

   10 9 8 7 56 4 3 12

2. EJudge: Matrix 'Матрица'

   Ввести квадратную «матрицу» — последовательность строк, содержащих целые числа, разделённые пробелами. Вывести номер столбца, сумма элементов в котором наибольшая. Если таких столбцов несколько, вывести самый маленький номер.

   Input:

   12 34 56 78 90
   23 45 67 89  2
   23 65 90 12 45
   13  4 35 46 57
   80 79 68 57 46

   Output:

   2

3. EJudge: Screen 'Экран'

   Написать четыре функции:

   1. screen(width, height, space), которая создаёт «текстовый экран» размером width×height, при этом «пустыми местами» в нём служат символы space. Функция возвращает только что созданный экран.

   2. show(screen), которая выводит экран screen в виде прямоугольника

   3. hline(screen, x0, x1, y, ink), которая заменяет в строке y экрана screen символы на позиции с x0 по x1-1 на строку ink, т. е. «рисует горизонтальную линию»

   4. vline(screen, x, y0, y1, ink), которая заменяет в столбце x экрана screen символы на позиции с y0 по y1-1 на строку ink, т. е. «рисует вертикальную линию»

   Реализация «экрана» — произвольная. Координаты всегда упорядочены, т. е. x0 ⩽ x1 и y0⩽y1, и не выходят за границы экрана.

   S = screen(15, 7, '.')
   vline(S, 3, 2, 6, '|')
   hline(S, 2, 13, 3, '-')
   show(S)

   Input:

   S = screen(15, 7, '.')
   vline(S, 3, 2, 6, '|')
   hline(S, 2, 13, 3, '-')
   show(S)

   Output:

   ...............
   ...............
   ...|...........
   ..-----------..
   ...|...........
   ...|...........
   ...............