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