Различия между версиями 9 и 10
Версия 9 от 2020-10-01 17:29:53
Размер: 6204
Редактор: FrBrGeorge
Комментарий:
Версия 10 от 2020-10-01 21:18:55
Размер: 8121
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 8: Строка 8:
  * <!> Задача_0: поиск Парето-фронта в двумерном пространстве
   * пара (x,y) доминируется парой (a,b), если x<=a, y<=b, и верно хотя бы одно из: x<a, y<b
   * написать функцию Pareto, которая:
    * получает на вход набор пар чисел, количество пар заранее не известно
    * находит Парето-фронт, т.е. все пары из заданного набора, каждая из которых не доминируется никакой парой из заданного набора
    * возвращает результат в виде кортежа из найденных пар чисел
   * функция должна поддерживать вызов в формате Pareto(pair_1, pair_2, pair_3, ...), где pair_i -- кортеж из двух чисел
   * допустимо решать задачу путем прохода по набору пар и проверки, доминируется ли очередная пара какой-либо из других пар
  * <!> [[#0|Задача_0]]: поиск Парето-фронта в двумерном пространстве
Строка 20: Строка 13:
  * <!> Задача_1: написать функцию вычитания двух объектов
   * должно поддерживаться вычитание объектов, для которых вычитание уже определено (целые, вещественные, множества, ...)
   * должно поддерживаться вычитание упорядоченных хранимых последовательностей (кортежей, списков) по следующим правилам:
    * в "разность" должны попасть все элементы "уменьшаемого", которых нет в "вычитаемом"; если элемент встречается в "вычитаемом" хотя бы раз, то он не попадает в "разность"
    * элементы должны располагаться в "разности" в том же порядке, что и в "уменьшаемом"
   * Подсказки:
    * проверять на всех указанных выше типах последовательностей, для которых нужно реализовать вычитание
    * как работает `type(object)()`?
    * строка обрабатывается чуть-чуть не так, как кортеж (но есть вариант, когда так же)
  * <!> Задача_2: Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.
   * на вход подаётся искомый элемент и последовательность, гарантированно упорядоченная по неубыванию
   * бинарный поиск:
    * смотрим элемент в "середине" последовательности; если элемент равен искомому, то возвращаем `TRUE`; если элемент меньше искомого, ищем рекурсивно в "хвосте" последовательности; если элемент больше искомого, ищем рекурсивно в "голове" последовательности
    * при рекурсивном поиске, "хвост" и "голова" рассматриваются как новые последовательности
    * если искомый элемент не найден, возвращаем `FALSE`
  * если в последовательности чётное число элементов, "серединой" считается тот из двух средних элементов, у которого меньше индекс
  * проверить функцию на строках и кортежах
  * <!> [[#1|Задача_1]]: написать функцию вычитания двух объектов
  * <!> [[#2|Задача_2]]: Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.
Строка 39: Строка 17:
 * {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))`.
 * {i} Функционал: на вход две функции от одной переменной (`f(x)` и `g(x)`) , на выходе — ''функция'' от одной переменой `h(x)=f(x)+g(x)`
 * <!> [[#3|Задача_3]]: Функционал-еval()-ище.

== Задачи ==
 1.#0 <<Anchor(0)>>Поиск Парето-фронта в двумерном пространстве
  * пара (x,y) доминируется парой (a,b), если x<=a, y<=b, и верно хотя бы одно из: x<a, y<b
  * написать функцию Pareto, которая:
   * получает на вход набор пар чисел, количество пар заранее не известно
   * находит Парето-фронт, т.е. все пары из заданного набора, каждая из которых не доминируется никакой парой из заданного набора
   * возвращает результат в виде кортежа из найденных пар чисел
  * функция должна поддерживать вызов в формате Pareto(pair_1, pair_2, pair_3, ...), где pair_i -- кортеж из двух чисел
  * допустимо решать задачу путем прохода по набору пар и проверки, доминируется ли очередная пара какой-либо из других пар
 {{{#!pycon
>>> Pareto((32, 38), (10, 14), (19, 44), (31, 31), (17, 33), (53, 6), (48, 9), (6, 38), (30, 49), (52, 30), (7, 30), (45, 45), (21, 51), (7, 49), (11, 23))
((53, 6), (30, 49), (52, 30), (45, 45), (21, 51))
>>> Pareto((1,2), (3,4), (2,2), (4,3), (7,0), (1,8))
((3, 4), (4, 3), (7, 0), (1, 8))
 }}}
 1. <<Anchor(1)>>Написать функцию вычитания двух объектов
  * должно поддерживаться вычитание объектов, для которых вычитание уже определено (целые, вещественные, множества, ...)
  * должно поддерживаться вычитание упорядоченных хранимых последовательностей (кортежей, списков) по следующим правилам:
   * в "разность" должны попасть все элементы "уменьшаемого", которых нет в "вычитаемом"; если элемент встречается в "вычитаемом" хотя бы раз, то он не попадает в "разность"
   * элементы должны располагаться в "разности" в том же порядке, что и в "уменьшаемом"
  * Подсказки:
   * проверять на всех указанных выше типах последовательностей, для которых нужно реализовать вычитание
   * как работает `type(object)()`?
   * строка обрабатывается чуть-чуть не так, как кортеж (но есть вариант, когда так же)
 {{{#!pycon
>>> SUB(123, 45)
78
>>> SUB((4,2,7,4,6,87,7), (2,54,67,3,2))
(4, 7, 4, 6, 87, 7)
>>> SUB(["Q", "WE", "RTY"], ["WE", "ZZ"])
['Q', 'RTY']
>>> SUB({2,4,6,8}, {1,2,3,4})
{8, 6}
>>> SUB("qwretyqwerty", "qawsqas")
'retyerty'
 }}}
 1. <<Anchor(2)>>Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.
  * на вход подаётся искомый элемент и последовательность, гарантированно упорядоченная по неубыванию
  * бинарный поиск:
   * смотрим элемент в "середине" последовательности; если элемент равен искомому, то возвращаем `TRUE`; если элемент меньше искомого, ищем рекурсивно в "хвосте" последовательности; если элемент больше искомого, ищем рекурсивно в "голове" последовательности
   * при рекурсивном поиске, "хвост" и "голова" рассматриваются как новые последовательности
   * если искомый элемент не найден, возвращаем `FALSE`
 * если в последовательности чётное число элементов, "серединой" считается тот из двух средних элементов, у которого меньше индекс
 * проверить функцию на строках и кортежах
 {{{#!pycon
>>> Bisect("a", "abcdfghklmoprsyz")
True
>>> Bisect("z", "abcdfghklmoprsyz")
True
>>> Bisect("l", "abcdfghklmoprsz")
True
>>> Bisect(6, (3,8,12,6,4,8,234,8,9))
False
>>> Bisect(6, sorted((3,8,12,6,4,8,234,8,9)))
True
>>> Bisect(6, (1,23,234,2354,25667))
False
>>> Bisect(6, range(2,17,2))
True
>>> Bisect(6, range(2,18,2))
True
>>> Bisect(6, range(3,18,2))
False
 }}}
 1. <<Anchor(3)>>Функционал-еval()-ище. Написать функцию `calc(s, t ,u)`, которой передаются три строки. Каждая строка — это формула; `s` и `t` — над одной переменной `x`, а `u` — над двумя переменными `x` и `y`. Возвращается ''функция'', которая по заданному `x` вычисляет `u(s(x), t(x))`.
Строка 42: Строка 86:
  {{{#!pycon
>>> F = Calc("x", "2*x+1", "x/y")
>>> F(100)
0.4975124378109453
>>> F(0.1)
0.08333333333333334
>>> from math import *
>>> F = Calc("sin(x)**2", "cos(x)**2", "x+y")
>>> F(123)
1.0
>>> F(0.123)
1.0
>>> cos = lambda x: -x
>>> sin = lambda x: x/2
>>> F(123)
18911.25
>>> F = Calc("len(s)", "max(s)", "x+y")
>>> F((1,2,34,56,12,3,1,7))
64
  }}}

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

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

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

    • лямбда-функции (функции-выражения)
      • как работает sorted(…, key=fun)

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

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

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

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

  • <!> Задача_3: Функционал-еval()-ище.

Задачи

  1. Поиск Парето-фронта в двумерном пространстве

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

    • написать функцию Pareto, которая:
      • получает на вход набор пар чисел, количество пар заранее не известно
      • находит Парето-фронт, т.е. все пары из заданного набора, каждая из которых не доминируется никакой парой из заданного набора
      • возвращает результат в виде кортежа из найденных пар чисел
    • функция должна поддерживать вызов в формате Pareto(pair_1, pair_2, pair_3, ...), где pair_i -- кортеж из двух чисел
    • допустимо решать задачу путем прохода по набору пар и проверки, доминируется ли очередная пара какой-либо из других пар
    >>> Pareto((32, 38), (10, 14), (19, 44), (31, 31), (17, 33), (53, 6), (48, 9), (6, 38), (30, 49), (52, 30), (7, 30), (45, 45), (21, 51), (7, 49), (11, 23))
    ((53, 6), (30, 49), (52, 30), (45, 45), (21, 51))
    >>> Pareto((1,2), (3,4), (2,2), (4,3), (7,0), (1,8))
    ((3, 4), (4, 3), (7, 0), (1, 8)) 
  2. Написать функцию вычитания двух объектов

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

      • строка обрабатывается чуть-чуть не так, как кортеж (но есть вариант, когда так же)
    >>> SUB(123, 45)
    78
    >>> SUB((4,2,7,4,6,87,7), (2,54,67,3,2))
    (4, 7, 4, 6, 87, 7)
    >>> SUB(["Q", "WE", "RTY"], ["WE", "ZZ"])
    ['Q', 'RTY']
    >>> SUB({2,4,6,8}, {1,2,3,4})
    {8, 6}
    >>> SUB("qwretyqwerty", "qawsqas")
    'retyerty'
  3. Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.

    • на вход подаётся искомый элемент и последовательность, гарантированно упорядоченная по неубыванию
    • бинарный поиск:
      • смотрим элемент в "середине" последовательности; если элемент равен искомому, то возвращаем TRUE; если элемент меньше искомого, ищем рекурсивно в "хвосте" последовательности; если элемент больше искомого, ищем рекурсивно в "голове" последовательности

      • при рекурсивном поиске, "хвост" и "голова" рассматриваются как новые последовательности
      • если искомый элемент не найден, возвращаем FALSE

  4. если в последовательности чётное число элементов, "серединой" считается тот из двух средних элементов, у которого меньше индекс
  5. проверить функцию на строках и кортежах
    >>> Bisect("a", "abcdfghklmoprsyz")
    True
    >>> Bisect("z", "abcdfghklmoprsyz")
    True
    >>> Bisect("l", "abcdfghklmoprsz")
    True
    >>> Bisect(6, (3,8,12,6,4,8,234,8,9))
    False
    >>> Bisect(6, sorted((3,8,12,6,4,8,234,8,9)))
    True
    >>> Bisect(6, (1,23,234,2354,25667))
    False
    >>> Bisect(6, range(2,17,2))
    True
    >>> Bisect(6, range(2,18,2))
    True
    >>> Bisect(6, range(3,18,2))
    False
  6. Функционал-е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}$$

      >>> F = Calc("x", "2*x+1", "x/y")
      >>> F(100)
      0.4975124378109453
      >>> F(0.1)
      0.08333333333333334
      >>> from math import *
      >>> F = Calc("sin(x)**2", "cos(x)**2", "x+y")
      >>> F(123)
      1.0
      >>> F(0.123)
      1.0
      >>> cos = lambda x: -x
      >>> sin = lambda x: x/2
      >>> F(123)
      18911.25
      >>> F = Calc("len(s)", "max(s)", "x+y")
      >>> F((1,2,34,56,12,3,1,7))
      64

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