Практика языка C (МФТИ, 2023-2024). Семинар 1.3. Числа Фибоначчи.

Рет қаралды 6,695

Күн бұрын

Практические занятия по языку 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)" , а не больше

Пікірлер: 19

@MikhailGoncharov-tl4cr 4 ай бұрын

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

@alex_s_ciframi 8 ай бұрын

Константин, спасибо за лекцию. Тут оговорка 1:04:55 - надо "assert(j

@user-pl9ek9du8p 7 ай бұрын

Наверное я никогда не погружался так глубоко в тему с числами Фибоначчи, и никто из моих преподавателей не обращал внимание на такие закономерности. Большое спасибо. Идея с кроликами тоже очень хорошая, переводит математическую абстракцию в плоскость реальных проблем, отсюда и мотивация и желания понять, как посчитать fib(200). Пробовать переворачивать строчки кода с r-value и l-value тоже очень хорошая идея, сразу как бы учит переворачивать любую строчку так в голове, чтобы понять, где какое value.

@ivankorotkov2563 8 ай бұрын

Наивный подход вычисления чисел фибоначи требует порядка фибоначи времени. В теории можно через время выполнения программы оценить значение результата. В конце порадовался за Марка, который скромно упомянул что прочитал несколько глав Кнута пока учился на физтехе. Емнип там каждый том состоит из двух глав, кроме возможно последних.

@pavel_trpn 9 ай бұрын

Спасибо за лекции, отличный материал! Признаюсь, ждал от первого курса МФТИ большей "прыти" в околоматематических вопросах (да и в области информатики тоже). В аудитории присутствуют олимпиадники, интересно?

@tilir 9 ай бұрын

Они на первом курсе пока что стесняются отвечать даже если знают ответ. Немного пообвыкнутся к концу первого семестра.

@user-de5wm3ik2v 6 ай бұрын

Спасибо, великолепный материал и лекция! Неоднократно сталкивалась с числами Фибоначчи в олимпиадных задачах и вопросах собеседований. Настолько интересно, просто и развернуто данная тема не рассматривалась нигде. Игра со спичками и объяснение алгоритма на примере кроликов великолепны. Про NAF, период Пизано и матричный метод ранее не знала. У автора есть бумажный сборник с задачами? Очень интересно порешать остальные HW. МФТИ ❤

@tilir 6 ай бұрын

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

@user-gl1bg3ef5m 9 ай бұрын

47:56 Оговорка: числа Фибоначчи растут чуточку медленнее, чем 2^n)

@tilir 9 ай бұрын

Да действительно, спасибо. Если бы росли быстрее метод бы очевидно не работал. Заговариваюсь под конец семинара.

@napalm20005 9 ай бұрын

Здравствуйте, пытаюсь осваивать трушное программирование средствами Oracle VM VirtualBox (накатил на нее Ubuntu). Не подскажите, кто-нибудь из данного потока студентов cmake использует?

@tilir 9 ай бұрын

Пока что задачи одномодульные. Многомодульные программы и сборка с make и cmake будут позже.