Алгоритмы и структуры данных. Подгруппа 105-1 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(Новая страница: «==Материалы к занятиям== ===Занятие 1 (11.01.15)=== ==Полезные ссылки==») |
(→Занятие 1 (11.01.15)) |
||
| Строка 1: | Строка 1: | ||
==Материалы к занятиям== | ==Материалы к занятиям== | ||
| − | ===Занятие 1 ( | + | В каждом домашнем задании для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками. Решения после установленного дедлайна не принимаются. |
| + | |||
| + | ===Занятие 1 (12.01.15)=== | ||
| + | |||
| + | ====Домашнее задание (12.01 - 26.01)==== | ||
| + | Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами от 0 до 2^32. Числа распределены равномерно. Для первых 6 задач необходимо | ||
| + | * написать алгоритм на любом языке программирования или на псевдокоде, | ||
| + | * описать что можно считать наилучшим, средним и худшим случаями, | ||
| + | * для каждого из трёх случаев подсчитать отдельно количество операций сравнения и swap. | ||
| + | |||
| + | =====Задачи===== | ||
| + | # Дано три числа, требуется вернуть наименьшее. | ||
| + | # Дано три числа, требуется отсортировать их. | ||
| + | # Дана последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. | ||
| + | # * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена. | ||
| + | # * Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки последовательности из предыдущей задачи, который бы учитывал специфику входных данных. | ||
| + | # * Даны 32-ух битные неотрицательные числа m и n в двоичной записи. Требуется вывести True, если m < n, иначе False. Можно обращаться к i-тому биту и сравнивать биты. При оценке среднего случая постарайтесь примерно предсказать необходимо количество операций. | ||
| + | # Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи. Подсчитайте количество рекурсивных вызовов. | ||
==Полезные ссылки== | ==Полезные ссылки== | ||
Версия 02:06, 12 января 2015
Содержание
Материалы к занятиям
В каждом домашнем задании для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками. Решения после установленного дедлайна не принимаются.
Занятие 1 (12.01.15)
Домашнее задание (12.01 - 26.01)
Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами от 0 до 2^32. Числа распределены равномерно. Для первых 6 задач необходимо
- написать алгоритм на любом языке программирования или на псевдокоде,
- описать что можно считать наилучшим, средним и худшим случаями,
- для каждого из трёх случаев подсчитать отдельно количество операций сравнения и swap.
Задачи
- Дано три числа, требуется вернуть наименьшее.
- Дано три числа, требуется отсортировать их.
- Дана последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x.
- * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена.
- * Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки последовательности из предыдущей задачи, который бы учитывал специфику входных данных.
- * Даны 32-ух битные неотрицательные числа m и n в двоичной записи. Требуется вывести True, если m < n, иначе False. Можно обращаться к i-тому биту и сравнивать биты. При оценке среднего случая постарайтесь примерно предсказать необходимо количество операций.
- Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи. Подсчитайте количество рекурсивных вызовов.
