Коровы и быки (Turbo Pascal)

Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 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. Немнюгин С. Pascal: Учебный курс. Санкт-Петербург: "Питер", 1999 г.
2. Рюттен Т., Франкен Г. Turbo Pascal 7.0. Киев: Изд. гр. "BHV", 1998 г.
3. Уэйт М., Прата С., Мартин Д. Язык СИ. Москва: "Мир", 1998 г.
4. Фаронов В. В. Turbo Pascal 7.0. Москва: "Нолидж", 2000 г.

Дисциплина: Информатика, Программирование, Базы данных
Тип работы: Реферат
Бесплатно: Антиплагиат
Объем: 22 страниц
В избранное:

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РЕСПУБЛИКИ КАЗАХСТАН

Казахский национальный технический университет им. К.И.Сатпаева

Институт информатики и информационных технологий

Кафедра технической кибернетики

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

Проверил: преподаватель

________________________

“___” _____________ 2002 г.

Выполнил: ст. гр._________

________________________

“___” _____________ 2002 г.

Алматы 2002 г.
Содержание

Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 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

Введение

Осноновной целью курсового проекта является приобретение практических
навыков по разработке алгоритмов реализации основных численных методов,
комбинаторных задач (игровых задач), программ, реализующих эти алгоритмы.
Поставленная цель достигается путем самостоятельной разработки алгоритмов
решения задач с использованием численных методов и задач обработки
сложноорганизованных объектов, программной реализации этих алгоритмов на
языках Паскаль и Си.
Данная работа предстовляет собой курсовой прект, выполнение, которого
является завершающим этапом изучения курса "Языки и технология
программирования", позволяющим проверить свои знания по всему курсу и
глубже специализироваться по одному из его разделов. В период выполнения
курсовой работы необходимо приобрести и закрепить навыки работы со
специальной литературой при разработке алгоритмов, программ по решению
заданных задач.
Курсовой прект, на заданную тему, был разработан мною с целью
демонстрирования полученных знаний по дисциплине "Языки и технология
программирования".

Постановка задачи

Вариант задания - №26.

Постановка задачи, решение которой является основопологающей частью в
составлении курсового проекта, представляет собой некую игровую ситуацию на
заданную в методическом пособии тему. "Коровы и быки" - именно так
называется задача, решение которой описано в курсовом проекте. Суть задачи,
а по большому счету, игры заключается в следующем: программа выбирает с
помощью датчика случайных чисел четырехзначное число с разными цифрами.
Необходимо угадать это число. На каждом шаге играющий называет
четырехзначное число, а программа сообщает, сколько цифр угадано
(количество угаданных цифр и означает количество "быков") и сколько цифр
угадано и стоит на нужном месте (количество угаданных и стоящих на нужных
местах цифр именуется "коровами"). Например, если программой загадано число
1294, а играющий назвал 1423, он получит ответ: "одна корова, три быка".
Данная постановка задачи является индивидуальным заданием, а за ее
разработку я взялся по той причине, что игра "Коровы и быки" довольно-таки
интересна по своему принципу и смыслу, к тому же она как-никак актуальна
тем, что развивает не только память, но и логическое мышление.

1. Описание использованного метода

Методы сортировки

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

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

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 = N, то вернуться к шагу S2.
В противном случае алгоритм оканчивается неудачно.
Заметим, что у этого алгоритма может быть два разных исхода: удачный
(когда найдено положение нужного ключа) и неудачный (когда установлено, что
искомого аргумента нет в таблице). Это справедливо для большинства
алгоритмов данного описания.

