Спасибо за лекцию. Эх, вернуть бы те времена, когда я мог учиться и не работать, я бы не одной лекции не пропустил. Сейчас приходиться и работать и учиться и на работе учиться. Но с такими преподавателями у меня есть шанс.
подача у препода хорошая, но этот тупняк при объяснении просто всё ломает. Лучше бы остановился и всё продумал на перёд, чем эти вечные "а, нет, извините, ой, подождите" и т.д.
@@gerhardshreder2391 да иди ты в баню. Всегда бесят такие критики, которые сами хер чего сделали. Тот кто пробовал что-то сделать сам, будет с уважением относится к труду другого.
@@Самисвоимируками-я4ь боже мой, без недели 2020ый год на дворе, а в мире оказывается всё еще живут люди с таким ограниченным мышлением. Ты, я надеюсь, никогда в жизни не критиковал власть, футбол, кино, книги? А то я сильно сомневаюсь, что ты великий реформатор, игрок года FIFA, гениальный режиссер и писатель в одном лице. Что касается лекции - у препода есть конкретные косяки и я имею полное право о них здесь высказываться. Если тебя это бесит - это исключительно твои проблемы.
Тайм-коды: генерация всех перестановок 0:49 генерация комбинаторных объектов 5:25 упрощенная задача - все числа от 00...0 до N-1 N-1...N-1. Перебор всевозможных состояний у каждой ячейки 7:00 рекурсивная генерация всех чисел длины М # def generate_numbers(N:int, M:int, prefix = None) 14:48 prefix = prefix or [] # если не первое и не второе, то значение второго 16:15 в and и or ленивое выполнение (может проверять Только первое значение) 23:08 рекурсивный вызов в цикле 27:14 алгоритм генерации всех чисел для N-ричной системы счисления 29:50 в Питоне можно создавать пустые списки и конкатенировать списки 32:17 алгоритм генерации всех чисел без цикла для двоичной системы счисления 36:33 алгоритм генерации всех чисел в цикле для двоичной системы счисления 39:19 алгоритм генерации всех перестановок (рекурсивная) # def generate_permutations(N:int, M:int, prefix = None) 46:29 continue 49:01 однопроходный алгоритм 53:11 *prefix # раскрытие элементов списка в параметр функции не в список со скобками, а через пробел 58:32 рекурсивные сортировки (быстрые сортировки): сортировка Тони Хоара и сортировка слиянием 59:47 их характеристики 1:04:05 иллюстрация сортировка Хоара 1:11:00 иллюстрация сортировка слиянием. Деление напополам и слияние уже отсортированных половинок
Хорошо, что в 2к18 к таким преподавателям есть доступ у всех. Когда я учился в универе, youtube не существовал, а дипломы сдавали на дискетках, а до МФТИ было 10000 км от моего универа. Слава Гуглу, слава RUclips, слава Питону, Гвидо и Тимофею)))).
выдающийся базовый курс Python! профессор очень увлечен и занят. Самая сложная часть цикла лекций в том, что они на русском языке. Я не говорю по-русски - я учусь. Спасибо, профессор, и спасибо Google Translate!
@@nicholasspezza9449 Вообще-то этот курс лекций рассчитан так же и на тех, кто не знаком с Python, поэтому с первых лекций постепенно рассказывается и про простейший синтаксис.
Удивительно, что на Ваши лекции студенты не ходят. Когда учился в СПбГТИ(ТУ), у нас в принципе таких преподавателей (которые любят свой предмет и умеют супер качественно его преподнести) не было, к сожалению. Сейчас мне 31, учусь заново) Спасибо Вам за труды!
Колоссальная учебная нагрузка на студентов физтеха приводит к соблазну проспать те предметы, которые можно выучить самостоятельно. Но я думаю, что посещаемость у Тимофея Фёдоровича всё равно очень хорошая.
Рекурсию для N=2, M=2 понял, только когда нарисовал стек вызовов, и бегал глазами по стеку с этими 0 и 1. Потому что продолжать не понимая рекурсию невозможно. Можно не понять формулу которая будет в рекурсии, но визуализировать стек вызовов, отработать условие ретурна в голове надо обязательно, иначе не понять что куда ушло, что кого вызвал и как это работает. На примере генерации всех числе N=2, M=2 можно понять, ведь математической сложности там нет, а рекурсивная витиеватость там есть, по стеку вызов за вызовом, ретурн. Уже не помню, что тут про стек рассказывали, я немного в другом месте смотрел. Однако поверить просто мало, а понять уже пришлось зарисовывать древовидную последовательную схему вызовов, которая являлась стеком.
@@prototyperail-gun5589 он, видимо, просто не знает. В этом и есть одна из ролей родителя по отношению к детям, в случае обдуманной подготовки-воспитания отпрыска.
Как-то замудрено реализовано генерация чисел. prefix=None - лишнее, prefix = prefix or [] - лишнее, прилеплять к концу списка значение а потом отлеплять - лишнее. Во-первых это лишнее, во-вторых - это "программистские хитрости" которые сломали мозг бедным студентам. Вот просто и понятно, результат такой-же: def generate_numbers(N:int, M:int, prefix = []): if M==0: print(prefix) return for digit in range(N): generate_numbers(N, M-1, prefix + [digit]) не надо использовать .append который "портит" исходный список, надо использовать конкатенацию списков, что и показано в реализации выше. Кроме того - не рассказано "на пальцах" принцип алгоритма, а сразу началась реализация в коде. Я несколько раз отматывал назад на пересмотр чтобы понять принцип алгоритма, а у студентов все в реальном времени идет.
я вот тоже не понял, зачем отдельно добавлять окончание, запускать рекурсию и тут же убирать digit , если можно запустить рекурсию с нужным окончанием, после выпадения из рекурсии окончания уже не будет. Разве что специально для студентов это сделано, чтобы те поняли, как это работает. Хотя ваш вариант проще для понимания, на мой взгляд.
@@danxai На самом деле, в варианте с использованием методов .append и .pop (то есть прилепливание и отлепливание окончания списка) мы гоняем по дереву рекурсии один и тот же объект - список, только меняем его длину. А в предложенном варианте (конкатенация списка и последнего элемента в вызове рекурсии) в каждом вызове рекурсии создается новый список(который уничтожается при возврате из рекурсии), что увеличивает время и забивает память (стек). Но про эти ограничения ничего не сказано в постановке задачи. И по скорости я разницы не заметил. А вот использование None вместо [ ] вообще непонятно зачем.
@@eugenedukatta9355 Подскажите пожалуйста, а как в этом алгоритме получаемые числа не выводить на экран, а запоминать в списке? Пробовал добавить первой строкой в функции создание пустого массива result = [] if M == 0: result.append(prefix) return. Так не получается.
Как говорят философы, сложное - это сложенное из простого. Пока есть только знание о простом, но нет умения (а тем более навыка) оперировать этим простым, то восприятие сложного - трудно (то есть трудозатратно, напрягаться надо). Надо после (а иногда лучше и до) прослушивания лекции поразбираться с каждым из её элементов: - постановкой задачи; - алгоритмом; - синтаксисом языка; - реализацией алгоритма на языке; - графическими представлениями задач; - графическими пошаговым представлениями действий программы. Если сознательно формировать навык понимания, то со временем станет легче.
Генерация перестановок в лексикографическом порядке с помощью ЦИКЛОВ: def f(n): # n - натуральное число, где n>1 обозначающее количество элементов в массиве A=list(range(n)) while True: print(A) i=n-2 while A[i]>=A[i+1]: i=i-1 if i==-1: return j=n-1 while A[j]
сортировка пузырька и грузила (модифицированная пузырьковая сортировка) в цикле ищется минимальный и максимальный элемент массива после чего они обмениваются (при необходимости) с крайними элементами (минимальный в начало, максимальный - в конец) после чего область обработки (срез массива) уменьшается на 1 с краев, т.к. элементы там уже отсортированные. количество итераций повторять до числа, равного половине длинны массива. сортировка массива упорядоченного по убыванию требует всего N//2 обменов # ========================================================= def my_sort(arr): for j in range(0,len(arr)//2): min=j # minimal index max=len(arr)-j-1 # maximal index for i in range(j,len(arr)-j): if arr[min] > arr[i]: min = i if arr[max] < arr[i]: max = i if min==i and max==j:#ловушка двойного обмена, в сумме не дающая перестановки arr[min], arr[max]=arr[max],arr[min] else: if max==j:#ловушка обмена затрагивающая перестановку минимального элемента, в которую входит максимальный max=(min) if min!=j: #не переставлять если элемент на месте arr[j], arr[min] = arr[min], arr[j] if max!=len(arr)-j-1: #не переставлять если элемент на месте arr[len(arr)-j-1], arr[max] = arr[max], arr[len(arr)-j-1] return(arr) import random print("\033[H\033[J", end="") # проверка работоспособности алгоритма switch=True while switch: print(" =Start= ") unsort = [random.randint(10,99) for x in range (random.randint(30,50))] print(unsort) check=my_sort(unsort) print(check) for i in range(len(check)-1): if (check[i] - check[i+1]) > 0: print("error! len: ",len(check)," pos: ",i," " ,check[i],">" ,check[i+1]) switch=False
@@vp_arth так всмысле необходимое, я говорю как убрать лишнее и сделать более понятный код. Вместо выражение if в строчке присвоения просто проверять на существование переменной M
Мне казалось, что до prefix.pop не дойдёт никогда, попробовал убрать строчку- понял, попробовал вернуть и добавить перед этим строчку print( 'I am here ") - понял всё) Строчку prefix = prefix or [ ] можно вообще убрать, а в аргументы функции поставить по умолчанию prefix = [ ]. Работает без ущерба.
def find(number, A): """ search for number in A return True if found False if not found """ flag = False for x in A: if number == x: flag = True break return flag def generate_permutations(N:int, M:int=-1, prefix=None): """ generation all with N digits in M positions with prefix = prefix """ M = N if M == -1 else M prefix = prefix or [] if M == 0: # print(prefix) # print(*prefix) print("") for i in range(0, N): print(prefix[i], end="") return for number in range(1, N+1): if find(number, prefix): continue prefix.append(number) generate_permutations(N, M-1, prefix) prefix.pop() generate_permutations(3, 3)
Что-то как-то мудрено объясняется принцип перестановки. Не проще провести аналогию с кодовым замком TSA (на чемоданах такой ставят)? А вывод - это все возможные комбинации. Соответственно, N = 10 - цифры от 0 - 9 на каждом цилиндре, M - это количество цилиндров с цифрами, ну а префикс - это наш счетчик, который мы выводим на каждой итерации - печатаем комбинацию (список). Для лучшей визуализации, можно бы было запускать отладку и показывать выполнение кода и значения переменных по шагам. А алгоритм хитро написан - полезно знать, спасибо.
Вообще-то тема про рекурсию. И это пример задачи, которую МОЖНО свести к рекурсивному решению. Естественно, у более опытных "алгоритмщиков" появляется желание всю эту возню с префиксом и рекурсией "упростить" - но лекцию-то читают не для них, а для тех, кому нужно понять, что такое рекурсия :)
Спасибо. Смотрю на x2.75 скорости. Пришлось несколько раз пересматривать 22:05 до 22:10, все время слышал "Я должен единичку туда за'append'ить" на русском, почему-то.
в принципе можно с f форматированиемм и со строкой сделать) def gen_number(n, m, prefix=""): if m == 0: print(prefix) return for i in range(n): gen_number(n, m-1, f"{prefix}{i}")
57:10 Чет у меня пока естественно это не получается это осознать😄. Сложно в голове отслеживать все эти погружения, хочется узнать, что код внутри делает, даже по дебагу сложновато
В Гарварде есть такой курс под названием CS50. Его так же смотрят и онлайн. Так вот русские там часто пишут - вот это преподаватель, не то что наши... И наши есть такие же ))
Чтобы попрактиковаться в написании однопроходных алгоритмов, чисто в образовательных целях. Лектор об этом говорил. Конечно, и лучше, и проще, было бы сделать так, как вы написали. Получили бы тот же результат, только без написания велосипедов.
prefix.append(digit) это метод. Он берет список (в данном случае prefix), лепит к нему новый элемент в хвост (в данном случае digit) при этом список становится измененным, и еще(!) возвращает(внимание!!!) результат None. Когда вы передаете в функцию prefix.append(digit), на самом деле передается None, хотя и сам список prefix при этом увеличивается на элемент digit.
Здраствуйте, скажите пожалуйста в функции генерации всех перестановок (def generate_permutations), вместо дополнительной функции (def find) можно воспользоваться оператором in ?
я ещё нуб в питоне, но что-то я не понял, зачем была нужна это котовасия с написанием функции find на 52:00, если было достаточно написать в функции generate_permitations: if number in prefix: continue # это выражением само по себе бы выдало True или False. Может это было в целях обучения?
В шапке у него присваевается Prefix = None, чтобы переменная была объявлена. Он не может в шапке сделать Prefix = [], потому что поведение функции будет совсем другим. А в части Prefix = Prefix or [] ему уже нужно, чтобы префикс или сохранил свое значение или стал пустым массивом.
Операция or (а также and) - это логическая операция, и вообще она должна работать с логическими значениями (типа True и False) и возвращать логическое значение тоже. Но язык так реализован, что каждое значение логической операции неявно преобразуется к логическому типу с помощью функции bool(). То есть выражение Prefix = Prefix or [ ] - реализуется как Prefix = bool(Prefix) or bool([ ]). А все "пустые" значения преобразуются в False: bool(None), bool(False), bool(0), bool([ ]), bool(), bool(''), bool(""), bool({}), bool(()) - это все False. Второй факт - если в операции or первый (левый) операнд равен False то он вычисляет следующий операнд и даже не вникая в его логическое значение - возвращает его целиком в том виде в каком он представлен. Так как bool(None)==False то он его пропускает, далее вычисляет и возвращает второй операнд [ ]. То же самое для if () и while().
@@stanislavch5323 это все лишнее. В шапке надо сделать prefix = [ ], а в рекурсивный вызов функции передавать prefix + [digit] И все прекрасно работает - проверено.
@@eugenedukatta9355 Help! Параметр (префикс) передан как None, при рекурсии он меняет свое значение как глобальная переменная или при каждом вызове сбрасывается в None?
@@istra3265 В видео, функция выглядит так: def generate_numbers(N:int, M:int, prefix = None): здесь параметр prefix не передается как None. prefix = None означает значение по умолчанию, которое принимает параметр, если параметр не передается явно. В примере, (первый) раз функция вызывается без параметра prefix и он в первом вызове принудительно принимает значение по умолчанию = None. В первом вызове срабатывает строка "prefix = prefix or []" и значение prefix становится [] то есть пустым списком. В следующих (рекурсивных) вызовах , строка "prefix = prefix or []" не меняет значения prefix В последующие (рекурсивные) вызовы параметр prefix передается явно, его новое значение вычисляется до рекурсивного вызова в строке "prefix.append(digit)" - список prefix удлиняется новым числом в конце списка и передается далее по рекурсии. prefix в каждом вызове это разные переменные (локальная переменная)
А зачем переопределять переменную списка вот этим prefix = prefix or [ ] ? Я сразу в переменную поставил дефолтное значение prefix=[ ] и всё работает точно также
def subs_char(Names:list, letter:str, num:int): for name in Names: for idx, char in enumerate(name): if type(char) == str and char == letter: name[idx] = num def check_ford_task(prefix): Names=[['g','e','r','a','l','d'],['d','o','n','a','l','d'],['r','o','b','e','r','t']] table = ['t', 'd', 'e', 'g', 'l', 'n', 'o', 'r','a', 'b'] for idx, char in enumerate(table): subs_char(Names, char,prefix[idx]) for idx, name in enumerate(Names): Names[idx] = int("".join(str(num) for num in name)) if Names[0] + Names[1] == Names[2]: print('gerald = {}'.format(Names[0])) print('donald = {}'.format(Names[1])) print('robert = {}'.format(Names[2])) return True return False def generate_permutation(N:int, M:int=-1, prefix=None): M=N if M == -1 else M prefix = prefix or [] if M == 0: if check_ford_task(prefix): import sys sys.exit() return for number in range(0, N): if number in prefix: continue prefix.append(number) generate_permutation(N, M-1, prefix) prefix.pop() map = [0, 5] # d =5, t = 0 generate_permutation(10,8,map)
либо я не догоняю, либо алгоритм перестановок возможных чисел не верный. На каждой итерации алгоритм проходится по ВСЕМ числам из системы счисления, благодаря чему 1) числа повторяются (противоречит 2:28), 2) количество перестановок из трех чисел должно быть: 1х2х3 = 6, алгоритм же выдает 27 вариантов (3 варианта на 1ой позиции Х 3 варианта на 2ой позиции Х 3 варианта на 3ей позиции)
Нее, рекурсия, не просто зашла (( Ну не то чтобы принцип сложный, нет здесь все понятно, но когда дело доходить до вызова в цикле, не сразу в голове сложилось, лично мне не хватило детального разбора в какой момент какой рекурентный случай в какой ячейке будет генерировать какое число. P.S. лекции слушаю в дороге, нет возможности тут же экспериментировать, это конечно, Очень сильно усложняет процесс обучения, но что имеем (((.. Короче пока спокойно не сел и не переслушал еще как минимум дважды не разобрался За лекции низкий поклон!
самое забавное что нам преподавали все что в лекциях больше 20 лет назад (первый выпуск по ИТ специальности одного института). с годами все забылось, в сейчас зато вспоминается и легко понимаешь про что речь.
Как сделать чтобы prefix не печатался а ретурнился (извиняюсь)? Просто return prefix не работает, дает None. Другими словами, как результаты загнать в переменную?
Объясните, пожалуйста, по поводу момента где, лектор говорит, что в аргумент функции нельзя передать пустой список, потому что в таком случае "он сгенерится один раз" и останется одним и тем тем же. ruclips.net/video/2XFaK3bgT7w/видео.html Попробовал передать в prefix=[ ] - результат выполнения функции не изменился
def permutations(lst): return [lst] if len(lst) == 1 else \ [[el]+p for el in lst for p in permutations(list(filter(lambda x: x != el, lst)))] print(permutations([1, 2, 3]))
Поставил на паузу на 19:08, записал. Пытаюсь включить несколько раз - ничего. Потом замечаю, что что-то не так. Глаза у Тимофея двигаются. Стало страшно.
def generate_number(N: int, M: int, prefix=None): prefix = prefix or [] if M == 0: print(prefix) return for digit in range(N): prefix.append(digit) generate_number(N, M - 1, prefix) prefix.pop() generate_number(3, 3) Не могу въехать, почему в то время когда M>0 не срабатывает prefix.pop() но проход по prefix.pop() происходит при М==0
Не буду утверждать ничего об ожидаемых прорывах отечественной школы программирования, хотя лекции качественные. А вот в обороноспособности нашей страны нет решительно никаких сомнений! С такими солдатиками для опытов по сортировкам нам ничего не страшно! Ура, товарищи! (если что, это легкая ирония, не отражающая реального положения дел в ВПК)
Вот реально с этим prefix.pop() было сложно. Пришлось тормознуть видео, и тупо вручную накидать алгоритм, чтобы понять зачем выкидывать последний элемент из массива. Думаю, у студентов на лекции те же проблемы.
И даже эта функция не объективна, потому что чем дальше - сложнее тема. Из-за этого оставшиеся начинают пересматривают видео. То есть фактически оставшихся даже ещё меньше, чем просмотров))
Если написать пустой список среди списка переменных, то он создается только один раз, и для всех вызовов он будет общим, и туда будут попадать элементы от всех вызовов.
Все верно, строка prefix=prefix or [] здесь лишняя можно было обойтись значением по умолчанию. Объект prefix ссылочного типа и в каждом вызове функции мы ссылаемся на один и тот же список, поэтому необходимо удалять после вызова функции добавленный элемент. Можно тело цикла реализовать иначе: gen_nums(n, m - 1, [*prefix, i]) тогда на каждый вызов функции будет создаваться новый список с копированием текущего содержимого списка prefix и добавлением в конец следующего числа.
В данной реализации в prefix и так храниться один общий для всех рекуррентных вызовов функции список, так как строка prefix=prefix or [] отработает ровно один раз, что эквивалентно параметру по умолчанию
Это ведёт преподаватель, а не программист. Боюсь у него это просчитано уже много-много раз (аж надоело) и он тупо думает над тем как нас заинтриговать(потому и так внимательно в зал поглядывает(жертву ищет)) чтобы думали. Как идеально решается эта задача см. в методичке (у старших курсов). Не удивлюсь когда узнаю, что есть ещё пара возможно скрытых видеокамер, которые снимают аудиторию.
Есть знающие люди в комментах? Как реализовать этот рекурсивный код в виде генератора чисел, так чтобы это был генератор, а не просто печаталка? Т.е. чтобы функция что-то возвращала и я мог перебирать эти значение. Пыжился, пытался использовать yield prefix в базовом случае и yield from gen_bin(length, prefix + f'{i}'), но ничего не работает. Можно конечно вместо принта все в глобальный список складывать, но это вроде как бэд практис, есть ли более элегантное решение?
Сортировка Хоара - лучший случай n log^2 n Сортировка слиянием - n log n Сортировка Хоара же быстрее выходить должна, почему здесь на доске одинаковые значения
Спасибо за лекцию. Эх, вернуть бы те времена, когда я мог учиться и не работать, я бы не одной лекции не пропустил. Сейчас приходиться и работать и учиться и на работе учиться. Но с такими преподавателями у меня есть шанс.
так рил топчик
подача у препода хорошая, но этот тупняк при объяснении просто всё ломает. Лучше бы остановился и всё продумал на перёд, чем эти вечные "а, нет, извините, ой, подождите" и т.д.
@@gerhardshreder2391 да иди ты в баню. Всегда бесят такие критики, которые сами хер чего сделали. Тот кто пробовал что-то сделать сам, будет с уважением относится к труду другого.
@@Самисвоимируками-я4ь боже мой, без недели 2020ый год на дворе, а в мире оказывается всё еще живут люди с таким ограниченным мышлением. Ты, я надеюсь, никогда в жизни не критиковал власть, футбол, кино, книги? А то я сильно сомневаюсь, что ты великий реформатор, игрок года FIFA, гениальный режиссер и писатель в одном лице. Что касается лекции - у препода есть конкретные косяки и я имею полное право о них здесь высказываться. Если тебя это бесит - это исключительно твои проблемы.
@@gerhardshreder2391 Да ты прав мне как-то пофиг на твой высер, просто считаю что ты нихера не сделал, а мычишь вот и все.
Тайм-коды: генерация всех перестановок
0:49 генерация комбинаторных объектов
5:25 упрощенная задача - все числа от 00...0 до N-1 N-1...N-1. Перебор всевозможных состояний у каждой ячейки
7:00 рекурсивная генерация всех чисел длины М # def generate_numbers(N:int, M:int, prefix = None)
14:48 prefix = prefix or [] # если не первое и не второе, то значение второго
16:15 в and и or ленивое выполнение (может проверять Только первое значение)
23:08 рекурсивный вызов в цикле
27:14 алгоритм генерации всех чисел для N-ричной системы счисления
29:50 в Питоне можно создавать пустые списки и конкатенировать списки
32:17 алгоритм генерации всех чисел без цикла для двоичной системы счисления
36:33 алгоритм генерации всех чисел в цикле для двоичной системы счисления
39:19 алгоритм генерации всех перестановок (рекурсивная) # def generate_permutations(N:int, M:int, prefix = None)
46:29 continue
49:01 однопроходный алгоритм
53:11 *prefix # раскрытие элементов списка в параметр функции не в список со скобками, а через пробел
58:32 рекурсивные сортировки (быстрые сортировки): сортировка Тони Хоара и сортировка слиянием
59:47 их характеристики
1:04:05 иллюстрация сортировка Хоара
1:11:00 иллюстрация сортировка слиянием. Деление напополам и слияние уже отсортированных половинок
Красава
.rmrr. r.rmnrmr.n...n6rmmmrmmmnmb..n,mmnon
.?
Krn
Nm..rr.nm.!rn.nmn
Rmrmrr,Rmrmrr m.rm nrmnr.n?,rmr.rm..r.rm..m,r nnnnnmmnn r.
Nr
Mrm.nmrrmrn.n
Rmrrmrnmn
.r
.m
R.nrnmhmn.rn.mrn.r
Mrmrmn.rmrn...nr.nmmr,.nmm
M.,r.
M..m.rm.nm.rm.m..nmm,rm,r..r.rmnrmnrmmrm.n
R,.nn
Mmmbrnr.n.mr
я как те студенты, не сразу врубилась в фунццию перебора, но я-то могу остановить видео. Му-Ха-Ха!!!
Спасибо за лекцию!
Хорошо, что в 2к18 к таким преподавателям есть доступ у всех. Когда я учился в универе, youtube не существовал, а дипломы сдавали на дискетках, а до МФТИ было 10000 км от моего универа. Слава Гуглу, слава RUclips, слава Питону, Гвидо и Тимофею)))).
"дипломы сдавали на дискетках"... охххх... были времена когда дипломы сдавали написанными рукой на бумаге!
выдающийся базовый курс Python! профессор очень увлечен и занят. Самая сложная часть цикла лекций в том, что они на русском языке. Я не говорю по-русски - я учусь. Спасибо, профессор, и спасибо Google Translate!
Чушь написал недалекий иностранец. Это не базовый курс по Python, тут уже его надо знать, т.к. здесь учат алгоритмам.
@@nicholasspezza9449 Вообще-то этот курс лекций рассчитан так же и на тех, кто не знаком с Python, поэтому с первых лекций постепенно рассказывается и про простейший синтаксис.
wow, you’re good, good luck
Тимофей Федорович, спасибо за Ваш труд!
Принцип работы генератора чисел очень напомнил механизм работы одометра.
Удивительно, что на Ваши лекции студенты не ходят. Когда учился в СПбГТИ(ТУ), у нас в принципе таких преподавателей (которые любят свой предмет и умеют супер качественно его преподнести) не было, к сожалению. Сейчас мне 31, учусь заново)
Спасибо Вам за труды!
Колоссальная учебная нагрузка на студентов физтеха приводит к соблазну проспать те предметы, которые можно выучить самостоятельно. Но я думаю, что посещаемость у Тимофея Фёдоровича всё равно очень хорошая.
моё почтение студентам МФТИ если они это понимают. Я весь день потратил разобраться в материале и дошёл только до середины лекции...
Тимофей, спасибо Вам огромное! Вы великолепный преподаватель.
Попробуйте посмотреть с 5:50 на скорости воспроизведения 0,5 забавно :)
И правда забавно, алгоритмы заиграли новыми красками)
😂😂😂😂😂
😀😀мажет люто 😁
неполенился попробовал да это ж мы как раз после 0.5 ти
От лекции к лекции число зрителей убывает. И прямо в начале этой лекции Тимофей то же самое говорит о студентах
Чет на этом уроке я поплыл, как-то сложновато стало.
Нужно еще раз пересмотреть с паузами.
Теория понятна, а вот как код работает....
Крутая лекция! Посмотрел на скорости 1.5, всё понятно. Спасибо
А я на 47:55 "Ай-яй-яй" три раза слушал)) пока не врубился наконец...
Рекурсию для N=2, M=2 понял, только когда нарисовал стек вызовов, и бегал глазами по стеку с этими 0 и 1. Потому что продолжать не понимая рекурсию невозможно. Можно не понять формулу которая будет в рекурсии, но визуализировать стек вызовов, отработать условие ретурна в голове надо обязательно, иначе не понять что куда ушло, что кого вызвал и как это работает. На примере генерации всех числе N=2, M=2 можно понять, ведь математической сложности там нет, а рекурсивная витиеватость там есть, по стеку вызов за вызовом, ретурн. Уже не помню, что тут про стек рассказывали, я немного в другом месте смотрел. Однако поверить просто мало, а понять уже пришлось зарисовывать древовидную последовательную схему вызовов, которая являлась стеком.
28:30 можно поменять умолчание у prefix=[] generation_number(N:int, M:int, prefix=[]) и не делать проверку на каждой итерации.
Только ваши лекции спасают меня от мыслей бросить программирование
Спасибо Вам огромное! Задумался, чтобы сына готовить к поступлению в МФТИ после просмотра ваших роликов!
А сын сам хочет в МФТИ?
@@prototyperail-gun5589 он, видимо, просто не знает. В этом и есть одна из ролей родителя по отношению к детям, в случае обдуманной подготовки-воспитания отпрыска.
Как-то замудрено реализовано генерация чисел. prefix=None - лишнее, prefix = prefix or [] - лишнее, прилеплять к концу списка значение а потом отлеплять - лишнее. Во-первых это лишнее, во-вторых - это "программистские хитрости" которые сломали мозг бедным студентам. Вот просто и понятно, результат такой-же:
def generate_numbers(N:int, M:int, prefix = []):
if M==0:
print(prefix)
return
for digit in range(N):
generate_numbers(N, M-1, prefix + [digit])
не надо использовать .append который "портит" исходный список, надо использовать конкатенацию списков, что и показано в реализации выше.
Кроме того - не рассказано "на пальцах" принцип алгоритма, а сразу началась реализация в коде. Я несколько раз отматывал назад на пересмотр чтобы понять принцип алгоритма, а у студентов все в реальном времени идет.
я вот тоже не понял, зачем отдельно добавлять окончание, запускать рекурсию и тут же убирать digit , если можно запустить рекурсию с нужным окончанием, после выпадения из рекурсии окончания уже не будет. Разве что специально для студентов это сделано, чтобы те поняли, как это работает. Хотя ваш вариант проще для понимания, на мой взгляд.
@@danxai На самом деле, в варианте с использованием методов .append и .pop (то есть прилепливание и отлепливание окончания списка) мы гоняем по дереву рекурсии один и тот же объект - список, только меняем его длину. А в предложенном варианте (конкатенация списка и последнего элемента в вызове рекурсии) в каждом вызове рекурсии создается новый список(который уничтожается при возврате из рекурсии), что увеличивает время и забивает память (стек). Но про эти ограничения ничего не сказано в постановке задачи. И по скорости я разницы не заметил. А вот использование None вместо [ ] вообще непонятно зачем.
@@eugenedukatta9355 Подскажите пожалуйста, а как в этом алгоритме получаемые числа не выводить на экран, а запоминать в списке? Пробовал добавить первой строкой в функции создание пустого массива
result = []
if M == 0:
result.append(prefix)
return.
Так не получается.
Разобрался.
def generate_numbers(N:int, M:int, prefix = [],result=[]):
if M==0:
result.append(prefix)
return
for digit in range(N):
generate_numbers(N, M-1, prefix + [digit])
return result
Спасибо. Ваш коммент помог понять алгоритм и двинуться дальше.
Что-то с этой лекции стало реально сложно
Да просто это как c уроком по рисованию совы, если вы понимаете, о чём я.
чтобы понять рекурсию надо понять рекурсию
не то слова как сложно я в шоке
Как говорят философы, сложное - это сложенное из простого.
Пока есть только знание о простом, но нет умения (а тем более навыка) оперировать этим простым, то восприятие сложного - трудно (то есть трудозатратно, напрягаться надо).
Надо после (а иногда лучше и до) прослушивания лекции поразбираться с каждым из её элементов:
- постановкой задачи;
- алгоритмом;
- синтаксисом языка;
- реализацией алгоритма на языке;
- графическими представлениями задач;
- графическими пошаговым представлениями действий программы.
Если сознательно формировать навык понимания, то со временем станет легче.
@@karbafozaga2174 только чуть-чуть поменьше))
В моем маленьком городе лекции классные были и преподы выходцы из МГУ, а универ на 300 месте по стране :)
Генерация перестановок в лексикографическом порядке с помощью ЦИКЛОВ:
def f(n): # n - натуральное число, где n>1 обозначающее количество элементов в массиве
A=list(range(n))
while True:
print(A)
i=n-2
while A[i]>=A[i+1]:
i=i-1
if i==-1: return
j=n-1
while A[j]
49:06
вместо написания функции find в строке #FIXME пишем:
if number in prefix:
continue
25:50 по такому "дереву" понятно становится как работает алгоритм, но как до этого додумались, вот что самое удивительное😃
сортировка пузырька и грузила (модифицированная пузырьковая сортировка)
в цикле ищется минимальный и максимальный элемент массива
после чего они обмениваются (при необходимости) с крайними элементами (минимальный в начало, максимальный - в конец)
после чего область обработки (срез массива) уменьшается на 1 с краев, т.к. элементы там уже отсортированные.
количество итераций повторять до числа, равного половине длинны массива.
сортировка массива упорядоченного по убыванию требует всего N//2 обменов
# =========================================================
def my_sort(arr):
for j in range(0,len(arr)//2):
min=j # minimal index
max=len(arr)-j-1 # maximal index
for i in range(j,len(arr)-j):
if arr[min] > arr[i]:
min = i
if arr[max] < arr[i]:
max = i
if min==i and max==j:#ловушка двойного обмена, в сумме не дающая перестановки
arr[min], arr[max]=arr[max],arr[min]
else:
if max==j:#ловушка обмена затрагивающая перестановку минимального элемента, в которую входит максимальный
max=(min)
if min!=j: #не переставлять если элемент на месте
arr[j], arr[min] = arr[min], arr[j]
if max!=len(arr)-j-1: #не переставлять если элемент на месте
arr[len(arr)-j-1], arr[max] = arr[max], arr[len(arr)-j-1]
return(arr)
import random
print("\033[H\033[J", end="")
# проверка работоспособности алгоритма
switch=True
while switch:
print("
=Start=
")
unsort = [random.randint(10,99) for x in range (random.randint(30,50))]
print(unsort)
check=my_sort(unsort)
print(check)
for i in range(len(check)-1):
if (check[i] - check[i+1]) > 0:
print("error! len: ",len(check)," pos: ",i," " ,check[i],">" ,check[i+1])
switch=False
45:00
Заменить на
M= M or N
А в вызове функции поставить M=None
Проблема в том, что M=0 необходимое значение
@@vp_arth так всмысле необходимое, я говорю как убрать лишнее и сделать более понятный код. Вместо выражение if в строчке присвоения просто проверять на существование переменной M
@@Quickpass-mu2xg тогда до print-а не дойдет ни разу, т.к. при M=0 M станет снова N
@@Quickpass-mu2xg если только строку M = M or N поставить после if
Начиная с этой приходится пересматривать по несколько раз.
Мне казалось, что до prefix.pop не дойдёт никогда, попробовал убрать строчку- понял, попробовал вернуть и добавить перед этим строчку print( 'I am here ") - понял всё)
Строчку prefix = prefix or [ ] можно вообще убрать, а в аргументы функции поставить по умолчанию prefix = [ ]. Работает без ущерба.
ето же условие фано как в игэ) эх вспоминаю 2023 когда егэ сдавал и готовился, прикольно было, впервые узнал о сс, рекурсии и т.д.
Жлобьё считет себя гени... альным-->АРМИЯ
Эпически излагает, "не ,не будем вдавться в синтаксис", но заковырки излагает (!) прям на доске!! РЕСПЕКТ !!! Благодарю
54:35 in def generate_permutations: # print(prefix)
for i in range(0, N):
print(prefix[i], end="")
return
def find(number, A):
""" search for number in A return True if found
False if not found
"""
flag = False
for x in A:
if number == x:
flag = True
break
return flag
def generate_permutations(N:int, M:int=-1, prefix=None):
""" generation all with N digits in M positions
with prefix = prefix
"""
M = N if M == -1 else M
prefix = prefix or []
if M == 0:
# print(prefix)
# print(*prefix)
print("")
for i in range(0, N):
print(prefix[i], end="")
return
for number in range(1, N+1):
if find(number, prefix):
continue
prefix.append(number)
generate_permutations(N, M-1, prefix)
prefix.pop()
generate_permutations(3, 3)
Отличные лекции. Благодарю вас.
Что-то как-то мудрено объясняется принцип перестановки. Не проще провести аналогию с кодовым замком TSA (на чемоданах такой ставят)? А вывод - это все возможные комбинации. Соответственно, N = 10 - цифры от 0 - 9 на каждом цилиндре, M - это количество цилиндров с цифрами, ну а префикс - это наш счетчик, который мы выводим на каждой итерации - печатаем комбинацию (список).
Для лучшей визуализации, можно бы было запускать отладку и показывать выполнение кода и значения переменных по шагам.
А алгоритм хитро написан - полезно знать, спасибо.
Вообще-то тема про рекурсию. И это пример задачи, которую МОЖНО свести к рекурсивному решению.
Естественно, у более опытных "алгоритмщиков" появляется желание всю эту возню с префиксом и рекурсией "упростить" - но лекцию-то читают не для них, а для тех, кому нужно понять, что такое рекурсия :)
Спасибо.
Смотрю на x2.75 скорости. Пришлось несколько раз пересматривать 22:05 до 22:10, все время слышал "Я должен единичку туда за'append'ить" на русском, почему-то.
Как ты на такой скорости смотришь если у Ютуба Макс х2
@@th3754
Бан в гугле? =)
javascript:document.getElementsByClassName("video-stream html5-main-video")[0].playbackRate = 2.75
Ktykhy Telepuzik уделал ))))
Денис Головкин ага, ещё и «д» там плохо слышится )))
А он говорит не это?
в принципе можно с f форматированиемм и со строкой сделать)
def gen_number(n, m, prefix=""):
if m == 0:
print(prefix)
return
for i in range(n):
gen_number(n, m-1, f"{prefix}{i}")
как хорошо, что видео можно отмотать назад)))
Много раз.)))
Спасибо! Очень доходчиво объяснили
В 31:48 чуть не спалился ))
Отодрать эту последнею цифру :-D
😂
Это не могло быть случайностью, ведь буквы находятся далеко не рядом))
57:10 Чет у меня пока естественно это не получается это осознать😄. Сложно в голове отслеживать все эти погружения, хочется узнать, что код внутри делает, даже по дебагу сложновато
Спасибо за контент!
до этой лекции кое-как понимал, в этой 15 минут и поплыл ( буду пока другое учить. сюда позже вернусь...
На самом деле этот желаемый код:
if number in prefix:
continue
действительно бы сработал.
Я тоже удивился, нафига преподавателю было делать вид, что так нельзя
@@ТайлерДерден-ю2у проходные алгоритмы ещё раз показать. Он же вроде говорил.
Шикарные лекции!
Это и правда отличные лекции.
мне начинают алгоритмы радовать)
Я во сне: *бормочу* итак... мы с вами... мыы с вамиии... с вами мы...
Спасибо за лекцию)
спасибо за лекцию, очень доступно и понятно !
В Гарварде есть такой курс под названием CS50. Его так же смотрят и онлайн. Так вот русские там часто пишут - вот это преподаватель, не то что наши... И наши есть такие же ))
согласен
55:00 Где поиск числа в списке для его дальнейшего исключения. Что если в списке будет 2 одинаковых числа? Как это можно исправить грамотно
На восьмой лекции уже деревья и рекурсия, в которой я сижу два года и только после этой лекции начинаю понимать. Что же будет на двадцатой лекции?
Всё время представлял, как мышка на принтере распечатывает префикс :)
Отличный курс!!!
Генерация всех перестановок: "существует"
Я: ща взламаю пентагон!
Как можно такие лекции пропускать?
47:03 Не понял почему надо было создать функцию find() когда можно было написать просто if (number in prefix):
Чтобы попрактиковаться в написании однопроходных алгоритмов, чисто в образовательных целях. Лектор об этом говорил. Конечно, и лучше, и проще, было бы сделать так, как вы написали.
Получили бы тот же результат, только без написания велосипедов.
Почему нельзя в вызов рекуррентной функции сразу передать prefix.append(digit). Проверяла, не работает. Не пойму, почему?
prefix.append(digit) это метод. Он берет список (в данном случае prefix), лепит к нему новый элемент в хвост (в данном случае digit) при этом список становится измененным, и еще(!) возвращает(внимание!!!) результат None. Когда вы передаете в функцию prefix.append(digit), на самом деле передается None, хотя и сам список prefix при этом увеличивается на элемент digit.
Здраствуйте, скажите пожалуйста в функции генерации всех перестановок (def generate_permutations), вместо дополнительной функции (def find) можно воспользоваться оператором in ?
Ни-я не понятно, но очень интересно!
Интересно как можно понять работу например gen_bin не вдаваясь в стек вызовов, и пространство имён...
дерево нарисуй в паинте
Salova Fidi это не буквальный вопрос, а скорее риторический, понятия стек вызовов и пространство имён должны быть расписаны на соседней доске!
@@weightkiller3976 про стек вызовов говорилось в первой лекции про рекурсию
Salova Fidi я смотрел все лекции до этой, маловато было сказано по этим темам на мой взгляд, а темы одни из самых важных
@@weightkiller3976ну мало было, да
Ладно пацаны, я на месяц отлучусь. Дискретную математику подтяну и инглиш)
48:00 чет я затупел, а что просто if number in prefix: нельзя было написать? я проверил, так можно))
Просто учителю необходимо было показать однопроходный алгоритм поиска, который он не успел реализовать в прошлых лекциях,
на таком примере
Help! Параметр (префикс) передан как None, при рекурсии он меняет свое значение как глобальная переменная или при каждом вызове сбрасывается в None?
При рекурсии в функцию передаётся значение prefix, поэтому значение по умолчанию (=None) уже не применяется.
я ещё нуб в питоне, но что-то я не понял, зачем была нужна это котовасия с написанием функции find на 52:00, если было достаточно написать в функции generate_permitations:
if number in prefix: continue # это выражением само по себе бы выдало True или False.
Может это было в целях обучения?
Да. Он потом об этом сказал)
ради однопроходных алгоритмов
Почему то не удалось воспроизвести алгоритм перестановки, повторил все в точности, проверял много раз, и все равно не хочет перебирать у меня.
И у меня (
Единственное, что не понятно, а что если барьерным элементом будет выбран наименьший?
Prefix = Prefix or [ ]. Кто нибудь, объясните, почему он не может присвоить None? Ведь по умолчанию это и есть None? Не понял логику
В шапке у него присваевается Prefix = None, чтобы переменная была объявлена. Он не может в шапке сделать Prefix = [], потому что поведение функции будет совсем другим. А в части Prefix = Prefix or [] ему уже нужно, чтобы префикс или сохранил свое значение или стал пустым массивом.
Операция or (а также and) - это логическая операция, и вообще она должна работать с логическими значениями (типа True и False) и возвращать логическое значение тоже. Но язык так реализован, что каждое значение логической операции неявно преобразуется к логическому типу с помощью функции bool(). То есть выражение Prefix = Prefix or [ ] - реализуется как Prefix = bool(Prefix) or bool([ ]). А все "пустые" значения преобразуются в False: bool(None), bool(False), bool(0), bool([ ]), bool(), bool(''), bool(""), bool({}), bool(()) - это все False. Второй факт - если в операции or первый (левый) операнд равен False то он вычисляет следующий операнд и даже не вникая в его логическое значение - возвращает его целиком в том виде в каком он представлен. Так как bool(None)==False то он его пропускает, далее вычисляет и возвращает второй операнд [ ]. То же самое для if () и while().
@@stanislavch5323 это все лишнее. В шапке надо сделать prefix = [ ], а в рекурсивный вызов функции передавать prefix + [digit] И все прекрасно работает - проверено.
@@eugenedukatta9355 Help! Параметр (префикс) передан как None, при рекурсии он меняет свое значение как глобальная переменная или при каждом вызове сбрасывается в None?
@@istra3265 В видео, функция выглядит так:
def generate_numbers(N:int, M:int, prefix = None):
здесь параметр prefix не передается как None. prefix = None означает значение по умолчанию, которое принимает параметр, если параметр не передается явно. В примере, (первый) раз функция вызывается без параметра prefix и он в первом вызове принудительно принимает значение по умолчанию = None. В первом вызове срабатывает строка "prefix = prefix or []" и значение prefix становится [] то есть пустым списком.
В следующих (рекурсивных) вызовах , строка "prefix = prefix or []" не меняет значения prefix
В последующие (рекурсивные) вызовы параметр prefix передается явно, его новое значение вычисляется до рекурсивного вызова в строке "prefix.append(digit)" - список prefix удлиняется новым числом в конце списка и передается далее по рекурсии.
prefix в каждом вызове это разные переменные (локальная переменная)
мне, по словам лектора, "не вошло". если кто-то выпадает вначале, то лучше просмотр начинать с 32минуты.
А зачем переопределять переменную списка вот этим prefix = prefix or [ ] ? Я сразу в переменную поставил дефолтное значение prefix=[ ] и всё работает точно также
Можешь построить функцию просмотров видео от номера лекции
Шеня цитирует! Класс!
У Шеня описание алгоритма перестановок для меня было не понятным, пришлось на просторах интернета искать более доходчивое описание
все поняли эту функцию generate_numbers? Я пересмотрел пару раз, не понял. Понял что делает, но как работает и как к такому приити не понял
интересно, почему сами написали функцию find, а не воспользовались готовой prefix.__contains__(number)
if number in prefix:
continue
Офигенно!!
from itertools import permutations
работает значительно быстрее, значительно)
дружище, конечно так можно, но смысл то в том что бы понять алгоритм и то как это работает.
Очень не легко стало... Понять трудно
у меня почему- то не запускается программа. нажимаю ран(F5), она сейвает и дальше пишет >>> и все.. в чем проблема?
У меня тоже (
@@natashasolianyk забейте)
После этой лекции, смог решить задачу
DONALD
+
GERALD
__________
ROBERT
Где D=5, с помощью грубой силы.
def subs_char(Names:list, letter:str, num:int):
for name in Names:
for idx, char in enumerate(name):
if type(char) == str and char == letter:
name[idx] = num
def check_ford_task(prefix):
Names=[['g','e','r','a','l','d'],['d','o','n','a','l','d'],['r','o','b','e','r','t']]
table = ['t', 'd', 'e', 'g', 'l', 'n', 'o', 'r','a', 'b']
for idx, char in enumerate(table):
subs_char(Names, char,prefix[idx])
for idx, name in enumerate(Names):
Names[idx] = int("".join(str(num) for num in name))
if Names[0] + Names[1] == Names[2]:
print('gerald = {}'.format(Names[0]))
print('donald = {}'.format(Names[1]))
print('robert = {}'.format(Names[2]))
return True
return False
def generate_permutation(N:int, M:int=-1, prefix=None):
M=N if M == -1 else M
prefix = prefix or []
if M == 0:
if check_ford_task(prefix):
import sys
sys.exit()
return
for number in range(0, N):
if number in prefix:
continue
prefix.append(number)
generate_permutation(N, M-1, prefix)
prefix.pop()
map = [0, 5] # d =5, t = 0
generate_permutation(10,8,map)
Непонятна суть задачи, даже после просмотра результата выполнения.... код читать лень.
либо я не догоняю, либо алгоритм перестановок возможных чисел не верный. На каждой итерации алгоритм проходится по ВСЕМ числам из системы счисления, благодаря чему 1) числа повторяются (противоречит 2:28), 2) количество перестановок из трех чисел должно быть: 1х2х3 = 6, алгоритм же выдает 27 вариантов (3 варианта на 1ой позиции Х 3 варианта на 2ой позиции Х 3 варианта на 3ей позиции)
я в 9 классе учусь , хочу в МФТИ , надеюсь что вы будете преподавать, если поступлю)
Можно лекции где он все успел? 😒
Нее, рекурсия, не просто зашла ((
Ну не то чтобы принцип сложный, нет здесь все понятно, но когда дело доходить до вызова в цикле, не сразу в голове сложилось, лично мне не хватило детального разбора в какой момент какой рекурентный случай в какой ячейке будет генерировать какое число.
P.S. лекции слушаю в дороге, нет возможности тут же экспериментировать, это конечно, Очень сильно усложняет процесс обучения, но что имеем (((..
Короче пока спокойно не сел и не переслушал еще как минимум дважды не разобрался
За лекции низкий поклон!
самое забавное что нам преподавали все что в лекциях больше 20 лет назад (первый выпуск по ИТ специальности одного института). с годами все забылось, в сейчас зато вспоминается и легко понимаешь про что речь.
Как сделать чтобы prefix не печатался а ретурнился (извиняюсь)? Просто return prefix не работает, дает None. Другими словами, как результаты загнать в переменную?
все круто и понятно!
только не понял зачем find() надо было писать. можно было отсечь одним if number not in prefix, но это мелочь в целом
Что такое prefix?
Что значит перестановки в m позициях?
Объясните, пожалуйста, по поводу момента где, лектор говорит, что в аргумент функции нельзя передать пустой список, потому что в таком случае "он сгенерится один раз" и останется одним и тем тем же.
ruclips.net/video/2XFaK3bgT7w/видео.html
Попробовал передать в prefix=[ ] - результат выполнения функции не изменился
def permutations(lst):
return [lst] if len(lst) == 1 else \
[[el]+p for el in lst
for p in permutations(list(filter(lambda x: x != el, lst)))]
print(permutations([1, 2, 3]))
оно будет на каждой рекурсии по списку на стек лОжить ?
Поставил на паузу на 19:08, записал. Пытаюсь включить несколько раз - ничего. Потом замечаю, что что-то не так. Глаза у Тимофея двигаются. Стало страшно.
def generate_number(N: int, M: int, prefix=None):
prefix = prefix or []
if M == 0:
print(prefix)
return
for digit in range(N):
prefix.append(digit)
generate_number(N, M - 1, prefix)
prefix.pop()
generate_number(3, 3)
Не могу въехать, почему в то время когда
M>0
не срабатывает prefix.pop()
но проход по prefix.pop() происходит при М==0
потому что pop() работает только после выхода из функции generate_number(а выход происходит при М == 0)
Не буду утверждать ничего об ожидаемых прорывах отечественной школы программирования, хотя лекции качественные. А вот в обороноспособности нашей страны нет решительно никаких сомнений! С такими солдатиками для опытов по сортировкам нам ничего не страшно! Ура, товарищи! (если что, это легкая ирония, не отражающая реального положения дел в ВПК)
Вот реально с этим prefix.pop() было сложно. Пришлось тормознуть видео, и тупо вручную накидать алгоритм, чтобы понять зачем выкидывать последний элемент из массива. Думаю, у студентов на лекции те же проблемы.
ну дак и в чем же? накидываю от руки, накидываю, а в голову пока не приходит понимание 😬
а, уже понял 😂
можно строить функцию и по количеству просмотров от номера лекции
И даже эта функция не объективна, потому что чем дальше - сложнее тема. Из-за этого оставшиеся начинают пересматривают видео. То есть фактически оставшихся даже ещё меньше, чем просмотров))
А почему не написать в функции generate_permutations(N:int, M:int, prefix=None):
M = M or N
в этом случае, если m = -1, то m примет значение самого себя, т.к. оператор or возвращает первый же "истинаподобный" элемент (если таковой имеется)
Может кто объяснить, зачем так вводить prefix в первой функции? Почему просто не написать, что он равен пустому списку, ведь результат тот же?
Если написать пустой список среди списка переменных, то он создается только один раз, и для всех вызовов он будет общим, и туда будут попадать элементы от всех вызовов.
Нельзя передавать в качестве аргументов по умолчанию изменяемые объекты! Причина написана в комментарии выше
Все верно, строка prefix=prefix or [] здесь лишняя можно было обойтись значением по умолчанию. Объект prefix ссылочного типа и в каждом вызове функции мы ссылаемся на один и тот же список, поэтому необходимо удалять после вызова функции добавленный элемент. Можно тело цикла реализовать иначе: gen_nums(n, m - 1, [*prefix, i]) тогда на каждый вызов функции будет создаваться новый список с копированием текущего содержимого списка prefix и добавлением в конец следующего числа.
В данной реализации в prefix и так храниться один общий для всех рекуррентных вызовов функции список, так как строка prefix=prefix or [] отработает ровно один раз, что эквивалентно параметру по умолчанию
Это ведёт преподаватель, а не программист. Боюсь у него это просчитано уже много-много раз (аж надоело) и он тупо думает над тем как нас заинтриговать(потому и так внимательно в зал поглядывает(жертву ищет)) чтобы думали. Как идеально решается эта задача см. в методичке (у старших курсов).
Не удивлюсь когда узнаю, что есть ещё пара возможно скрытых видеокамер, которые снимают аудиторию.
Есть знающие люди в комментах? Как реализовать этот рекурсивный код в виде генератора чисел, так чтобы это был генератор, а не просто печаталка? Т.е. чтобы функция что-то возвращала и я мог перебирать эти значение.
Пыжился, пытался использовать yield prefix в базовом случае и yield from gen_bin(length, prefix + f'{i}'), но ничего не работает.
Можно конечно вместо принта все в глобальный список складывать, но это вроде как бэд практис, есть ли более элегантное решение?
Тут нужно переходить от рекурсии к итеративному алгоритму со стеком
Сортировка Хоара - лучший случай n log^2 n
Сортировка слиянием - n log n
Сортировка Хоара же быстрее выходить должна, почему здесь на доске одинаковые значения
Вы ошиблись, сортировка Хоара (она же быстрая) имеет сложность n*log(n) в среднем.
год назад умеренно вникал в сортировки и их сравнение. Хоар хорошо работает на больших массивах, на мелких (меньше 20-30 элементов) может проигрывать.
47:47 что это было
Рекуррентный и рекурсивный синонимы в английском и соответственно в русском.
Одну минуточку was in есть в пайтоне 😉
Спасибо
Я 13-летний школьник. Ты топ