Алгоритмы и структуры данных

1.

Алгоритмы и структуры
данных
практические занятия
Марквирер Владлена Дмитриевна
[email protected]

2.

Онлайн курс
• Алгоритмы: теория и практика. Структуры данных
• Ссылка на курс на степике: https://stepik.org/course/1547/promo
• Срок прохождения: в течение 2-3 модуля
(примерно к концу марта 2023 года).
• Нужно пройти курс с оценкой не ниже 8 баллов для тех, кто хочет
получить высокую итоговую оценку (оценка за онлайн курс будет
учитываться в 3-4 модуле).
• Формула второго модуля: 0,4*экзамен+0,3*практика+0,3*к/р
если без экзамена 7-8 баллов => на экзамен можно не идти;
если желаете итоговую 9-10 => обязателен экзамен.
13.11.2022
НИУ ВШЭ - Пермь
2

3.

13.11.2022
НИУ ВШЭ - Пермь
3

4.

Задачи с практики №5
в 1 модуле
«Взаимная и двойная рекурсия»

5.

Задача по взаимной рекурсии
• Необходимо сгенерировать все строки длины n в алфавите {0, 1}, в
которых нет двух подряд идущих нулей.
• Например, при n = 3, результатом будет {010, 011, 110, 101, 111}.
• Задача: реализовать рекурсивный алгоритм генерации таких строк,
при этом если будет выбран переборный алгоритм, то
максимальная оценка за это задание 0,4 балла (т.к. сложность
алгоритма экспоненциальная). Перебор можно использовать для
проверки.
• Воспользуйтесь материалами из лекции по взаимной рекурсии.
13.11.2022
НИУ ВШЭ - Пермь
5

6.

Задача по двойной рекурсии
• Рекурсивным методом вычислить число сочетаний