Практика языка C (МФТИ, 2023-2024). Семинар 2.1. Простые числа.
Вставка
- Опубліковано 13 чер 2024
- Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом семинаре мы разберёмся с двумя крайне важными концепциями -- со структурами в языке и с асимптотикой алгоритмов. Для иллюстрации и того и другого я выбрал простые числа.
Семинарист: Константин Владимиров.
Дата: 22 сентября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Простые числа
06:25 Решето Эратосфена
15:02 Структуры в C
20:55 Площадь треугольника
27:03 Структуры для решета
32:15 Время решать задачи
35:40 O-нотация
51:43 Улучшаем алгоритм P
01:00:05 Упражнения с асимптотикой
01:08:00 Ревью кода и завершение
Errata:
* пока нет
Желаю вам крепкого здоровья !
Только зашёл)
На 1:12:45 скорее всего имеется в виду "спекулятвино увеличить" надо перед циклом for,а не внутри, как может показаться, "в надежде, что не нарвемся на if", а если все-такие нарвались, то откатить Count на один. Спасибо за видосы)
Константин, а где теоретическая часть курса? Лекции будут залиты на ютуб ?
Насколько я понимаю нет. Лекции читаю не я и их никуда не выкладывают. Поэтому я стараюсь записать все семинары максимально самодостаточными. Если вам не хватает теории, читайте K&R.
Спасибо, что выкладываете такой полезный материал!
(жаль только ссылка на слайды ко 2-му семинару нерабочая почему-то).
Пофиксил проверьте
@@tilirСпасибо, работает )
От разрядности чисел?)
Асимптотика на 1:07:20 скорее всего несколько выше, чем O(n), нам ведь еще нужно на каждой итерации считать что-то вроде lcm(i, result). O(n * log(lcm(2,...,n))) точно подойдет, но наверное, можно уже
Если числа M-битные, это добавляет множитель O(logM). Но для 32-битных чисел это константа, поэтому O(N) -- мы зависим только от общего количества чисел и съедаем их по одному.
Доброго дня будите ли дублировать канал на рутубе или в ВК ?
На рутубе давно есть: rutube.ru/channel/10218561
По поводу синтаксиса -> - на ютубе есть паренек, новосибирский, но вещает только на английском - он взял какой то очень простой компилятор сей и добавил точке право делать тоже самое что делает ->, и попробовал покомпилить библиотеки заменив эту стрелку точкой - ничего не сломалось. Технически от стрелки можно избавиться в пользу точки, зачем она нужна не понятно.
В языке C она нужна только потому, что это хорошая дизамбигуация для читающего код. Но кроме того это интересный случай гениального технического видения наперёд. В C++ это раскрылось: точка осталась обозначать id-expression, а стрелка стала перегружаемой и приобрела drill-down поведение и разница стала существенной.
На 30:55 формула написана математическим языком, соответственно правильно будет использовать для натурального логарифма символы "ln", а не "log".
G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 4th Ed., Oxford 1975, footnote to paragraph 1.7: "log x is, of course, the 'Naperian' logarithm of x, to base e. 'Common' logarithms have no mathematical interest".
@@tilirДа, так. Но если заглянуть в русские школьные учебники по алгебре, то там "ln".
Например, если загуглить (коммент с ссылкой наверно ютьюб не пропустит) "натуральный логарифм мфти", то одним из первых попадается учебник "Лекции по математическому анализу" Г.Е. Иванова. ("Содержание материала соответствует программе кафедры высшей математики МФТИ."
Я в свое время учился по подобному учебнику, поэтому такая ваша запись меня немного запутала )
Не надо путать матан и теорию чисел. Разные традиции обозначений.
@@tilir Понятно.
1:00:50: Я был бы чуть более аккуратным в вопросах O нотаций для комплексных функций. Для модуля, конечно, всё работает также, но вот с самими функциями...
Я не ввожу этих понятий для комплексных функций. Время и память это действительные числа. Вообще интересная идея -- найти комплекснозначный ресурс....
@@tilir (из Википедии): "Ресу́рс (от фр. ressource) - источник покрытия нужд, потребностей." Я думаю, квантовые состояния системы (волновые функции) подошли бы под это описания
Ближайшим циркулярным к 200 будет 199
Смотрел до 4-ой минуты, и сразу на вопрос как определить простое число, в двоичной системе счисления, ответ достаточно просто, если последний разряд (младший) оканчивается на 0, то число не простое, если на 1 то число простое, если же в десятичной то да, там уже сложнее.
Вы неправы. В двоичной системе число 9 имеет вид 1001. Оно тем не менее составное.
@@tilir Спасибо за поправку,согласен не прав.
Ты, видимо, хотел сказать о четном и нечетном числе)
@@unclemax1 Да, именно так