Алгоритмы на Python 3. Лекция №8

Практика: judge.mipt.ru/m...
Telegram-группа: t.me/tkhiriano...
Спонсировать: / tkhirianov или www.paypal.me/...
курс: Информатика. Алгоритмы и структуры данных на Python 3.
лектор: Хирьянов Тимофей Фёдорович
24.10.2017
Темы, рассмотренные на лекции №8:
Генерация комбинаторных объектов.
Рекурсивная генерация всех чисел длины M.
Генерация всех перестановок (рекурсивная).
Быстрые сортировки: Тони Хоара и слиянием (без реализации).

[@andreykelip5631]

моё почтение студентам МФТИ если они это понимают. Я весь день потратил разобраться в материале и дошёл только до середины лекции...

[@iritaka]

Тайм-коды: генерация всех перестановок 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 иллюстрация сортировка слиянием. Деление напополам и слияние уже отсортированных половинок

[@Andri-f3s]

Красава

[@VladK181]

.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

[@predatel_rodini]

Спасибо за лекцию. Эх, вернуть бы те времена, когда я мог учиться и не работать, я бы не одной лекции не пропустил. Сейчас приходиться и работать и учиться и на работе учиться. Но с такими преподавателями у меня есть шанс.

[@ЮстасПельмень]

так рил топчик

[@gerhardshreder2391]

подача у препода хорошая, но этот тупняк при объяснении просто всё ломает. Лучше бы остановился и всё продумал на перёд, чем эти вечные "а, нет, извините, ой, подождите" и т.д.

[@Самисвоимируками-я4ь]

@@gerhardshreder2391 да иди ты в баню. Всегда бесят такие критики, которые сами хер чего сделали. Тот кто пробовал что-то сделать сам, будет с уважением относится к труду другого.

[@gerhardshreder2391]

@@Самисвоимируками-я4ь боже мой, без недели 2020ый год на дворе, а в мире оказывается всё еще живут люди с таким ограниченным мышлением. Ты, я надеюсь, никогда в жизни не критиковал власть, футбол, кино, книги? А то я сильно сомневаюсь, что ты великий реформатор, игрок года FIFA, гениальный режиссер и писатель в одном лице. Что касается лекции - у препода есть конкретные косяки и я имею полное право о них здесь высказываться. Если тебя это бесит - это исключительно твои проблемы.

[@Самисвоимируками-я4ь]

@@gerhardshreder2391 Да ты прав мне как-то пофиг на твой высер, просто считаю что ты нихера не сделал, а мычишь вот и все.

[@leya_lutik9601]

я как те студенты, не сразу врубилась в фунццию перебора, но я-то могу остановить видео. Му-Ха-Ха!!! Спасибо за лекцию!

[@maratgabitov]

Удивительно, что на Ваши лекции студенты не ходят. Когда учился в СПбГТИ(ТУ), у нас в принципе таких преподавателей (которые любят свой предмет и умеют супер качественно его преподнести) не было, к сожалению. Сейчас мне 31, учусь заново) Спасибо Вам за труды!

[@ВасилийВишневский-н2ф]

Колоссальная учебная нагрузка на студентов физтеха приводит к соблазну проспать те предметы, которые можно выучить самостоятельно. Но я думаю, что посещаемость у Тимофея Фёдоровича всё равно очень хорошая.

[@predatel_rodini]

Хорошо, что в 2к18 к таким преподавателям есть доступ у всех. Когда я учился в универе, youtube не существовал, а дипломы сдавали на дискетках, а до МФТИ было 10000 км от моего универа. Слава Гуглу, слава KZbin, слава Питону, Гвидо и Тимофею)))).

[@eugenedukatta9355]

"дипломы сдавали на дискетках"... охххх... были времена когда дипломы сдавали написанными рукой на бумаге!

[@everythingiskubernetes8331]

выдающийся базовый курс Python! профессор очень увлечен и занят. Самая сложная часть цикла лекций в том, что они на русском языке. Я не говорю по-русски - я учусь. Спасибо, профессор, и спасибо Google Translate!

[@nicholasspezza9449]

Чушь написал недалекий иностранец. Это не базовый курс по Python, тут уже его надо знать, т.к. здесь учат алгоритмам.

[@konstantin7821]

@@nicholasspezza9449 Вообще-то этот курс лекций рассчитан так же и на тех, кто не знаком с Python, поэтому с первых лекций постепенно рассказывается и про простейший синтаксис.

[@SHRTST]

wow, you’re good, good luck

[@МаркГубин-к6е]

Тимофей Федорович, спасибо за Ваш труд! Принцип работы генератора чисел очень напомнил механизм работы одометра.

[@Alex-hh5oe]

Чет на этом уроке я поплыл, как-то сложновато стало. Нужно еще раз пересмотреть с паузами. Теория понятна, а вот как код работает....

[@DimonRonD]

От лекции к лекции число зрителей убывает. И прямо в начале этой лекции Тимофей то же самое говорит о студентах

[@maximsatskevich3043]

Тимофей, спасибо Вам огромное! Вы великолепный преподаватель.

[@istra3265]

Только ваши лекции спасают меня от мыслей бросить программирование

[@ВладимирЕрмолов-б4ш]

Спасибо Вам огромное! Задумался, чтобы сына готовить к поступлению в МФТИ после просмотра ваших роликов!

[@prototyperail-gun5589]

А сын сам хочет в МФТИ?

[@antioch44channel]

@@prototyperail-gun5589 он, видимо, просто не знает. В этом и есть одна из ролей родителя по отношению к детям, в случае обдуманной подготовки-воспитания отпрыска.

[@LSE13]

Крутая лекция! Посмотрел на скорости 1.5, всё понятно. Спасибо

[@Inco80Rus]

А я на 47:55 "Ай-яй-яй" три раза слушал)) пока не врубился наконец...

[@dushirak]

Рекурсию для N=2, M=2 понял, только когда нарисовал стек вызовов, и бегал глазами по стеку с этими 0 и 1. Потому что продолжать не понимая рекурсию невозможно. Можно не понять формулу которая будет в рекурсии, но визуализировать стек вызовов, отработать условие ретурна в голове надо обязательно, иначе не понять что куда ушло, что кого вызвал и как это работает. На примере генерации всех числе N=2, M=2 можно понять, ведь математической сложности там нет, а рекурсивная витиеватость там есть, по стеку вызов за вызовом, ретурн. Уже не помню, что тут про стек рассказывали, я немного в другом месте смотрел. Однако поверить просто мало, а понять уже пришлось зарисовывать древовидную последовательную схему вызовов, которая являлась стеком.

[@okyskaa]

На восьмой лекции уже деревья и рекурсия, в которой я сижу два года и только после этой лекции начинаю понимать. Что же будет на двадцатой лекции?

[@xrollup]

Начиная с этой приходится пересматривать по несколько раз.

[@Roiser101]

Что-то как-то мудрено объясняется принцип перестановки. Не проще провести аналогию с кодовым замком TSA (на чемоданах такой ставят)? А вывод - это все возможные комбинации. Соответственно, N = 10 - цифры от 0 - 9 на каждом цилиндре, M - это количество цилиндров с цифрами, ну а префикс - это наш счетчик, который мы выводим на каждой итерации - печатаем комбинацию (список). Для лучшей визуализации, можно бы было запускать отладку и показывать выполнение кода и значения переменных по шагам. А алгоритм хитро написан - полезно знать, спасибо.

[@MaxPV1981]

Вообще-то тема про рекурсию. И это пример задачи, которую МОЖНО свести к рекурсивному решению. Естественно, у более опытных "алгоритмщиков" появляется желание всю эту возню с префиксом и рекурсией "упростить" - но лекцию-то читают не для них, а для тех, кому нужно понять, что такое рекурсия :)

[@istra3265]

Help! Параметр (префикс) передан как None, при рекурсии он меняет свое значение как глобальная переменная или при каждом вызове сбрасывается в None?

[@ПавелМаксимов-н6о]

При рекурсии в функцию передаётся значение prefix, поэтому значение по умолчанию (=None) уже не применяется.

[@victorkrupeichenko8028]

Здраствуйте, скажите пожалуйста в функции генерации всех перестановок (def generate_permutations), вместо дополнительной функции (def find) можно воспользоваться оператором in ?

[@iEfimoff]

В моем маленьком городе лекции классные были и преподы выходцы из МГУ, а универ на 300 месте по стране :)

[@IndexSteadFast]

Что-то с этой лекции стало реально сложно

[@savel2work]

Да просто это как c уроком по рисованию совы, если вы понимаете, о чём я.

[@karbafozaga2174]

чтобы понять рекурсию надо понять рекурсию

[@ISUZU2012]

не то слова как сложно я в шоке

[@AntonZubkov]

Как говорят философы, сложное - это сложенное из простого. Пока есть только знание о простом, но нет умения (а тем более навыка) оперировать этим простым, то восприятие сложного - трудно (то есть трудозатратно, напрягаться надо). Надо после (а иногда лучше и до) прослушивания лекции поразбираться с каждым из её элементов: - постановкой задачи; - алгоритмом; - синтаксисом языка; - реализацией алгоритма на языке; - графическими представлениями задач; - графическими пошаговым представлениями действий программы. Если сознательно формировать навык понимания, то со временем станет легче.

[@НиктоНиктоев-щ7ю]

@@karbafozaga2174 только чуть-чуть поменьше))

[@eugenedukatta9355]

Как-то замудрено реализовано генерация чисел. 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 который "портит" исходный список, надо использовать конкатенацию списков, что и показано в реализации выше. Кроме того - не рассказано "на пальцах" принцип алгоритма, а сразу началась реализация в коде. Я несколько раз отматывал назад на пересмотр чтобы понять принцип алгоритма, а у студентов все в реальном времени идет.

[@danxai]

я вот тоже не понял, зачем отдельно добавлять окончание, запускать рекурсию и тут же убирать digit , если можно запустить рекурсию с нужным окончанием, после выпадения из рекурсии окончания уже не будет. Разве что специально для студентов это сделано, чтобы те поняли, как это работает. Хотя ваш вариант проще для понимания, на мой взгляд.

[@eugenedukatta9355]

@@danxai На самом деле, в варианте с использованием методов .append и .pop (то есть прилепливание и отлепливание окончания списка) мы гоняем по дереву рекурсии один и тот же объект - список, только меняем его длину. А в предложенном варианте (конкатенация списка и последнего элемента в вызове рекурсии) в каждом вызове рекурсии создается новый список(который уничтожается при возврате из рекурсии), что увеличивает время и забивает память (стек). Но про эти ограничения ничего не сказано в постановке задачи. И по скорости я разницы не заметил. А вот использование None вместо [ ] вообще непонятно зачем.

[@АркадийПаравозов-р4ф]

@@eugenedukatta9355 Подскажите пожалуйста, а как в этом алгоритме получаемые числа не выводить на экран, а запоминать в списке? Пробовал добавить первой строкой в функции создание пустого массива result = [] if M == 0: result.append(prefix) return. Так не получается.

[@АркадийПаравозов-р4ф]

Разобрался. 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

[@andreykuznetsov7442]

Спасибо. Ваш коммент помог понять алгоритм и двинуться дальше.

[@Gerotero-r1o]

Отличные лекции. Благодарю вас.

[@klopus]

Попробуйте посмотреть с 5:50 на скорости воспроизведения 0,5 забавно :)

[@ivan.peshkov]

И правда забавно, алгоритмы заиграли новыми красками)

[@evgenymarshin]

😂😂😂😂😂

[@Позаписанномупути]

Алгоритмы под шафе

[@maiorchiks3107]

😀😀мажет люто 😁

[@sanjarkenjayev7368]

неполенился попробовал да это ж мы как раз после 0.5 ти

[@AndreiSokolov-k7j]

ето же условие фано как в игэ) эх вспоминаю 2023 когда егэ сдавал и готовился, прикольно было, впервые узнал о сс, рекурсии и т.д.

[@tirludjin1048]

28:30 можно поменять умолчание у prefix=[] generation_number(N:int, M:int, prefix=[]) и не делать проверку на каждой итерации.

[@konstantin7821]

Генерация перестановок в лексикографическом порядке с помощью ЦИКЛОВ: 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]

[@denisbel9740]

Шикарные лекции!

[@BoldBass24]

Спасибо за контент!

[@titovcg]

как хорошо, что видео можно отмотать назад)))

[@dimoneagle100]

Много раз.)))

[@ИльяМалыгин-е6х]

25:50 по такому "дереву" понятно становится как работает алгоритм, но как до этого додумались, вот что самое удивительное😃

[@wonder_go]

Мне казалось, что до prefix.pop не дойдёт никогда, попробовал убрать строчку- понял, попробовал вернуть и добавить перед этим строчку print( 'I am here ") - понял всё) Строчку prefix = prefix or [ ] можно вообще убрать, а в аргументы функции поставить по умолчанию prefix = [ ]. Работает без ущерба.

[@dianaoryol3014]

Почему нельзя в вызов рекуррентной функции сразу передать prefix.append(digit). Проверяла, не работает. Не пойму, почему?

[@eugenedukatta9355]

prefix.append(digit) это метод. Он берет список (в данном случае prefix), лепит к нему новый элемент в хвост (в данном случае digit) при этом список становится измененным, и еще(!) возвращает(внимание!!!) результат None. Когда вы передаете в функцию prefix.append(digit), на самом деле передается None, хотя и сам список prefix при этом увеличивается на элемент digit.

[@Santiago21_RU]

Как сделать чтобы prefix не печатался а ретурнился (извиняюсь)? Просто return prefix не работает, дает None. Другими словами, как результаты загнать в переменную?

[@mikhailkalashnikov4771]

Спасибо! Очень доходчиво объяснили

[@rurybug4125]

Жлобьё считет себя гени... альным-->АРМИЯ Эпически излагает, "не ,не будем вдавться в синтаксис", но заковырки излагает (!) прям на доске!! РЕСПЕКТ !!! Благодарю

[@maiorchiks3107]

до этой лекции кое-как понимал, в этой 15 минут и поплыл ( буду пока другое учить. сюда позже вернусь...

[@sergiozaichenko3485]

сортировка пузырька и грузила (модифицированная пузырьковая сортировка) в цикле ищется минимальный и максимальный элемент массива после чего они обмениваются (при необходимости) с крайними элементами (минимальный в начало, максимальный - в конец) после чего область обработки (срез массива) уменьшается на 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

[@8888UNIVERSE8888]

Это и правда отличные лекции.

[@i7ion]

На самом деле этот желаемый код: if number in prefix: continue действительно бы сработал.

[@ТайлерДерден-ю2у]

Я тоже удивился, нафига преподавателю было делать вид, что так нельзя

[@lebfrspb]

@@ТайлерДерден-ю2у проходные алгоритмы ещё раз показать. Он же вроде говорил.

[@borodatsik]

Всё время представлял, как мышка на принтере распечатывает префикс :)

[@ChuvakSurala]

Объясните, пожалуйста, по поводу момента где, лектор говорит, что в аргумент функции нельзя передать пустой список, потому что в таком случае "он сгенерится один раз" и останется одним и тем тем же. kzbin.info/www/bejne/aImpkn5pl8yHbdk Попробовал передать в prefix=[ ] - результат выполнения функции не изменился

[@bektursun]

В 31:48 чуть не спалился ))

[@olegvolkov8006]

Отодрать эту последнею цифру :-D

[@husanturdiev]

😂

[@husanturdiev]

Это не могло быть случайностью, ведь буквы находятся далеко не рядом))

[@AndreiSokolov-k7j]

в принципе можно с 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}")

[@TyTaHXaMoH23]

у меня почему- то не запускается программа. нажимаю ран(F5), она сейвает и дальше пишет >>> и все.. в чем проблема?

[@natashasolianyk]

У меня тоже (

[@TyTaHXaMoH23]

@@natashasolianyk забейте)

[@СергейБыковский-ъ1ъ]

В Гарварде есть такой курс под названием CS50. Его так же смотрят и онлайн. Так вот русские там часто пишут - вот это преподаватель, не то что наши... И наши есть такие же ))

[@ISUZU2012]

согласен

[@Gerotero-r1o]

мне начинают алгоритмы радовать)

[@AlxAtv76]

Отличный курс!!!

[@Andrei-de6mf]

Ладно пацаны, я на месяц отлучусь. Дискретную математику подтяну и инглиш)

[@zion4d]

49:06 вместо написания функции find в строке #FIXME пишем: if number in prefix: continue

[@leolis3851]

спасибо за лекцию, очень доступно и понятно !

[@banaaboy6504]

Как можно такие лекции пропускать?

[@ИльяПудов-в5г]

А зачем переопределять переменную списка вот этим prefix = prefix or [ ] ? Я сразу в переменную поставил дефолтное значение prefix=[ ] и всё работает точно также

[@Pixel_Magic]

Я во сне: *бормочу* итак... мы с вами... мыы с вамиии... с вами мы... Спасибо за лекцию)

[@ИльяМалыгин-е6х]

57:10 Чет у меня пока естественно это не получается это осознать😄. Сложно в голове отслеживать все эти погружения, хочется узнать, что код внутри делает, даже по дебагу сложновато

[@radunov.a]

все поняли эту функцию generate_numbers? Я пересмотрел пару раз, не понял. Понял что делает, но как работает и как к такому приити не понял

[@halloweex]

Почему то не удалось воспроизвести алгоритм перестановки, повторил все в точности, проверял много раз, и все равно не хочет перебирать у меня.

[@natashasolianyk]

И у меня (

[@Pixel_Magic]

Генерация всех перестановок: "существует" Я: ща взламаю пентагон!

[@NethronCoru]

Спасибо. Смотрю на x2.75 скорости. Пришлось несколько раз пересматривать 22:05 до 22:10, все время слышал "Я должен единичку туда за'append'ить" на русском, почему-то.

[@th3754]

Как ты на такой скорости смотришь если у Ютуба Макс х2

[@Ktykhy]

@@th3754 Бан в гугле? =) javascript:document.getElementsByClassName("video-stream html5-main-video")[0].playbackRate = 2.75

[@danalexpiano]

Ktykhy Telepuzik уделал ))))

[@danalexpiano]

Денис Головкин ага, ещё и «д» там плохо слышится )))

[@winandfx]

А он говорит не это?

[@shtern_of_kruzenshtern]

Единственное, что не понятно, а что если барьерным элементом будет выбран наименьший?

[@willgoonandon3050]

Ни-я не понятно, но очень интересно!

[@weightkiller3976]

Интересно как можно понять работу например gen_bin не вдаваясь в стек вызовов, и пространство имён...

[@salovafidi8913]

дерево нарисуй в паинте

[@weightkiller3976]

Salova Fidi это не буквальный вопрос, а скорее риторический, понятия стек вызовов и пространство имён должны быть расписаны на соседней доске!

[@salovafidi8913]

@@weightkiller3976 про стек вызовов говорилось в первой лекции про рекурсию

[@weightkiller3976]

Salova Fidi я смотрел все лекции до этой, маловато было сказано по этим темам на мой взгляд, а темы одни из самых важных

[@salovafidi8913]

@@weightkiller3976ну мало было, да

[@predatel_rodini]

я ещё нуб в питоне, но что-то я не понял, зачем была нужна это котовасия с написанием функции find на 52:00, если было достаточно написать в функции generate_permitations: if number in prefix: continue # это выражением само по себе бы выдало True или False. Может это было в целях обучения?

[@alexeygumenyuk8510]

Да. Он потом об этом сказал)

[@_ArPTech_]

ради однопроходных алгоритмов

[@IlyaZherebtsov]

интересно, почему сами написали функцию find, а не воспользовались готовой prefix.__contains__(number)

[@mr.angrom]

if number in prefix: continue

[@незнайкалунный-ю9ж]

мне, по словам лектора, "не вошло". если кто-то выпадает вначале, то лучше просмотр начинать с 32минуты.

[@kresh6187]

55:00 Где поиск числа в списке для его дальнейшего исключения. Что если в списке будет 2 одинаковых числа? Как это можно исправить грамотно

[@clinteastwood957]

Prefix = Prefix or [ ]. Кто нибудь, объясните, почему он не может присвоить None? Ведь по умолчанию это и есть None? Не понял логику

[@stanislavch5323]

В шапке у него присваевается Prefix = None, чтобы переменная была объявлена. Он не может в шапке сделать Prefix = [], потому что поведение функции будет совсем другим. А в части Prefix = Prefix or [] ему уже нужно, чтобы префикс или сохранил свое значение или стал пустым массивом.

[@eugenedukatta9355]

Операция 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().

[@eugenedukatta9355]

@@stanislavch5323 это все лишнее. В шапке надо сделать prefix = [ ], а в рекурсивный вызов функции передавать prefix + [digit] И все прекрасно работает - проверено.

[@istra3265]

@@eugenedukatta9355 Help! Параметр (префикс) передан как None, при рекурсии он меняет свое значение как глобальная переменная или при каждом вызове сбрасывается в None?

[@eugenedukatta9355]

@@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 в каждом вызове это разные переменные (локальная переменная)

[@ПлатонТрипуть]

я в 9 классе учусь , хочу в МФТИ , надеюсь что вы будете преподавать, если поступлю)

[@kartushinav]

все круто и понятно! только не понял зачем find() надо было писать. можно было отсечь одним if number not in prefix, но это мелочь в целом

[@maxviewtoday]

Очень не легко стало... Понять трудно

[@oanovitskij]

Что значит перестановки в m позициях?

[@Quickpass-mu2xg]

45:00 Заменить на M= M or N А в вызове функции поставить M=None

[@vp_arth]

Проблема в том, что M=0 необходимое значение

[@Quickpass-mu2xg]

@@vp_arth так всмысле необходимое, я говорю как убрать лишнее и сделать более понятный код. Вместо выражение if в строчке присвоения просто проверять на существование переменной M

[@АлексейМалышев-ц4ъ]

@@Quickpass-mu2xg тогда до print-а не дойдет ни разу, т.к. при M=0 M станет снова N

[@АлексейМалышев-ц4ъ]

@@Quickpass-mu2xg если только строку M = M or N поставить после if

[@nikichpyk]

Офигенно!!

[@justbar9164]

какой у вас текстовый редактор?

[@farshman57]

Шеня цитирует! Класс!

[@konstantin7821]

У Шеня описание алгоритма перестановок для меня было не понятным, пришлось на просторах интернета искать более доходчивое описание

[@freelife1000]

Можешь построить функцию просмотров видео от номера лекции

[@dznshfvt]

А почему не написать в функции generate_permutations(N:int, M:int, prefix=None): M = M or N

[@SemyonKalyakulin]

в этом случае, если m = -1, то m примет значение самого себя, т.к. оператор or возвращает первый же "истинаподобный" элемент (если таковой имеется)

[@Dimas-Dubna]

Что такое prefix?

[@НиктоНиктоев-щ7ю]

48:00 чет я затупел, а что просто if number in prefix: нельзя было написать? я проверил, так можно))

[@GeorgiiIurcenco]

Просто учителю необходимо было показать однопроходный алгоритм поиска, который он не успел реализовать в прошлых лекциях, на таком примере

[@maksim4334]

Можно лекции где он все успел? 😒

[@ФедякинРоман]

Есть знающие люди в комментах? Как реализовать этот рекурсивный код в виде генератора чисел, так чтобы это был генератор, а не просто печаталка? Т.е. чтобы функция что-то возвращала и я мог перебирать эти значение. Пыжился, пытался использовать yield prefix в базовом случае и yield from gen_bin(length, prefix + f'{i}'), но ничего не работает. Можно конечно вместо принта все в глобальный список складывать, но это вроде как бэд практис, есть ли более элегантное решение?

[@prototyperail-gun5589]

Тут нужно переходить от рекурсии к итеративному алгоритму со стеком

[@limirikys]

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

[@absent6322]

потому что pop() работает только после выхода из функции generate_number(а выход происходит при М == 0)

[@hellocode_dev]

Нее, рекурсия, не просто зашла (( Ну не то чтобы принцип сложный, нет здесь все понятно, но когда дело доходить до вызова в цикле, не сразу в голове сложилось, лично мне не хватило детального разбора в какой момент какой рекурентный случай в какой ячейке будет генерировать какое число. P.S. лекции слушаю в дороге, нет возможности тут же экспериментировать, это конечно, Очень сильно усложняет процесс обучения, но что имеем (((.. Короче пока спокойно не сел и не переслушал еще как минимум дважды не разобрался За лекции низкий поклон!

[@nikus20111111]

самое забавное что нам преподавали все что в лекциях больше 20 лет назад (первый выпуск по ИТ специальности одного института). с годами все забылось, в сейчас зато вспоминается и легко понимаешь про что речь.

[@Efimov1982]

После этой лекции, смог решить задачу DONALD + GERALD __________ ROBERT Где D=5, с помощью грубой силы.

[@Efimov1982]

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)

[@konstantin7821]

Непонятна суть задачи, даже после просмотра результата выполнения.... код читать лень.

[@user-serji0]

либо я не догоняю, либо алгоритм перестановок возможных чисел не верный. На каждой итерации алгоритм проходится по ВСЕМ числам из системы счисления, благодаря чему 1) числа повторяются (противоречит 2:28), 2) количество перестановок из трех чисел должно быть: 1х2х3 = 6, алгоритм же выдает 27 вариантов (3 варианта на 1ой позиции Х 3 варианта на 2ой позиции Х 3 варианта на 3ей позиции)

[@sinoikromov7322]

Одну минуточку was in есть в пайтоне 😉

[@barkas2589]

Спасибо

[@sergeyberezovskiy8366]

Тупо полностью скопировал код перестановки чисел. Он не работает от слова совсем. Может мне кто-то объяснить как у него ЭТО работает? У меня просто делает рестарт и не выводит НИЧЕГО, кроме >>>

[@MaxPV1981]

Поставил на паузу на 19:08, записал. Пытаюсь включить несколько раз - ничего. Потом замечаю, что что-то не так. Глаза у Тимофея двигаются. Стало страшно.

[@zerocool4eg]

Сортировка Хоара - лучший случай n log^2 n Сортировка слиянием - n log n Сортировка Хоара же быстрее выходить должна, почему здесь на доске одинаковые значения

[@romanivanov9266]

Вы ошиблись, сортировка Хоара (она же быстрая) имеет сложность n*log(n) в среднем.

[@nihonam]

год назад умеренно вникал в сортировки и их сравнение. Хоар хорошо работает на больших массивах, на мелких (меньше 20-30 элементов) может проигрывать.

[@Luka-se7sl]

47:03 Не понял почему надо было создать функцию find() когда можно было написать просто if (number in prefix):

[@sanakro5492]

Чтобы попрактиковаться в написании однопроходных алгоритмов, чисто в образовательных целях. Лектор об этом говорил. Конечно, и лучше, и проще, было бы сделать так, как вы написали. Получили бы тот же результат, только без написания велосипедов.

[@alexvb529]

Да Вы так шахматы сможете решить ;)

[@shaykhinurov]

И эту посмотрел.

[@logic0905]

на третей лекции пришла идея построить график кол-ва просмотров и лайков от номера лекции :)

[@Berseny]

Не буду утверждать ничего об ожидаемых прорывах отечественной школы программирования, хотя лекции качественные. А вот в обороноспособности нашей страны нет решительно никаких сомнений! С такими солдатиками для опытов по сортировкам нам ничего не страшно! Ура, товарищи! (если что, это легкая ирония, не отражающая реального положения дел в ВПК)

[@lebfrspb]

Спасибо!

[@ПетяШумский-л1ж]

from itertools import permutations работает значительно быстрее, значительно)

[@MrPemmmz]

дружище, конечно так можно, но смысл то в том что бы понять алгоритм и то как это работает.

[@denisporubov]

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

[@pyJlb]

ну дак и в чем же? накидываю от руки, накидываю, а в голову пока не приходит понимание 😬

[@pyJlb]

а, уже понял 😂

[@Pixel_Magic]

Я 13-летний школьник. Ты топ