Алгоритмы и структуры данных, семинар группы 158-2 — различия между версиями
(Добавил 14.01 strings.cpp) |
(Добавил 12.01 power.cpp) |
||
| Строка 71: | Строка 71: | ||
====Степень==== | ====Степень==== | ||
Предложить рекурсивный алгоритм вычисления неотрицательной степени числа. | Предложить рекурсивный алгоритм вычисления неотрицательной степени числа. | ||
| − | <div align="right">[Решение]</div> | + | <div align="right">[https://yadi.sk/d/bKiYylZYmz2cj Решение]</div> |
====Разворот списка (упражнение)==== | ====Разворот списка (упражнение)==== | ||
| Строка 78: | Строка 78: | ||
Пусть список имеет вид [1, 2, 3, 4, 5], тогда после применения функции reverse он должен выглядеть, как [5, 4, 3, 2, 1]. | Пусть список имеет вид [1, 2, 3, 4, 5], тогда после применения функции reverse он должен выглядеть, как [5, 4, 3, 2, 1]. | ||
<hr> | <hr> | ||
| − | :'''Re''': Кстати, | + | :'''Re''': Кстати, rроме рекурсивных функций принято еще выделять и рекурсивные структуры данных, к примеру [https://en.wikipedia.org/wiki/Linked_list списки] и [https://en.wikipedia.org/wiki/Binary_tree деревья]. В качестве подсказки воспользуйтесь итеративной версией функции, предложенной ниже. |
<div align="right">[https://yadi.sk/d/WLEAtqVxmwKVq [Подсказка]] [Решение]</div> | <div align="right">[https://yadi.sk/d/WLEAtqVxmwKVq [Подсказка]] [Решение]</div> | ||
Версия 01:03, 15 января 2016
Содержание
Правила игры
В основном все общение будет происходить с семинаристом курса, однако к проверке работы также будет привлекаться и учебный ассистент. Если у студента есть некоторые разногласия с ассистентом, то он всегда может обратиться к семинаристу, чтобы разрешить конфликт.
Семинарист: Симагин Денис, simagin.mail@yandex.ru
Ассистент: Владимир Гончаров, dev.zelta@gmail.com
Старайтесь не опаздывать на семинары, иначе вы можете прослушать важные анонсы, которые обычно будут проходить в начале занятий. А также пропустите много полезного. Приходите, будет интересно!
| День недели | Время проведения | Аудитория |
|---|---|---|
| |
|
|
| |
|
|
Структура курса
В ходе курса студентам будут предложены пять домашних заданий, практическая контрольная работа, а в заключении итоговый экзамен. Также в течении семестра необходимо активно участвовать в семинарах, решая задачки и выполняя практические упражнения, предусмотренные для самостоятельной работы.
Семинары
Вся ваша деятельность на семинарах делится на две части. Работа на семинаре и решение упражнений, которые вам даны для самостоятельного рассмотрения дома. Вы получаете плюсики за каждое решеное упражнение, а также за активное участие в семинаре, обычно это разбор небольшой задачи у доски (не более одного плюсика за занятие).
Упражнения стоит присылать на почту семинаристу, при этом тема письма должна строго удовлетворять формату. К примеру, меня зовут Симагин Денис и я хочу отправить задачу с первого семинар, тогда заголовок письма должен иметь вид
A12.01: Разворот списка - Симагин Денис.
Формула оценки
Оценка за семинары вычисляется следующим образом
OСеминар = Сн·N/Nmax,
N – количество набранных плюсов, Nmax – максимальное количество плюсов, Сн – нормирующий коэффициент (будет объявлен в конце семестра).
Оценка за домашние работы вычисляется как среднее за все 5 сданных работ. За работу в течении семестра студент получает накопленную оценку
OНакопленная = 0.2·ОКонтрольная + 0.6·ОДомашние задания + 0.2·ОСеминары.
Итоговая оценка складывается из накопленной оценки и экзамена
OИтоговая = 0.3·ОЭкзамена + 0.7·ОНакопленная.
Семинары
Семинар A12.01
- Знакомство с группой.
- Рассмотрение примеров использования рекурсии.
Факториал
Предложить рекурсивный вариант вычисления факториала.
- Re: Очевидно, что предложенная рекурсивная реализация факториала не является хвостовой рекурсией, однако существует итерационная версия алгоритма. Поэтому наличие хвостовой рекурсии является достаточным, но не обходимым условием наличия итерационного алгоритма.
Фибоначчи
Предложить рекурсивный вариант вычисления чисел Фибоначчи.
- Re: Показан пример сведения множественной рекурсии к одиночной.
Степень
Предложить рекурсивный алгоритм вычисления неотрицательной степени числа.
Разворот списка (упражнение)
Реализовать рекурсивную функцию reverse, которая обращает связи односвязанного списка в противоположную сторону. Таким образом последний элемент списка становится первым, предпоследний вторым, и т.д. Пусть список имеет вид [1, 2, 3, 4, 5], тогда после применения функции reverse он должен выглядеть, как [5, 4, 3, 2, 1].
- Re: Кстати, rроме рекурсивных функций принято еще выделять и рекурсивные структуры данных, к примеру списки и деревья. В качестве подсказки воспользуйтесь итеративной версией функции, предложенной ниже.
Семинар A14.01
- Множественная и одиночная рекурсии.
- Стек и куча.
- Мемоизация.
- Хвостовая рекурсия.
- Особенности реализации рекурсий.
- Принцип разделяй и властвуй.
- Бинарный поиск.
01 строки
Предложить рекурсивный алгоритм, выводящий всевозможные строки длины n из 0 и 1 в лексикографическом порядке.
- Re: В решении продемонстрированы все основные особенности реализации рекурсивных функций.
Бинарный поиск
Предложить рекурсивный алгоритм, производящий бинарный поиск элемента в отсортированном массиве.
- Re: Метод олицетворят подход разделяй и властвуй.
Ханойская башня - 1
Предложить рекурсивную функцию, печатающую последовательность перемещений (в формате (x, y), где x и y — номера стержней, с которого и на который перемещается диск), являющуюся решением задачи о Ханойской башне.
Алгоритм Евклида (упражнение)
Реализовать рекурсивную версию алгоритма Евклида для нахождения наибольшего общего делителя.
- Re: При правильном решении вы должны получить хвостовую рекурсию.
Ханойская башня - 2 (упражнение)
Реализовать рекурсивную функцию, получающую на вход число дисков Ханойской башни и выводящую состояние башень после каждого перемещения в оптимальном решении. Пример, n = 3, все диски на первом стержне:
- [3, 2, 1]
- []
- []
Состояние после перемещения верхнего диска на 3 стержень:
- [3, 2]
- []
- [1]
- Re: Для решения используйте задачу разобранную на семинре. Стержни можно смоделировать с помощью стека.