Алгоритм Q.
(Быстрый последовательный поиск). В отличие от алгоритма S здесь еще
предполагается, что в конце файла стоит фиктивная запись RN+1.
Q1. [Начальная установка.] Установить i ( 1 и КN+1 ( K
Q2. [Сравнение.] Если К=Кi, то перейти на Q4.
Q3. [Продвижение.] Увеличить i на 1 и вернуться к шагу Q2.
Q4. [Конец файла?] Если i = N, алгоритм оканчивается удачно; в противном
случае - неудачно (i = N + 1).

Алгоритм Т.
(Последовательный, поиск в упорядоченной таблице). Имеется таблица
записей R1,R2,..., RN, причем ключи удов летворяют неравенствам К1, К2,...,
КN. Алгоритм предназначается для поиска данного ключа К. В целях удобства и
увеличения скорости работы предполагается, что в конце таблицы расположена
фиктивная запись RN+1 ключ которой КN+1 = ∞ К.

Т1. [Начальная установка.] Установить I ( 1.
Т2. [Сравнение.]Если К = Ki, то перейти на Т4.
ТЗ. [Продвижение.] Увеличить i на 1 и вернуться к шагу Т2.
Т4. [Равенство?] Если К=Кi, то алгоритм оканчивается удачно. В противном
случае - неудачно, нужной записи в таблице нет.
Если величина К с равной вероятностью принимает все возможные
значения, то в случае удачного поиска алгоритм Т, по существу, не лучше
алгоритма Q. Однако отсутствие нужной записи алгоритм Т позволяет
обнаружить примерно в два раза быстрее.
Приведенные выше алгоритмы в целях удобства использовали индексные
обозначения для элементов таблицы; аналогичные процедуры применимы и к
таблицам в связанном представлении, так как в них данные тоже расположены
последовательно.

Алгоритмы сортировки
Проблема упорядочивания данных с практической точки зрения.
Сортировка применяется во всех без исключения областях
программирования, будь то базы данных или математические программы.
Практически каждый алгоритм сортировки можно разбить на три части:
• сравнение, определяющее упорядоченность пары
элементов;
• перестановку, меняющую местами пару элементов;
• собственно сортирующий алгоритм, который осуществляет сравнение и
перестановку элементов до тех пор, сока все элементы множества не будут
упорядочены.
Подобными свойствами обладают и те алгоритмы сортировки, которые
рассмотрены ниже.

Метод Шелла
Этот метод был предложен автором Donald Lewis Shеll в 1959 г.
Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить
массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга
элементы. Как
видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается
до единицы. Это означает, что на поздних стадиях сортировка сводится просто
к перестановкам соседних элементов (если, конечно, такие перестановки
являются необходимыми).

Метод Хoopа
Суть метода заключается в том, чтобы найти такой элемент множества,
подлежащего сортировке, который разобьет его на два подмножества: те
элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею
можно реализовать многими способами.

Метод Кнута - Морриса - Пратта
Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово:
X=x[1]x[2]... x[n] и просматривает его слева направо буква за буквой,
заполняя при этом массив натуральных чисел l[1]... l[n], где l[i]=длина
слова l(x[1]...х[i]) (функция l определена в предыдущем пункте). Словами:
l[i] есть длина наибольшего начала слова x[1]...x[i], одновременно
являющегося его концом. Какое отношение все это имеет к поиску подслова?
Другими словами, как использовать алгоритм КМП для определения того,
является ли слово A подсловом слова B?

Решение. Применим алгоритм КМП к слову A#B, где # - специальная
буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B
тогда и только тогда, когда среди чисел в массиве l будет число, равное
длине слова A.

Описать алгоритм заполнения таблицы l[1]...l[n].

Решение. Предположим, что первые i значений l[1]...l[i] уже найдены.
Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1].
Другими словами, нас интересуют начала Z слова x[1]...x[i+1, одновременно
являющиеся его концами -из них нам надо брать самое длинное. Откуда берутся
эти начала? Каждое из них (не считая пустого) получается из некоторого
слова Z' приписыванием буквы x[i+1] . Слово Z' является началом и концом
слова x[1]...x[i]. Однако не любое слово, являющееся началом и концом слова
x[1]...x[i], годится - надо, чтобы за ним следовала буква x[i+1].
Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова
x[1]...x[i], являющиеся одновременно его концами. Из них выберем подходящие
- те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное.
Приписав в его конец х[i+1], получим искомое слово Z.
Теперь пора воспользоваться сделанными нами приготовлениями и
вспомнить, что все слова, являющиеся одновременно началами и концами
данного слова, можно получить повторными применениями к нему функции l из
предыдущего раздела. Вот что получается: i:=1; 1[1]:=0; (таблица
l[1]..l[i] заполнена правильно).

while i n do begin
len:= l[i] (len - длина начала слова x[1]..x[i], которое является его
концом; все более длинные начала оказались неподходящими).

while (x[len+1]х[i+1]) and (len0) do begin {начало не подходит,
применяем к нему функцию l}
len:=l[len];
end;

{нашли подходящее или убедились в отсутствии}
if x[len+1]=x[i+1] do begin {х[1]..x[len] - самое длинное подходящее
начало}
l[i+1]:=len+1;
end else begin

{подходящих нет}
l[i+1]:= 0;
end;
i:=i+1;
end;

Доказать, что число действий в приведенном только что алгоритме не
превосходит Cn для некоторой константы C.

Решение. Это не вполне очевидно: обработка каждой очередной буквы
может потребовать многих итераций во внутреннем цикле. Однако каждая такая
итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1]
окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу
величина l[i] может возрасти не более чем на 1, так что часто и сильно
убывать она не может - иначе убывание не будет скомпенсировано
возрастанием.
Более точно, можно записать неравенство l[i+1]l [i] - (число
итераций на i-м шаге)+1 или (число итераций на i-м шаге)= l[i]-l[i+1]+1
Остается сложить эти неравенства по всем i и получить оценку сверху для
общего числа итераций. Будем использовать этот алгоритм, чтобы выяснить,
является ли слово X длины n подсловом слова Y длины m. (Как это делать с
помощью специального разделителя #, описано выше.) При этом число действий
будет не более C(n+m}, и используемая память тоже.

Придумать, как обойтись памятью не более Cn (что может быть
существенно меньше, если искомый образец короткий, а слово, в котором его
ищут - длинное).

Решение. Применяем алгоритм КМП ... продолжение

Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.