Алгоритмы и структуры данных. Подгруппа 105-1

Материалы к занятиям

В каждом домашнем задании для получения максимального балла требуется решить или все задачи без звёздочек, или все задачи со звёздочками. Решения после установленного дедлайна не принимаются.

Занятие 1 (12.01.15)

Домашнее задание (12.01 - 26.01)

Во всех задачах, если не оговорено иного, предполагаем, что работаем с целыми неотрицательными числами от 0 до 2^32. Числа распределены равномерно. Для первых 6 задач необходимо

• написать алгоритм на любом языке программирования или на псевдокоде,
• описать что можно считать наилучшим, средним и худшим случаями,
• для каждого из трёх случаев подсчитать отдельно количество операций сравнения и swap.

Задачи

1. Дано три числа, требуется вернуть наименьшее.
2. Дано три числа, требуется отсортировать их.
3. Дана последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x.
4. * Дана упорядоченная последовательность A из n элементов и число x, требуется найти такое i, что A[i] равно x. Алгоритм должен быть эффективней, чем в предыдущем пункте и использовать то, что последовательность упорядочена.
5. * Дана последовательность из 100 000 чисел от 0 до 100. Напишите эффективный алгоритм сортировки последовательности из предыдущей задачи, который бы учитывал специфику входных данных.
6. * Даны 32-ух битные неотрицательные числа m и n в двоичной записи. Требуется вывести True, если m < n, иначе False. Можно обращаться к i-тому биту и сравнивать биты. При оценке среднего случая постарайтесь примерно предсказать необходимо количество операций.
7. Напишите рекурсивную функцию, вычисляющую n-ое число Фибоначчи. Подсчитайте количество рекурсивных вызовов.