русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Проекты


Дата добавления: 2013-12-23; просмотров: 592; Нарушение авторских прав


Задачи

Сортировка черпаками

Если в процессе сортировки нужно хранить не только ключи, но и связанную с ними информацию, например, указатели на объекты, то нельзя обойтись подсчетом числа элементов одного вида, поскольку для каждого из элементов нужно сохранять связанную с ним информацию. В этом случае для каждого вида элементов нужно иметь свой "черпак" - массив, хранящий элементы данного вида. Алгоритм сортировки, как и в вышеописанном случае, состоит из двух этапов. На первом - заполняются черпаки, на втором - данные из черпаков сливаются в общий массив.

До сих пор разбиение элементов массива на виды осуществлялось с помощью представителей - к одному виду относились элементы с одним и тем же значением. Общий способ классификации состоит в задании классифицирующей функции - int Classification(int m, T item), которая для каждого элемента item возвращает число, задающее его вид. Аргумент m этой функции указывает максимальное число видов для этой функции классификации. Обычно предполагается, что значение, возвращаемое функцией, является целым числом в диапазоне [0, m-1], задавая номер вида. Примером такой функции классификации (оракула) является сортировочная шляпа из задачи Гарри Поттера, которая умеет по некоторым признакам ученика определить, к какому классу он должен принадлежать.

  • 65. Создайте Windows-проект для задачи "Красные и белые".
  • 66. Создайте Windows-проект для задачи Э. Дейкстры.
  • 67. Создайте Windows-проект для задачи "Сортировочная шляпа".
  • 68. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из трех значений, заданных в массиве представителей.
  • 69. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из трех видов. Вид элемента определяется функцией классификации, передаваемой методу сортировки в качестве параметра.
  • 70. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из четырех значений, заданных в массиве представителей.
  • 71. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из четырех видов. Вид элемента определяется функцией классификации, передаваемой методу сортировки в качестве параметра.
  • 72. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из m значений, заданных в массиве представителей.
  • 73. Создайте Windows-проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из m видов. Вид элемента определяется функцией классификации, передаваемой методу сортировки в качестве параметра.
  • 74. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortTwoKinds - процедуру сортировки массива типа T, содержащего элементы двух видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 75. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortTwoKinds - процедуру сортировки массива типа T, содержащего элементы двух видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 76. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortThreeKinds - процедуру сортировки массива типа T, содержащего элементы трех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 77. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortThreeKinds - процедуру сортировки массива типа T, содержащего элементы трех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 78. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortFourKinds - процедуру сортировки массива типа T, содержащего элементы четырех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 79. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortFourKinds - процедуру сортировки массива типа T, содержащего элементы четырех видов. Алгоритм должен выполняться за время порядка O(n), где n - число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 80. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortMKinds - процедуру сортировки массива типа T, содержащего элементы m видов. Виды элементов задаются массивом представителей. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 81. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortMKinds - процедуру сортировки массива типа T, содержащего элементы m видов. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows-проект, поддерживающий работу с этой DLL.
  • 82. На основе рассмотренного в этом разделе класса SortService постройте собственный класс, включающий различные методы сортировки для разных значений числа видов m. Постройте Windows-интерфейс, позволяющий клиентам класса вызывать его методы для массивов разных типов.
  • 83. Постройте проект, позволяющий сравнивать время, затрачиваемое компьютером на сортировку массива, когда применяются методы универсального класса SortService<T> и аналогичные методы, написанные для конкретного типа данных. Цель проекта - анализ возможных потерь эффективности, как плата за универсальный характер методов сортировки.
  • 84. Постройте проект, позволяющий сравнивать время, затрачиваемое компьютером на сортировку массива с элементами двух, трех, четырех и m видов, при использовании методов класса SortService и метода быстрой сортировки Хоара, встроенной в библиотеку FCL.


<== предыдущая лекция | следующая лекция ==>
Сортировка массивов с элементами m типов | А.А. Волосевич


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.001 сек.