Поиск и сортировка элементов в списке. Задачи для самостоятельного решения

   
На этом шаге мы приведем задачи для самостоятельного решения.

   Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.
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.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий