Практика языка C (МФТИ, 2023-2024). Семинар 1.3. Числа Фибоначчи.
Вставка
- Опубліковано 2 чер 2024
- Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом семинаре мы познакомимся с языком C, научимся писать простые функции и циклы и решим первые простые задачи.
Семинарист: Константин Владимиров.
Дата: 15 сентября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Числа Фибоначчи
12:45 Проблемы явной формулы
18:00 Переполнения
22:33 Периоды Пизано
31:15 Система счисления Фибоначчи
37:15 Время решать задачи
41:20 Игра с аудиторией
54:15 Ревью кода студентов
1:13:20 Lvalue и rvalue
1:19:06 Литература
Errata:
* 47:56 оговорка: числа Фибоначчи растут чуточку медленнее, чем 2^n
* оговорка 1:04:55 - надо "assert(j < NDEL)" , а не больше
ваши лекции настолько интересные, что в это сложно поверить. с вами любая лекция интересна, это однозначно
Константин, спасибо за лекцию.
Тут оговорка 1:04:55 - надо "assert(j
Наверное я никогда не погружался так глубоко в тему с числами Фибоначчи, и никто из моих преподавателей не обращал внимание на такие закономерности. Большое спасибо.
Идея с кроликами тоже очень хорошая, переводит математическую абстракцию в плоскость реальных проблем, отсюда и мотивация и желания понять, как посчитать fib(200).
Пробовать переворачивать строчки кода с r-value и l-value тоже очень хорошая идея, сразу как бы учит переворачивать любую строчку так в голове, чтобы понять, где какое value.
Наивный подход вычисления чисел фибоначи требует порядка фибоначи времени. В теории можно через время выполнения программы оценить значение результата.
В конце порадовался за Марка, который скромно упомянул что прочитал несколько глав Кнута пока учился на физтехе. Емнип там каждый том состоит из двух глав, кроме возможно последних.
Спасибо за лекции, отличный материал! Признаюсь, ждал от первого курса МФТИ большей "прыти" в околоматематических вопросах (да и в области информатики тоже). В аудитории присутствуют олимпиадники, интересно?
Они на первом курсе пока что стесняются отвечать даже если знают ответ. Немного пообвыкнутся к концу первого семестра.
Спасибо, великолепный материал и лекция! Неоднократно сталкивалась с числами Фибоначчи в олимпиадных задачах и вопросах собеседований. Настолько интересно, просто и развернуто данная тема не рассматривалась нигде. Игра со спичками и объяснение алгоритма на примере кроликов великолепны. Про NAF, период Пизано и матричный метод ранее не знала. У автора есть бумажный сборник с задачами? Очень интересно порешать остальные HW. МФТИ ❤
Почитайте Грэхема, Кнута и Паташника "Конкретная математика" если заинтересовались, там более подробно и есть много задач.
47:56
Оговорка: числа Фибоначчи растут чуточку медленнее, чем 2^n)
Да действительно, спасибо. Если бы росли быстрее метод бы очевидно не работал. Заговариваюсь под конец семинара.
Здравствуйте, пытаюсь осваивать трушное программирование средствами Oracle VM VirtualBox (накатил на нее Ubuntu). Не подскажите, кто-нибудь из данного потока студентов cmake использует?
Пока что задачи одномодульные. Многомодульные программы и сборка с make и cmake будут позже.
30:50 "Как поставить все элементы 1?" Можно так: int a[100] = { [0... 99] = 1};
це жарт такий?
Нет, это Designated Initializers
@@vdalart я знаю лиш ... = {[0]=1, [1]=2, .....}
Можно ли отправлять решения HWF и получать ревью и новые задачи тем, кто не является студентом МФТИ?
Можно но с немного более низким приоритетом проверки.