6204
Комментарий:
|
8121
|
Удаления помечены так. | Добавления помечены так. |
Строка 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
- вызов одной функции из другой
написать примитивно-рекурсивную функцию на 4 вызова, пронаблюдать как она работает
Задача_0: поиск Парето-фронта в двумерном пространстве
- лямбда-функции (функции-выражения)
как работает sorted(…, key=fun)
переписать Задачу_2 из прошлого семинара в однострочник с использованием sorted():
- ввести и отсортировать по возрастанию ключей числовой список, в качестве ключа сравнения использовать остаток от деления x2 на 100
Задача_1: написать функцию вычитания двух объектов
Задача_2: Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.
- Замыкание: как образуется, почему изнутри это не так просто, как снаружи?
- Разбор примера про adder-ы из лекций
Функционал: на вход две функции от одной переменной (f(x) и g(x)) , на выходе — функция от одной переменой h(x)=f(x)+g(x)
Задача_3: Функционал-еval()-ище.
Задачи
Поиск Парето-фронта в двумерном пространстве
пара (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))
Написать функцию вычитания двух объектов
- должно поддерживаться вычитание объектов, для которых вычитание уже определено (целые, вещественные, множества, ...)
- должно поддерживаться вычитание упорядоченных хранимых последовательностей (кортежей, списков) по следующим правилам:
- в "разность" должны попасть все элементы "уменьшаемого", которых нет в "вычитаемом"; если элемент встречается в "вычитаемом" хотя бы раз, то он не попадает в "разность"
- элементы должны располагаться в "разности" в том же порядке, что и в "уменьшаемом"
- Подсказки:
- проверять на всех указанных выше типах последовательностей, для которых нужно реализовать вычитание
как работает 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'
Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.
- на вход подаётся искомый элемент и последовательность, гарантированно упорядоченная по неубыванию
- бинарный поиск:
смотрим элемент в "середине" последовательности; если элемент равен искомому, то возвращаем TRUE; если элемент меньше искомого, ищем рекурсивно в "хвосте" последовательности; если элемент больше искомого, ищем рекурсивно в "голове" последовательности
- при рекурсивном поиске, "хвост" и "голова" рассматриваются как новые последовательности
если искомый элемент не найден, возвращаем FALSE
- если в последовательности чётное число элементов, "серединой" считается тот из двух средних элементов, у которого меньше индекс
- проверить функцию на строках и кортежах
>>> 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
Функционал-е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