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

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.

На этом семинаре мы познакомимся с языком C, научимся писать простые функции и циклы и решим первые простые задачи.

Семинарист: Константин Владимиров.
Дата: 15 сентября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.

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)" , а не больше

[MikhailGoncharov-tlcr]

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

[alex_s_ciframi]

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

[ДенисКолчев-щс]

Наверное я никогда не погружался так глубоко в тему с числами Фибоначчи, и никто из моих преподавателей не обращал внимание на такие закономерности. Большое спасибо.

Идея с кроликами тоже очень хорошая, переводит математическую абстракцию в плоскость реальных проблем, отсюда и мотивация и желания понять, как посчитать fib(200).

Пробовать переворачивать строчки кода с r-value и l-value тоже очень хорошая идея, сразу как бы учит переворачивать любую строчку так в голове, чтобы понять, где какое value.

[ivankorotkov]

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

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

[pavel_trpn]

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

[Nika-yw]

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

[vdalart]

30:50 "Как поставить все элементы 1?" Можно так: int a[100] = { [0... 99] = 1};

[ВладиславБелов-уф]

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

[egorbasharin]

Можно ли отправлять решения HWF и получать ревью и новые задачи тем, кто не является студентом МФТИ?

[napalm]

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