Студент 1 курса, группы 107314

КУРСОВАЯ РАБОТА

по дисциплине: “Языки программирования”

на тему: ” Сортировка массива структур на основе структуры

Белорусский национальный технический университет

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К курсовому проекту (работе)

по дисциплине “языки программирования”

на тему: ” Сортировка массива структур на основе структуры

Студент 1 курса, группы 107314

Руководитель:_____Желакович И.М.

Минск 2015

СОДЕРЖАНИЕ

Белорусский национальный технический университет. 2

1. ВВЕДЕНИЕ. 5

2. ТЕОРЕТИЧЕСКИЙ ВОПРОС Дисковые алгоритмы-планировщики. 6

2.1 Алгоритм лифта (англ.) — дисковый алгоритм планирования, который работает как лифт. 6

2.2 Алгоритм кратчайшего перемещения (англ.) — дисковый алгоритм планирования для уменьшения времени поиска. Хотя поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков. 6

Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы. 6

Типичной проблемой в поиске пути является обход препятствий. Наипростейшим подходом к проблеме является игнорирование препятствий до столкновения с ними. Такой алгоритм будет выглядеть примерно так: 6

Этот подход прост, так как он предъявляет совсем немного требований: все, что необходимо знать - это относительные положения объекта и его цели, и признак блокирования препятствием. Для многих игровых ситуаций этого достаточно. 6

Различные стратегии обхода препятствий включают в себя: 6

2.2.1 Перемещение в случайном направлении. 6

Если препятствия маленькие и выпуклые, объект (показан зеленой точкой) может, вероятно, обойти их путем небольшого смещения в сторону до тех пор, пока не достигнет цели (показана красной точкой). Рисунок 1А показывает, как работает такая стратегия. Проблемы у этого метода возникают, если препятствия большие или вогнутые, как показано на рисунке 1Б - объект может полностью застрять или как минимум потерять много времени, пока не будет найден обходной путь. Существует только один способ избежать этого: если проблему очень трудно преодолеть, то измените игру так, чтобы эта проблема никогда не возникала. То есть, убедитесь, что в игре никогда не будет вогнутых объектов. 6

2.2.2 Трассировка вокруг препятствия. 6

К счастью, существуют другие методы обхода. Если препятствие большое, можно коснуться рукой препятствия и следовать контуру препятствия, пока она не обойдено. Рисунок 2А показывает, как хорошо этот метод работает с большими препятствиями. Проблема с этим методом состоит в принятии решения - когда же прекратить трассировку. Типичной эвристикой может быть: "Остановить трассировку при передвижении в направлении, которое было желаемым в начале трассировки". Это будет работать во многих случаях, однако рисунок 2Б показывает, как можно постоянно кружить внутри препятствия не находя пути наружу. 7

2.2.3 Надежная трассировка. 7

Более надежная эвристика пришла из работ над мобильными роботами: "При блокировании, вычислить уравнение линии из текущей позиции к цели. Трассировать до тех пор, пока эта линия не пересечена снова. Прервать работу, если вы опять попали в начальную позицию". Этот метод гарантирует нахождение пути вокруг препятствия, если он есть, что показано на рисунке 3А. (Если изначальная точка блокирования между вами и целью при пересечении линии, ни в коем случае не останавливайте трассировку, чтобы избежать дальнейшего зацикливания) Рисунок 3Б показывает обратную сторону этого подхода: зачастую требуется гораздо больше времени на трассировку чем необходимо. Компромисс состоит в комбинации обоих подходов: всегда использовать эвристику попроще для остановки трассирования, но если зафиксировано зацикливание, переключаться на надежную эвристику. 7

3. ПРАКТИЧЕСКИЙ РАЗДЕЛ.. 8

3.1. Математическая формулировка задачи. 8

3.2. Описание программы. 9

3.3. Блок-схема алгоритма: 11

4 Контрольный пример. 12

5. ВЫВОДЫ.. 17

6. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.. 18

7. Приложение А.. 19

8. Приложение B. 31

ВВЕДЕНИЕ

Цель курсовой работы - закрепление и углубление знаний, полученных при изучении курса «Основы алгоритмизации и программирования» посредством разработки программного обеспечения на языке С++; нaучитьcя практический применять полеченные теоретический знания пpи решении конкретных вопросов; нaучитьcя пользоваться справочной литературой.

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

· Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O (n log n) и плохое поведение — это O (n ²). Идеальное поведение для упорядочения — O (n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в Ω(n log n) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O (n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О -обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O (log² n) операций. При этом число n должно быть заранее известно.

ТЕОРЕТИЧЕСКИЙ ВОПРОС Дисковые алгоритмы-планировщики.

Алгоритм лифта (англ.) — дисковый алгоритм планирования, который работает как лифт.

2.2 Алгоритм кратчайшего перемещения (англ.) — дисковый алгоритм планирования для уменьшения времени поиска. Хотя поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков.

Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы.

Типичной проблемой в поиске пути является обход препятствий. Наипростейшим подходом к проблеме является игнорирование препятствий до столкновения с ними. Такой алгоритм будет выглядеть примерно так:

Этот подход прост, так как он предъявляет совсем немного требований: все, что необходимо знать - это относительные положения объекта и его цели, и признак блокирования препятствием. Для многих игровых ситуаций этого достаточно.

Различные стратегии обхода препятствий включают в себя: