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

[@kotanvich]

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

[@MichaelSolovyev-l2y]

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

[@tilir]

Серьёзно? Это на какой минуте?

[@MichaelSolovyev-l2y]

@@tilirЭто я про задачу, в которой студенты в густую метель бегают по стадиону неизвестной формы, пытаясь понять, замкнутый он или нет. 21:15. Раз уж вы ответили, хочу сказать спасибо вам за эти записи!

[@kruassanorkiwi]

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

[@tilir]

Да тут не так просто поправить ошибку, надо серьёзно переделывать логику. Но студент в итоге разобрался. Я скорее просто указываю на то в чём проблема логически а не рекомендую конкретного фикса.

[@stanislavstanislavius7618]

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

[@tilir]

Не вижу проблем.

[@sibedir]

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

[@sibedir]

А. Всё. Увидел. В конце итеративный способ есть.

[@АлександрКондратьев-о1е]

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

[@tilir]

Представьте список где до петли сто элементов а сама петля два элемента. Заяц намотает полсотни петель пока черепаха дойдёт.

[@alexhitch9034]

Подскажите литературу хорошую литературу по структурам данных.. Можно и на английском

[@tilir]

На вводном уровне? Кормен и прочие, "Алгоритмы". Все практически важные структуры данных там разобраны. На продвинутом уровне -- зависит от агенды.

[@napalm20005]

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

[@dmitriy3510]

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

[@tilir]

Лучше аккуратно освободить ресурсы и вернуть код ошибки. Особенно если вы предполагаете что вашу программу могут использовать как библиотеку.

[@Aidar547]

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

[@tilir]

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

[@napalm20005]

А как же cmake?

[@tilir]

А что с ним? Чтобы дойти до систем сборки нам надо как минимум дойти до многомодульных программ. Это 4.3 минимум.

[@SeriousMan212]

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 в момент когда черепаха зашла на цикл -- весома.