На этом шаге мы приведем задачи для самостоятельного решения.
Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.
1. Применение сортировки списков
1*. Используя любой алгоритм сортировки, в одноуровневом числовом списке найдите максимальный элемент.
2*. Используя любой алгоритм сортировки, в одноуровневом числовом списке найдите элемент, ближайший к минимальному.
3*. Дан одномерный числовой список. Напишите предикат, проверяющий, является ли он упорядоченным по убыванию (возрастанию).
4*. Напишите функцию для нахождения медианы числового списка, опирающуюся на следующий алгоритм: вначале произведите сортировку списка, а затем выберите "средний" элемент.
Указание. Медианой списка, содержащего n элементов, называется элемент, значение которого меньше (или равно) половины n элементов и больше (или равно) другой половины. Например, 22 является медианой списка [16,22,99,95,18,87,10].
5*. Найдите количество различных чисел среди элементов данного списка. Число действий должно быть порядка n*log2n.
Указание. Отсортируйте список, а затем посчитайте количество различных элементов, просматривая элементы списка по порядку.
2. Реализация алгоритмов сортировки
1*. Реализуйте сортировку выбором.
2. Реализуйте операцию "соединение двух списков" с помощью функции, объединяющей элементы двух списков на основе заданного теста:
> merge (<) [2,4,6,8,10] [3,5,7,11] [2,3,4,5,6,7,8,10,11] > merge (<=) [2,4,6,8,10] [2,4,6,8] [2,2,4,4,6,6,8,8,10] > merge (=) [2,4,6] [3,5,7,11] [2,4,6,3,5,7,11]
3*. Напишите функцию, реализующую следующий алгоритм сортировки обменами: последовательными просмотрами чисел a1,...,an найдите наименьшее i такое, что ai>ai+1. Поменяйте ai и ai+1 местами и возобновите просмотр с начала списка. Когда не удается найти i, список будет упорядочен.
4*. ([1]) Практически важный алгоритм сортировки таков: чтобы отсортировать список, выберем случайный его элемент b, и разобьём список на три части: меньшие b, равные b и большие b. Теперь осталось отсортировать первую и третью части: это делается тем же способом. Приведите рекурсивную реализацию этого алгоритма сортировки.
Замечание. Время работы этого алгоритма - случайная величина; можно доказать, что в среднем он работает C*n*log(n) единиц времени (на практике - он один из самых быстрых).
5*. Упорядочите целочисленный список по неубыванию следующим методом фон Неймана. Сформируйте два списка A и B и поместите исходный список в A; упорядочите пары соседних чисел (A1 и A2, A3 и A4 и т.д.) и запишите их в список B; возьмите из списка B по две соседние упорядоченные пары и, "слив" их в упорядоченные четвёрки, снова запишите в список A; затем каждые две соседние четвёрки из B "слейте" в упорядоченные восьмёрки и перенесите в список A и т.д.
6*. Докажите, что следующий функционал реализует сортировку заданного списка:
sortG :: (t -> t -> Bool) -> [t] -> [t]
sortG comp [] = []
sortG comp (a:x) = sortG comp sml ++ [a] ++ sortG comp lrg
where sml = [b | b <- x, comp b a]
lrg = [b | b <- x, comp a b]
--------------------------------------
test1 = sortG (>=) [4,3,5,2,6,1,2]
test2 = sortG (<) [4,3,5,2,6,5,5]
(1)Шень А. Программирование: теоремы и задачи. - М.: Моск. центр нач. матем. образования, 1995. - 264 с.; МЦНМО, 2004. - 296 с.
Со следующего шага мы начнем рассматривать моделирование массивов на языке Haskell.
