Курсовая работа: “Языки и технологии программирования” Коровы и быки

[quote]

Содержание

Введение …………………………………………….………………………. 3
1. Постановка задание ………….…………………………………………... 4
2. Описание использованного метода …………….…………………….… 5
3. Разработка алгоритма …………………………………..…………….… 14
4. Описание программы (язык Turbo Pasal) …………….….…………..… 15
4.1 Общие сведения ………………………………………….………..…15
4.2 Функциональное назначение ……………………………..………… 15
4.3 Описание логической структуры ……………………….……….... 15
4.4 Используемые технические средства …………………….……..... 16
4.5 Вызов и загрузка ………………………………………….……...…. 16
4.6 Входные и выходные данные ……………………………..………... 17
5. Описание программы (язык Turbo C) ……………………………..…… 18
5.1 Общие сведения ………………………………………………….…. 18
5.2 Функциональное назначение ………………..…………………….... 18
5.3 Описание логической структуры ……………….………………… 18
5.4 Используемые технические средства ………………….…………. 19
5.5 Вызов и загрузка ……………………………………….…………… 19
5.6 Входные и выходные данные ……………………………..………... 20
Заключение ………………………………………………………...……….. 21
Список литературы ………………………………………………………… 22
Приложение A. Листинг программы "Коровы и быки"
на языке Turbo Pascal 7.0 ……………………………………………..…… 23
Приложение B. Листинг программы "Коровы и быки"
на языке Turbo C ……………………………………….…………….…… 26
Введение
Осноновной целью курсового проекта является приобретение практических навыков по разработке алгоритмов реализации основных численных методов, комбинаторных задач (игровых задач), программ, реализующих эти алгоритмы. Поставленная цель достигается путем самостоятельной разработки алгоритмов решения задач с использованием численных методов и задач обработки сложноорганизованных объектов, программной реализации этих алгоритмов на языках Паскаль и Си.
Данная работа предстовляет собой курсовой прект, выполнение, которого является завершающим этапом изучения курса "Языки и технология программирования", позволяющим проверить свои знания по всему курсу и глубже специализироваться по одному из его разделов. В период выполнения курсовой работы необходимо приобрести и закрепить навыки работы со специальной литературой при разработке алгоритмов, программ по решению заданных задач.
Курсовой прект, на заданную тему, был разработан мною с целью демонстрирования полученных знаний по дисциплине "Языки и технология программирования".
1. Постановка задачи
Вариант задания - №26.
Постановка задачи, решение которой является основопологающей частью в составлении курсового проекта, представляет собой некую игровую ситуацию на заданную в методическом пособии тему. "Коровы и быки" - именно так называется задача, решение которой описано в курсовом проекте. Суть задачи, а по большому счету, игры заключается в следующем: программа выбирает с помощью датчика случайных чисел четырехзначное число с разными цифрами. Необходимо угадать это число. На каждом шаге играющий называет четырехзначное число, а программа сообщает, сколько цифр угадано (количество угаданных цифр и означает количество "быков") и сколько цифр угадано и стоит на нужном месте (количество угаданных и стоящих на нужных местах цифр именуется "коровами"). Например, если программой загадано число 1294, а играющий назвал 1423, он получит ответ: "одна корова, три быка". Данная постановка задачи является индивидуальным заданием, а за ее разработку я взялся по той причине, что игра "Коровы и быки" довольно-таки интересна по своему принципу и смыслу, к тому же она как-никак актуальна тем, что развивает не только память, но и логическое мышление.
2. Описание использованного метода
Методы сортировки
При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
1. количество присваиваний;
2. количество сравнений.
Все методы сортировки можно разделить на две большие группы:
1. прямые методы сортировки;
2. улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:
1. сортировка вставкой (включением);
2. сортировка выбором (выделением);
3. сортировка обменом («пузырьковая» сортировка).
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса сортировки. Прямые методы на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массивов) некоторые из прямых методов могут даже превзойти улучшенные методы.
Сортировка вставкой
Принцип метода заключается в том, что массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве не отсортированной части – все остальные элементы.
Таким образом, алгоритм будет состоять из n-1-го прохода (n-размерность массива), каждый из которых будет включать четыре действия:
1. взятие очередного i-го, не отсортированного элемента и сохранение его в дополнительной переменной;
2. поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
3. сдвиг элементов массива от i-1-го до j-1-го вправо, чтобы освободить найденную позицию вставки;
4. вставка взятого элемента в найденную j-ю позицию.
Для реализации данного метода можно предложить несколько алгоритмов, которые будут отличаться способом поиска позиции вставки.
Сортировка выбором
Принцип метода заключается в том, что необходимо найти (выбрать) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.
Сортировка обменом («пузырьковая» сортировка)
Принцип метода заключается в том, что слева направо поочередно сравниваются два соседних элемента, ели их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент (“всплыл” первый “пузырек”). И так далее. Всего требуется n-1 проход.
Сравнение прямых методов сортировки
Теоретические и практические исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.
Если сравнить рассмотренные прямые методы между собой, то в среднем методы вставки и выбора оказываются приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена (“пузырька”).
Метод перебора
Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.
Разобьем отрезок [a,b] на n равных частей точками деления:
xi=a+i(b-a)/n, i=0,...n
Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что F(xm) = min F(xi) для всех i от 0 до n. Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величены Eps=(b-a)/n.
Последовательный поиск
Алгоритм S.
(Последовательный поиск.) Имеется таблица записей R1,R2,..., RN снабженных соответственно ключами К1, К2,..., КN. Алгоритм предназначен для поиска записи с данным ключом К. Предполагается, что N >= 1.
S1. [Начальная установка.] Установить i  1
S2. [Сравнение.] Если К = Кi, алгоритм оканчивается удачно.
S3. [Продолжение.] Увеличить i на 1.
S4. [Конец файла?] Если i


Мақала ұнаса, бөлісіңіз: