Практика языка C (МФТИ, 2023-2024). Семинар 4.1. Односвязные списки. 

Лучшие лекции по си, а позитив и увлеченность преподавателя передаются через экран и заражают!

Благодаря этому семинару общественность узнала, как выглядят занятия физкультурой на физтехе

14:17 А диапазоны под бакеты может должны быть такими: [0, 83] [84, 167] [168, 251] [252, 335] [336, 419] [420, 503] [504, 670]

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

31:35 А почему для разворота списка, если есть требование "не использовать О(n) памяти", нам подходит рекурсия?

1:11:50 Если мы в данной реализации вставим проверку на равенство после первого шага, то на первой же итерации получим true (или false, но если сначала проверим на NULL и сразу на него попадем, но все еще оба указателя будут NULL). Или я что-то не так понимаю?

Константин, может быть у вас уже спрашивали - могут ли домашки отсылать нестуденты?

Вопрос по оформлению кода. Как лучше подходить к написанию функций. Лучше возвращать флаг успешной операции или кидать аборд? Ну например написать функцию чтения из файла, и если файла нет, возвращать из функции код 1 например и не кидать аборд. А в мейне уже обрабатывать этот флаг?

где можно взять старта на эти семинары, я просто чайник в этом. Хочется у вас учится, понятным языком объясняете)) только только устанавливаю линукс убунту Спасибо за семинары!

А как же cmake?

1:10:35 Утверждается, что тут ошибка у студента из-за того, что заяц перепрыгнет иногда черепаху и лишний круг сделает. Я не согласен и вот почему. Пусть t_0 -- длина маршрута до цикла, t -- длина цикла. Следующие две интуиции обосновываются ниже: 1. Новый if добавит нам примерно t_0 + t проверок. 2. Ситуация, когда заяц перепрыгнет черепаху лишь иногда уменьшит лишние t итераций и это не то чтобы частая ситуация. Док-во: Рассмотрим сперва ситуацию, когда черепаха только зашла на цикл спустя t_0 и заяц сделал два шага. Пусть расстояние заяца по циклу до нее -- m. При существующем алгоритме: 1. За каждую итерацию расстояние сокращается на 1 (= -2 + 1) и происходит проверка, что позиции совпали. 2. Таким образом m итераций. 3. Новый if тут ничего не изменит -- проверки и так есть на каждом уменьшении расстояния m на 1. Новый if только убыстрит в ситуации, если черепаха зашла на цикл, а заяц проскочил в этот момент черепаху. Т.е. когда m = 1 или 0 сразу после захода черепахи на цикл. 1. Без доп if мы имеем примерно лишние t итераций только для данной ситуации. 2. Но с новым if мы всегда имеем лишние t_0 + t проверок и иногда в ситуации выше меньше итераций на t. То есть даже когда эта ситуация прозошла все равно будет лишние t_0 проверок против t лишний итераций прежнего цикла. Цикл не выглядит очень сложным -- пара проверок, присваиваний. А в остальных случаях всегда будет t_0 + t лишних проверок. Оптимизация тут как-то сомнительна или требует доп мотивации со стороны уже скорости конкретных инструкций и только при странных распределениях t_0, t когда вероятность m = 1 и 0 в момент когда черепаха зашла на цикл -- весома.