Различия между версиями 6 и 7
Версия 6 от 2020-10-01 08:53:14
Размер: 4954
Редактор: hbd
Комментарий: Добавлена Задача_1
Версия 7 от 2020-10-01 09:07:51
Размер: 6446
Редактор: hbd
Комментарий: Добавлена Задача_2
Удаления помечены так. Добавления помечены так.
Строка 29: Строка 29:
  * <!> (доформулировать) Задача_2 (на рекурсию): Реализовать функцию бинарного поиска в упорядоченной индексируемой хранимой последовательности
   * Проверить её на строках и кортежах
  * <!> Задача_2: Реализовать рекурсивную функцию бинарного поиска в упорядоченной по неубыванию индексируемой хранимой последовательности.
   * на вход подаётся искомый элемент и последовательность, гарантированно упорядоченная по неубыванию
   * бинарный поиск:
    * смотрим элемент в "середине" последовательности; если элемент равен искомому, то возвращаем его индекс; если элемент меньше искомого, ищем рекурсивно в "хвосте" последовательности; если элемент больше искомого, ищем рекурсивно в "голове" последовательности
    * при рекурсивном поиске, "хвост" и "голова" рассматриваются как новые последовательности
    * если искомый элемент не найден, возвращать (-1)
    * обращайте внимание, что если элемент найден в ходе рекурсивного вызова, его индекс нужно пересчитывать в индекс элемента в исходной последовательности
  * если в последовательности чётное число элементов, "серединой" считается тот из двух средних элементов, у которого меньше индекс
  * проверить функцию на строках и кортежах

04. Функции и замыкание

  • Функция как именованная запись алгоритма
    • duck typing
    • пространство имён и pythontutor.com
      • вызов одной функции из другой
      • {i} написать примитивно-рекурсивную функцию на 4 вызова, пронаблюдать как она работает

    • <!> Задача_0: поиск Парето-фронта в двумерном пространстве

      • пара (x,y) доминируется парой (a,b), если x<=a, y<=b, и верно хотя бы одно из: x<a, y<b

      • написать функцию Pareto, которая:
        • получает на вход набор пар чисел, количество пар заранее не известно
        • находит Парето-фронт, т.е. все пары из заданного набора, каждая из которых не доминируется никакой парой из заданного набора
        • возвращает результат в виде кортежа из найденных пар чисел
      • функция должна поддерживать вызов в формате Pareto(pair_1, pair_2, pair_3, ...), где pair_i -- кортеж из двух чисел
      • допустимо решать задачу путем прохода по набору пар и проверки, доминируется ли очередная пара какой-либо из других пар
    • лямбда-функции (функции-выражения)
      • как работает sorted(…, key=fun)

      • {i} переписать Задачу_2 из прошлого семинара в однострочник с использованием sorted():

        • ввести и отсортировать по возрастанию ключей числовой список, в качестве ключа сравнения использовать остаток от деления x2 на 100
    • <!> Задача_1: написать функцию вычитания двух объектов

      • должно поддерживаться вычитание объектов, для которых вычитание уже определено (целые, вещественные, множества, ...)
      • должно поддерживаться вычитание упорядоченных хранимых последовательностей (кортежей, строк) по следующим правилам:
        • в "разность" должны попасть все элементы "уменьшаемого", которых нет в "вычитаемом"; если элемент встречается в "вычитаемом" хотя бы раз, то он не попадает в "разность"
        • элементы должны располагаться в "разности" в том же порядке, что и в "уменьшаемом"
      • Подсказки:
        • проверять на всех указанных выше типах последовательностей, для которых нужно реализовать вычитание
        • как работает type(object)()?

        • строка обрабатывается чуть-чуть не так, как кортеж (но есть вариант, когда так же)
    • <!> Задача_2: Реализовать рекурсивную функцию бинарного поиска в упорядоченной по неубыванию индексируемой хранимой последовательности.

      • на вход подаётся искомый элемент и последовательность, гарантированно упорядоченная по неубыванию
      • бинарный поиск:
        • смотрим элемент в "середине" последовательности; если элемент равен искомому, то возвращаем его индекс; если элемент меньше искомого, ищем рекурсивно в "хвосте" последовательности; если элемент больше искомого, ищем рекурсивно в "голове" последовательности
        • при рекурсивном поиске, "хвост" и "голова" рассматриваются как новые последовательности
        • если искомый элемент не найден, возвращать (-1)
        • обращайте внимание, что если элемент найден в ходе рекурсивного вызова, его индекс нужно пересчитывать в индекс элемента в исходной последовательности
    • если в последовательности чётное число элементов, "серединой" считается тот из двух средних элементов, у которого меньше индекс
    • проверить функцию на строках и кортежах
  • Замыкание: как образуется, почему изнутри это не так просто, как снаружи?
    • Разбор примера про adder-ы из лекций
  • {i} Функуционал: на вход две функции от одной переменной (f(x) и g(x)) , на выходе — функция от одной переменой h(x)=f(x)+g(x)

  • <!> Задача_3: Функционал-еval()-ище. Написать функцию calc(s, t ,u), которой передаются три строки. Каждая строка — это формула; s и t — над одной переменной x, а u — над двумя переменными x и y. Возвращается функция, которая по заданному x вычисляет u(s(x), t(x)).

    • Например, calc("x", "2*x+1", "x/y") должно возвращать функцию, которая вычисляет $$x / {2x+1}$$

LecturesCMC/PythonIntro2020/Prac/04_FunctionsClosure (последним исправлял пользователь FrBrGeorge 2020-10-07 18:54:34)