Различия между версиями 3 и 4
Версия 3 от 2021-10-23 19:36:49
Размер: 7276
Редактор: FrBrGeorge
Комментарий:
Версия 4 от 2021-10-28 12:38:26
Размер: 7253
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 103: Строка 103:
'''TODO''' тесты

Массивы, они же списки

Замечание: В других языках программирования (например, в Си или C++) слово «список» обозначает довольно сложную в обхождении структуру данных, полное название которой — «связный список», он же linked list. В Python она не используется практически никогда, и термин «список» фактически обозначает «динамический массив»

О массивах вообще

  • Одна большая оперативная память на всю программу — ячейки и адреса
  • Доступ к ячейке — по адресу (фактически — адреса вместо имён)
  • Строка: последовательность ячеек
  • адрес n-го элемента строки = адрес начала строки + n

  • То же самое — для последовательностей любого одного типа:

    • Должны лежать строго подряд в памяти
    • Если один элемент занимает k ячеек, адрес n-го элемента = начало + n * k

  • До и после массива в памяти тоже может что-нибудь быть, поэтому менять его размер нельзя

Это и есть массив!

Python:

  • всевозможные проверки (на выход за пределы, например)
  • возможность менять размер массива
    • свободное место + копирование/удвоение, если оно закончилось
  • возможность хранить в нём произвольные данные (а не только однотипные)
    • в массиве хранятся только идентификаторы объектов (они однотипные!), а сами объекты хранятся где ни попадя
    • эта структура обычно называется «таблица ссылок» но так только хуже понимать)
  • Список
    динамически изменяемый массив произвольных объектов в Python

Кортежи

  • последовательности
  • индексирование / секционирование / for / in, вот это всё

  • Задание: в круглых скобках (иногда и без)

Списки

Первый (кажется) изменяемый объект в нашем курсе!

  • Задаётся квадратными скобками
  • В него можно записывать объекты L[i] = 2345

  • Трюк с несколькими именами одного и того же списка
    • .copy()

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

Основные алгоритмы

  • Проход всего
  • Проход по индексам
  • Поиск первого

Пример: поиск максимума

Не модифицируйте длину списка — не добавляйте и не удаляйте элементы — пока проходите по нему (например, с помощью for). Всегда делайте новый. Помните: append() дёшев, памяти хватит на двоих, а вот запутаться в плавающих индексах проще простого

Про eval(input())

Функция eval() вычисляет значение выражения, которое передаётся ей в виде строки. То есть она запускает интерпретатор Python (так же, как это делаем мы, когда запускаем программу!).

  • Простой пример
    • >>> a = "6"
      >>> b = "8"
      >>> c = a + "*" + b
      >>> c
      '6*8'
      >>> eval(c)
        48
  • То же самое происходит в форматных строках, но в случае eval() всё проще — результат именно такой, каким его вычислил Python:

    >>> type(f"{a} * 2 + {b} // 2")
    <class 'str'>
    >>> type(eval("a * 2 + b // 2"))
    <class 'int'>
  • Из примера выше видно, что, как и в форматных строках, eval() умеет использовать пространства имён (т. е. в нём могут встречаться переменные)

  • Это опасная функция, и её не стоит использовать, если вы не знаете, откуда получены её параметры и что в них содержится — при должной сноровке можно выполнить произвольный кусок программы!
  • Однако она незаменима в домашних заданиях, где правильность ввода гарантируется

Например, вот так начинается программа, в которой сказано «Введите через запятую два числа и строку в кавычках»:

  • x, y, s = eval(input())
  • Допустим, мы вели строку «123, 345, "ASDF"». Если бы такую строку увидел Python, он посчитал бы, что это обычный кортеж из трёх элементов — двух чисел и строки (потому что она в кавычках)

  • Ну так eval(inp) это и делает! Он возвращает кортеж, который раскладывается по трем переменным:

    >>> inp = input()
    123, 456, "ASDF"
    >>> print(inp)
    123, 456, "ASDF"
    >>> res = eval(inp)
    >>> print(res)
    (123, 456, 'ASDF')
    >>> print(type(res))
    <class 'tuple'>
    >>> a, b, s = res
    >>> a
    123
    >>> b
    456
    >>> s
    'ASDF'

Д/З

  1. Прочитать и прощёлкать:
  2. EJudge: PosCount 'Подсчёт Положительных'

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

    Input:

    1, 3, -3, 0, 234, 657
    -2, -4356, -345, 0, -11, -2134123412341234, 0, 0
    777, 2
    how boring!
    Output:

    6
  3. EJudge: NumSearch 'Поиск Числа'

    В первой строке вводится несколько (более одного) чисел через запятую. В последующих строках — произвольный текст. Последняя строка содержит одну точку, это конец ввода. Вывести, сколько раз каждое из этих чисел встречается в тексте. Достаточно воспользоваться строковым методом .count() и подсчитать количество вхождений числа как подстроки; не нужно учитывать, что одно число может встречаться внутри другого, внутри слова и т. п.

    Input:

    123, 2, 777, -8, 2, 100500
    1w21e23qr123rwe34rt5t5
    это кот на клавиатуру 8 раз сел и 22 клавиши нажал!
    777777 7777
    12-8=-123, ой, ошибся…
    .
    Output:

    123: 2
    2: 7
    777: 3
    -8: 1
    2: 7
    100500: 0
  4. EJudge: ThirdsOut 'Третий Лишний'

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

    Input:

    print(squeeze([1, 5, 4, 3, 7, 6, 14, 8, 2]))
    Output:

    [1, 4, 3, 7, 6, 8, 2]
  5. EJudge: BinSearch 'Двоичный поиск'

    Написать функцию, binsearch(x, A), реализующую двоичный поиск элемента x по индексируемой последовательности (списку, кортежу или даже range) A. Гарантировано, что последовательность упорядочена по возрастанию. Функция возвращает True, если $$ x \in A $$ и False в противном случае.

    Input:

    print(binsearch(123, sorted([123, 12, 45, 67, 23, 678, 12345, 4, 23, 768])))
    Output:

    True

Python/GeoPython2021/07_Lists (последним исправлял пользователь FrBrGeorge 2021-10-28 12:38:26)