Создание приложения игры 'Быки и коровы'

Курсовая работа

Создание приложения игры «Быки и коровы»

Введение

Глава 1. Основы программирования во Free Pascal

.1 Реализация основных алгоритмических структур Free Pascal

1.2 Средства разработки программ на языке Free Pascal

Глава 2. Разработка приложения во Free Pascal

.1 Алгоритм игры «Быки и коровы»

.2 Разработка игрового приложения «Быки и коровы»

Заключение

Введение

Язык Pascal, изобретенный в начале 70-х годов 20-го века Н. Виртом и названный в честь французского математика и философа Блеза Паскаля, является одним из наиболее распространенных языков программирования для обучения. Что вполне естественно, так как является структурированным, логичным, легко читаемым и понимаемым. Программа на языке Pascal состоит из двух частей: описание действий, которые должны быть выполнены и описание данных, над которыми они выполняются. В тексте программы описание данных предшествует описанию действий. В этом выражается общее правило языка - каждый встречающийся в программе объект должен быть предварительно описан.

Для того чтобы писать и выполнять программы, необходимы компилятор и среда разработки. Существует довольно много компиляторов для языка Pascal. Основным компилятором является Borland Pascal 7.0.Он применяется в основном для консольных приложений. Его логичным продолжением является визуальная среда разработки Borland Delphi. Данный инструмент предназначен для визуального проектирования и создания различных оконных приложений. Методы, подходы, принципы, применяемые в Delphi, сокращают в разы время разработки и поднимают на новый уровень качество разработки. Для того чтобы создать простое окно не надо писать строчки кода, нужно просто нажать на кнопку создания окна. То же самое можно сказать и про множество компонентов, используемых Delphi.

В последние 15 лет велась активная разработка альтернативы компилятору Borland Pascal. Она получила название Free Pascal. Free Pascal Compiler (FPC) это свободно распространяемый компилятор языка Pascal с открытыми исходными кодами, распространяется на условиях GNU General Public License (GNU GPL). Он совместим с Borland Pascal 7.0 и Object Pascal Delphi, но при этом обладает рядом дополнительных возможностей, например, поддерживает перегрузку операторов.Pascal Compiler имеет свою собственную интегрированную среду разработки. Применяется также аббревиатура IDE (Integrated Development Environment). Среда имеет текстовый интерфейс очень похожий на интерфейс Turbo Pascal 7.0.

Глава 1. Основы программирования во Free Pascal

.1 Реализация основных алгоритмических структур во Free Pascal

Основные виды алгоритмов (алгоритмических структур):

. Линейный алгоритм (еще называют следование);

. Разветвляющийся алгоритм;

. Циклический алгоритм;

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

Задачи, имеющие линейные алгоритмы решения.

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

Рассмотрим задачу: Троллейбус, трогаясь с места, двигается с ускорением a=1,5м/с2 . Какую скорость он приобретёт через время t? Какое расстояние он при этом пройдёт?

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

В рассматриваемой задаче известными величинами (судя по тексту), являются ускорение и время движения. Причем, значение ускорения дано, а ввод значение времени нужно запланировать во время работы программы. Неизвестные скорость и расстояние можно найти по формулам:

=a*t, S=v*t/2

Затем нужно определить тип и вид величин, которые будут использоваться в задаче. По виду простые величины (в программировании они все называются данными) делятся на константы и переменные. Тип данного определяет, в каком виде оно хранится в компьютере и какие значения может принимать.

Некоторые простые типы:

Целые типы (ShortInt, Integer, LongInt, Byte, Word).

Вещественные типы (Real, Single, Double, Extended, Comp).

Логический (Boolean).

Символьный (Char).

Строковые типы (String, String [n]).

Если переменная в процессе выполнения программы может принимать значение дробного числа, участвует в выражениях с умножением, делением, математическими функциями, то ее нужно определить как вещественную, если значение ее - буква, то это - символьная переменная, если значение - слово, то переменная - строкового типа. Различия между переменными типов одной группы более тонкие, и первое время можно не вдумываться в эти отличия, а использовать в качестве целого - тип Integer, в качестве вещественного - тип Real, в качестве строкового - тип String.

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

План (алгоритм) рассмотренной задачи:

.Описание констант и переменных a, t, v, S.

. Ввод t, a.

. Вычисление v, S.

. Вывод v, S.

Программа на языке Паскаль:

В языке программирования Паскаль программа состоит из заголовка, раздела описаний и исполняемой части. Данная программа имеет заголовок «Troll», раздел описаний состоит из объявления констант и переменных в блоках const и var соответственно. Исполняемая часть начинается с оператора begin и заканчивается оператором end. В фигурных скобках пишутся комментарии, они написаны для лучшего понимания программы человеком, компьютер их игнорирует и не выполняет.

Программа состоит из команд языка Паскаль, называемых операторами. Практически каждый оператор заканчивается точкой с запятой. Компьютер выполняет операторы последовательно, один за другим. Сначала будет выполнен первый оператор write. При этом на экране появится «подсказка» пользователю, будут выведены слова: «Введите время t » (без кавычек). Затем начнется выполнение оператора ввода с клавиатуры read(t). Компьютер при этом будет ожидать ввода с клавиатуры числа (т.к. переменная t -вещественная). После его ввода и нажатия клавиши ввода (Enter), переменная t примет значение, введенное с клавиатуры. Затем последовательно будут вычислены значения переменных v и s. Операторы writeln в конце программы выведут на экран переменные t, v, s. В операторе writeln (или write) все, что необходимо вывести на экран перечисляется через запятую. Если набор символов записан в апострофах (строковая константа), то эти символы будут выведены на экран без изменений, за исключением апострофов. Если в списке содержится имя переменной (например, t), то будет выведено ее значение.

Г) Контрольный пример.

при a = 1.5 t = 1

                                                 a • t2

v = a • t = 1.5 S = ------------------------------ = 0.75

                                                   2

На самом деле, на экране появится следующий результат:

Форматированный вывод

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

При использовании форматов для вывода значений в текстовые файлы или на экран около имени выводимого данного явно указывается размер поля для размещения его значения.

Форматы для данных различных типов:

Для целых данных (integer и др.) - формат задается одним числом, определяющим число позиций, отводимых на это число. Например:(i:5);

Для вещественных данных (real и др.) - формат задается либо одним числом, определяющим число позиций, отводимых на это число в экспоненциальной форме; либо двумя числами, первое из которых обозначает общий размер поля, отведенного под это число, второе - число знаков после запятой. Например:(p:10); или Writeln(p:6:2); Для строковых и символьных данных (string, char) - формат задается одним числом, определяющим число позиций, отводимых на значение этих данных (т.е. на символ или набор символов). Например:(d:10);

Если в разобранной выше задаче переписать оператор, который выводит на экран значение времени и скорости, таким образом:(‘ За ’,t:6:2,’ сек. скорость троллейбуса v=’,v:5:1,’ м/с’);

то на экране появится

Запись констант с порядком

Очень большие числа в алгебре принято представлять в виде степеней числа 10. В языках программирования такая запись тоже практикуется и называется она нормализованная (экспоненциальная) форма. Например, число -1,17*108 записывается как -1.17E+08 или -1.17E8.

Несколько примеров простых линейных программ.

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

Задачи с ветвлением

На практике часто встречаются задачи, в которых, в зависимости от некоторого условия, выполняются те или иные действия. Например, общее сопротивление участка цепи из двух резисторов находится по разным формулам, в зависимости от типа соединения. Значение функции можно рассчитать, если аргумент принадлежит области её определения. Рассмотрим такую задачу подробнее.

 =

Решение.

Найти значение функции можно, подставляя значение x в формулу для f(x), если она определена. Расчет значения функции возможен, если А=х2 - 3х - 15 > 0, при A £ 0 то функция не определена.

План:

а)      описание переменных x, f, A

б)      ввод x

в)      расчет A= x2 - 3х - 15

Написать программу с выполнением разных действий, в зависимости от значения А (как предусмотрено в п. г) можно, если использовать условный оператор.

Условный и составной операторы

Для реализации ветвления можно использовать условный оператор:

игровой цикл алгоритмический pascal

if условие then оператор1оператор2;

где условие - это выражение логического типа (например, а>0, (d<0) and (c=5) и другие). При выполнении такого оператора, компьютер проверяет, выполняется ли условие. Если условие верно, то выполняется ветвь then, т.е. оператор1; если условие не выполняется - то ветвь else - оператор2.

Если в какой-либо ветви нужно выполнить не один, а несколько операторов, необходимо поместить эти операторы внутри составного оператора begin ... end, как в приведенной ниже программе. В этом случае последовательность операторов, объединенная в группу внутри begin ... end рассматривается как один оператор или блок. Составной оператор используется в тех случаях, когда по правилам языка допускается использовать только один оператор, а требуется выполнить несколько действий. Такой случай часто возникает при написании условных операторов, операторов выбора и цикла.

Описанную выше задачу реализует программа:

vetv; var x, f, A: real; begin

write(‘Введите x ’); read(x);:=sqr(x) - 3*x - 15; if A>0 then:=1/sqrt(A);(‘f(‘,x:4:1,’)=’,f:7:3);

endwriteln (‘при x=’,x:4:1,’ функция не определена’);.

Обратите внимание на то, что так как составной оператор стоит в ветви then, и после него условный оператор не заканчивается (есть ветвь else), то точка с запятой (знак конца оператора) не поставлена.

Если бы по логике задачи нужно было бы выполнить несколько действий в ветви else, то составной оператор нужно было бы использовать и там. Например: if A>0 then

:=1/sqrt(A);(‘f(‘,x:4:1,’)=’,f:7:3);(‘при x=’,x:4:1,’ функция не определена’); writeln (‘A=’,A:6:2); end;

Усеченный условный оператор и оператор exit.

Возможно использование усеченного условного оператора if условие then оператор;

При этом, если условие не выполняется, то ветвь then игнорируется и управление передается следующему за if оператору.

Кроме того, в программе иногда удобно использовать оператор exit, чтобы досрочно прекратить ее выполнение.

Задача. Написать программу, которая рассчитывает работу 1 моля газа в течении одного из изопроцессов. Начальные температура, объем и давление известны. Программа запрашивает наименование процесса и недостающие параметры.

Решение

Обычно рассматриваются три вида изопроцессов:

Изобарический (p-const). Работа газа A = p(V2 - V1);

Изотермический (T-const). Работа газа

Изохорический (V-const). Работа газа A = 0

Приведенная ниже программа написана так, что человек сначала вводит с клавиатуры номер изопроцесса. Если процесс изохорический, то расчет производить не надо, программа сообщает результат (А=0) и заканчивает работу (по оператору exit). Если процесс не изохорический, то вводятся с клавиатуры начальный и конечный объемы газа, а затем, в зависимости от номера изопроцесса, запрашиваются дополнительные данные и производится расчет по соответствующей формуле. Использование логических операторов позволяет запрашивать только необходимые данные.

vetv_1; const R=8.31; var i:integer;

p,V1,V2,T, A: real; begin(‘Выберите изопроцесс: 1.p-const; 2.T-const; 3.V-const ’); read(i);i=3 then begin(‘Изохорический процесс А=0’);;;

write(‘Введите начальный и конечный объем '); read(V1,V2); if i=1 then begin(‘Изобарический процесс ’); write(‘Введите давление '); read(p);

A:=p*(V2-V1);

begin(‘Изотермический процесс ’); write(‘Введите температуру '); read(T);

A:=R*T*ln(V2/V 1); end;

writeln (‘Работа газа А=’,А:6:1,’ Дж’); end.

Несколько примеров написания условного оператор

Оператор выбора.

Если для решения задачи нужно организовать более двух ветвей, удобно использовать оператор выбора CASE. Общий вид оператора:

селектор of

значение 1: оператор 1; значение 2: оператор 2;

значение N: оператор N; else         оператор;

где селектор это переменная или выражение целого, символьного (char) типов, допустимы и некоторые другие типы. Набор значений - это конкретные значения сектора, при которых будет выполнен соответственно нужный оператор.

Работа оператора: сначала вычисляется значение селектора, если он является выражением. Затем выполняется тот оператор, который соответствует значению, совпадающему со значением селектора. Если значение сектора не совпало ни с одним из указанных значений, то выполняется ветвь else.

Рассмотренную в п.2.1. задачу, можно написать с помощью этого оператора:

vetv2; var, f, A: real; n: integer; begin(‘Введите x ’); read(x);

A:=sqr(x) - 3*x - 15;:=ord(A>0);     { функция ord( ) равна 1, если выражение в}

{ скобках верно, и 0 , если неверно}n of

: writeln(‘ функция не определена’);

1: begin:=1/sqrt(A);(‘x=’,x:4:1,’      f=’,f:6:3);;writeln(‘ Такого случая нет’); end; end.

Циклические алгоритмы

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

Цикл с параметром (счетный цикл).

Общий вид оператора:параметр:=нач_значение To кон_значение Do оператор

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

Порядок выполнения оператора.

Вычисляются (если нужно) начальное и конечное значения параметра и фиксируются;

Если нач_значение<= кон_значения, то параметр= нач_значение и выполняется оператор;

Значение параметра цикла возрастает (для целого - на единицу);

Если значение параметра Ф кон_значения, то выполняется оператор,

и компьютер снова переходит к выполнению п.3

Цикл выполняется последний раз, когда параметр= кон_значению, затем управление передается оператору после цикла.

Оператор (n- переменная целого типа) for n:=1 to 9 do a:=10*n; будет выполняться для значений параметра n=1,2,3,4,5,6,7,8,9. При этом переменная а будет принимать значения а=10,20,30,40,50,60,70,80,90.

Для того, чтобы увидеть эти значения на экране, нужно записать оператор цикла в виде for n:=1 to 9 do begin a:=10*n; writeln(n,’ ‘,a); end;

В этом случае, на каждом шаге цикла рассчитывается значение переменной а и выводятся на экран значения переменных n и а. Так как после служебного слова do в счетном цикле должен стоять только один оператор, использован составной оператор begin. end, внутрь которого и записываются все необходимые операторы. Таким образом, этот цикл начинается служебным словом for и заканчивается служебным словом end.

Другой пример цикла с параметром (m- переменная символьного типа):

m:=’a’ to ‘z’ do write(‘ ‘, m);

Этот цикл распечатывает через пробел на экране латинские буквы a, b,c,d,...z.

Важно понимать, что оператор цикла сам организует изменение параметра, и для целого параметра это изменение всегда равно 1. Попытка изменить значение параметра внутри цикла приводит к трудно распознаваемым логическим ошибкам, поэтому категорически не рекомендуется! Если по условию задачи необходимо изменять значения с другим шагом h, опишите другую переменную (x) и изменяйте её на каждом шаге цикла, например, с помощью оператора x:=x+h; или так как показано ниже, в примере №4.

Несколько примеров написания оператора цикла с параметром

Цикл с предусловием. Циклическим называется процесс многократного повторения некоторого участка вычислений при изменении хотя бы одной из входящих в него величин. Если в задаче число повторений заранее не известно, цикл for использовать неудобно и можно воспользоваться оператором цикла while (общий вид):

while условие DO оператор;

Где условие - логическое выражение, оператор может быть простым или составным.

Порядок выполнения оператора.

Сначала проверяется условие: если оно верно, то выполняется оператор, затем опять проверяется условие и т.д., пока условие не перестанет выполняться. Если условие не верно, то оператор игнорируется и управление передается следующему за циклом оператору.

Пример цикла с предусловием: while n <9 do n:=n+1;

В этом операторе значение переменной n на каждом шаге цикла возрастает на 1. Однако, сколько шагов будет у цикла, зависит от значения переменной n до цикла. Если до цикла n=0, то выполнение оператора тела цикла n:=n+1 повторится 9 раз, при n=8 - 1 раз, а при n=9 -цикл выполняться не будет. Необходимо помнить, что цикл while начинает выполняться, когда условие верно, и заканчивается, когда условие становится неверным. Следовательно, его нужно писать так, чтобы в условии были переменные или функции, которые меняются внутри цикла и он мог когда-нибудь закончиться. В противном случае, цикл будет выполняться бесконечно, т.е. программа «зациклится». Чтобы прервать выполнение такой неудачной программы, необходимо подать команду ctrl+c.

Приведенный выше оператор не имеет практической ценности, так как на каждом шаге только изменяет значение переменной n, которая играет роль номера шага цикла. Для организации расчета и распечатки нескольких значений, необходимо записать соответствующую группу операторов внутри составного оператора: n:= 0;

n <9 do begin:=n+1; a:=10*n; writeln(n,’ ‘,a);

end;

Этот оператор, как и оператор for в п.3.1, выведет на экран попарно значения переменной n=1,2,3,4,5,6,7,8,9 и переменной а=10,20, 30,40,50,60,70,80,90.

Несколько примеров написания оператора цикла с предусловием

Цикл с постусловием.

Общий вид оператора: Repeat

Оператор 1;

Оператор 2;

Оператор N;условие;

Работа оператора: выполнение операторов 1- N повторяется, пока условие не станет верным.

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

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

Несколько примеров написания оператора цикла с предусловием

Распечатка таблиц функций

Задача: Рассчитать таблицу значений функции f(x) = x3 eSin x

для xe [1, 10].

Решение: В таких задачах предполагается, что необходимо рассчитать и распечатать таблицу значений аргумента и данной функции с некоторым шагом h. Обозначим предельные значения аргумента x0=1 и xk=10.

Равноотстоящие значения аргумента х всегда можно рассчитать по формуле

=x0 + h*i

где i - целое число i =0,1,2,...

Если пользователь сам выбирает значение шага изменения аргумента h, то число значений х (равное числу строк будущей таблицы) можно рассчитать по формуле

=целая_часть[(xk-x0)/h]+1.

Можно, наоборот, выбрать число строк и рассчитать шаг h=( xk- x0)/(ik-1). Если в нашей задаче выбрать шаг таблицы h = 1, получим ik=( xk- x0)/h+1=10 строк таблицы. Обозначим номер строки таблицы i, тогда значения аргумента в i-той строке можно рассчитать по формуле

= x0 + h*i

значение i = 0 ik (эта запись означает, что i изменяется от до ik). Для каждого значения x можно рассчитать значение функции. План программы:

а)      описать переменные x, x0, h, xk, i, f

б)      ввести x0, h, xk

в)      распечатать заголовок таблицы

г)       рассчитывать и печатать значения x, f(x) пока xi £ xk.

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

Программа с использованием цикла с параметром.

chikl 1; var, xk, x, h, f: real; ik, i: integer;('Введите x0,xk,h '); read(x0, xk, h); ik:=trunc((xk-x0)/h); writeln('Таблица функции');('    ');('| x | f |' );('        ');i:=0 to ik do begin x:=x0 + i * h;:= exp(3 * ln(x)) * exp(Sin(x)); writeln(' | ',x:5:1,' | ',f: 10:3,' | '); end;

writeln('      ');.

В данной программе учтено, что в языке Паскаль нет операции возведения в степень, поэтому х3= exp(3ln(x)). Ввод трех значений в операторе read(x0, xk, h) производится через пробел.

Функция trunc(..) используется для получения целого значения в правой части оператора присваивания, так как по правилам языка Паскаль целой переменной ik можно присвоить только целое значение.

Результат выполнения программы:

Программа с использованием цикла с предусловием.

chikl2; var, x0, xk, h,f: real; begin('Введите x0, xk,h '); read(x0, xk, h); writeln('Tаблица функции');('         ');('| x | f |' );('        ');:= x0;

while x <= xk do {        Оператор   после          do     выполняется}      {        пока         условие      x <= xk верно}:= exp(3 * ln(x)) * exp(Sin(x)); { Здесь оператором тела

цикла }:= x + h;  { является составной оператор}

writeln(' | ',x:5:1,' | ',f: 10:3,' | '); end;

Обратите внимание, что в этой программе использован другой способ подсчета х.

Программа с использованием цикла с постусловием.

chikl3; var, x0, xk, h,f : real; begin('Введите x0,xk,h '); read(x0, xk, h); writeln('Таблица функции');('         ');(' | x |       f        |'        );

writeln('      ');:= x0;       {        Операторы         между        repeat         и       until         выполняются}

{ пока условие x >xk не станет верно} f:= exp(3 * ln(x)) * exp(Sin(x)); writeln(' | ',x:5:1,' | ',f: 10:3,' | '); x:= x + h; until x>xk;('    ');.

.2 Средства разработки программ на языке Free Pascal

Язык программирования Free Pascal является свободным ответвлением от классического языка Pascal, разработанного Никлаусом Виртом в конце 60-х годов. Н. Вирт разработал данный язык для обучения студентов навыкам процедурного программирования. Со временем язык Pascal был сильно развит, возникло множество диалектов данного языка (наиболее известный из них - Turbo Pascal фирмы Borland).Pascal является свободной реализаций языка Pascal (если быть точнее, свободно распространяемый компилятор языка программирования Pascal), поддерживает объектно-ориентированное программирование и может быть использован для написания не только учебных программ, но и более серьезных приложений обработки данных.

Среда программирования Free Pascal

Рассмотрим процесс установки.

1) Для пользователей ОС Windows необходимо скачать инсталлятор с интернет-страницы <#"871328.files/image009.gif"> <#"871328.files/image010.gif"> <#"871328.files/image011.gif"> <#"871328.files/image012.gif"> <#"871328.files/image013.gif"> <#"871328.files/image014.gif"> <#"871328.files/image015.gif"> <http://www.rassyhaev.ru/wp-content/uploads/2011/05/lazarus.p>

Многооконный интерфейс среды Lazarus

Глава 2. Разработка приложения во Free Pascal

.1 Алгоритм игры «Быки и коровы»

В игровых программах описывается стратегия, приводящая к выигрышу игры. Для игры с двумя игроками возможны варианты: человек-машина, машина-машина. Это программа разгадывает секретный код. Другое название этой игры "Быки и коровы". Она является хорошим примером того, как без особых размышлений легко запрограммировать на Прологе.

Правила игры:

Игрок А выбирает секретный код, представляющий из себя последовательность из N различных десятичных цифр (обычно N устанавливается равным 4). Игрок В пытается угадать задуманный код и спрашивает игрока А о числе "быков" (число "быков" - количество совпадающих цифр в одинаковых позициях предполагаемого и задуманного кодов; число "коров" - количество совпадающих цифр, входящих в предполагаемый и задуманный код, но находящихся на разных позициях).

Код угадан если число быков равно N.

Алгоритм в общем описывается следующим образом:

Вводится некоторый порядок на множестве допустимых правилами предложений; выдвижение очередных предположений учитывает, накопленную к тому времени информмацию, и так до тех пор пока секретный код не будет раскрыт.

Рассмотренный алгоритм позволяет решить задачу - раскрыть код за 4-6 попыток ( как опытный игрок ).

Программа «Быки и Коровы»

mind (Code): -cleanup, guess (Code), check (Code), announce
guess(Code):-Code=[X1,X2,X3,X4],selects(Code,[1,2,3,4,5,6,7,8,9,0]).

/* Verify the proposed guess */(Guess):-not inconsistent(Guess),ask(Guess).(Guess):-query(OldGuess,Bulls,Cows), not bulls_and_cows_match(OldGuess,Guess,Bulls,Cows)._and_cows_match(OldGuess,Guess,Bulls,Cows):-_matches(OldGuess,Guess,N1),=:= N1,_members(OldGuess,Guess,N2),=:= N2 - Bulls._matches(X,Y,N):-size_of(A,same_place(A,X,Y),N)._members(X,Y,N):-size_of(A,(member(A,X),member(A,Y)),N)._place(X,[X|Xs],[X|Ys]).
same_place(A,[X|Xs],[Y|Ys]):-same_place(A,Xs,Ys).

/* Asking a guess */(Guess):-repeat,write_ln(['How many bulls and cows in ',Guess,'?']),((Bulls,Cows)),
sensible(Bulls,Cows), !,(query(Guess,Bulls,Cows)),=:=4.(Bulls,Cows):-integer(Bulls),integer(Cows),Bulls+Cows=4.

/* Bookkeeping */:- abolish(query,3).:-_of(X,query(X,A,B),N),_ln(['Found the answer after ',N,' queries'])._of(X,Goal,N) :-(X,Goal,Instances),length(Instances,N).([X|Xs],Ys) :-(X,Ys,Ys1),selects(Xs,Ys1).([],Ys).(X,[X|Xs],Xs).(X,[Y|Ys],[Y|Zs]) :-(X,Ys,Zs).(Xs,N) :- length(Xs,0,N).([X|Xs],Acc,N) :-is Acc + 1,(Xs,Acc1,N).([],N,N).

Спрашивающая процедура guess действует как генератор, использует процедуру selekt (Xs Ys) для недетерминированного выбора списка Хs из элементов списка Ys Согласно правилам игры, Хs ограничивается четырьмя различными десятичными цифрами, в то время как список Ys содержит 10 десятичных цифр. Процедура check (guess)

2.2 Разработка игрового приложения «Быки и коровы»

) Пользователь загадывает число из 4 цифр, каждая из которых от 1 до 6, причем все цифры различны. Разработать алгоритм, который угадывает число по следующим правилам: выводится число и пользователь сообщает, сколько в нем "быков" и "коров", т.е. сколько цифр стоят на своих местах и сколько цифр содержатся в обоих числах, но совпадают лишь по значению. Например, пусть загадано число 1264, спрошено 1256. В этом случае 2 быка (1,2) и одна корова (6)

б) Правила игры те же, но загадывается 6-значное число с цифрами от 1 до 9, причем среди цифр допускаются одинаковые.

Примечание : Спрошенное число должно удовлетворять правилам для загадываемого; компьютеру на ход дается 1 минута .

Итак, 1-ое что приходит в голову играть по следующему правилу: называть первое попавшееся число, которое может быть задуманно, т.е. при сопоставлении любого ранее спрошенного числа с новым должно получится такое-же количество 'быков' и 'коров'. Число будем представлять в виде массива цифр.}

MaxSgn = 6; {Максимальное значение в числе}= 4; {Количество цифр в числе}

type S = 1..MaxSgn;= array[1..Sgn] of S;cows(n1,n2:Numb):byte;

{Сравнивает два числа и возвращает результат

сравнения в виде <количество быков>*10+<количество коров>}

var i1,i2 : 1..Sgn;: byte;

begin

{Необходимо сравнивать все цифры первого

числа со всеми цифрами второго}

a:=0;i1:=1 to Sgn doi2:=1 to Sgn don1[i1]=n2[i2] theni1=i2 then a:=a+10 {Встретился 'Бык'}inc(a);:=a;

end;Step = Record {Информация об одном вопросе - ответе}: Numb; {Спрошенное число}: byte; {Ответ}

end;= array[1..32] of step;

{Информация о всех вопросах - ответах}Nstep : byte; {Номер текущего шага}

Info : Game;: Numb; i,j : integer; b : boolean;;i:=1 to Sgn do Curnumb[i]:=i;

Nstep:=0;true do

{Пока не будут перебраны все числа

или не найденно решение}

{Спросить текущее число}

for i:=1 to Sgn do write(Curnumb[i]);(' ? ');(Nstep);[Nstep].n:=Curnumb;(Info[Nstep].Answer);

{Пользователь должен ввести число, первая цифра

которого 'Быки', вторая - 'Коровы'}(Info[Nstep].Answer div 10+Info[Nstep].Answer mod 10)>Sgn thenwriteln('Плохая игра !'); exit; end;

{'Быков' и 'Коров' вместе не может быть больше, чем цифр}

if Info[Nstep].Answer=10*Sgn then exit;

{Далее идет генерация нового числа}:=Sgn;

{Увеличение числа на 1-цу}

while (i>=1) and (Curnumb[i]=MaxSgn) do[i]:=1;(i);

end;i<1 then{Все числа перебраны, а ответ не найден}('Вы неправильно отвечали !'); exit; end;

inc(Curnumb[i]);:=true;

{Проверка на встречающиеся одинаковые цифры}

for i:=1 to Sgn doj:=i+1 to Sgn do:=b and (Curnumb[i]<>Curnumb[j]);i:=1 to Nstepb:=b and (cows(Curnumb,Info[i].n)=Info[i].Answer);b;; {while}. {program}

Итак, наша программа работает следующим образом: мы путем последовательного увеличения на 1 генерируем все возможные 6-значные числа, отбираем среди них те, в которых все цифры различные, и, наконец, те из них, которые удовлетворяют хранящимся в массиве Info ответам, задается пользователю в качестве вопроса. Возникает ряд резонных вопросов: сколько всего интересующих нас 4-значных цифр и какая их часть не содержит повторений.

За сколько шагов может угадать ответ самый быстрый алгоритм и насколько хороша наша стратегия?

Давайте попытаемся ответить на них. Итак сколько всего чисел? Пусть k цифр и m позиций. В первой позиции может стоять любая

Из k цифр, что нам дает k вариантов. Во второй-также любая из k цифр, т.е. k2. И так далее m раз, т.е. всего km вариантов. Обобщим эту идею.

Определение: размещение с n повторением из k элементов по m называется m-элементный массив натуральных чисел, каждое из которых не превосходит k.

Утверждение: Число размещений с повторениями из k по m равно km. Доказательство проводим по индукции:

Базис индукции: При m=1 у нас ровно k вариантов.

Индуктивный переход: Пусть утверждение верно при m=n-1. Докажем, что оно верно при m=n. Зафиксируем число 1. Справа к этому числу припишем kn=1 размещений из k по n-1. Аналогично поступим с 1,2,3...k. Получим kn-1*k=kn вариантов.

Таким образом, число 4-значных чисел с цифрами от 1 до 6 равно 64=1296. Теперь посмотрим, сколько из них не содержит повторяющихся цифр.

Определения: размещением из k элементов по m называется m-элементный массив каждая компонента которого не превосходит k и среди них не встречаются одинаковые. Очевидно, что множество размещений не пусто лишь при m<=k.

Число размещений из k по m принято обозначать A.

Доказательство проводим по индукции:

Базис индукции: При m=1 у нас ровно k вариантов.

Индуктивный переход: Пусть утверждение верно при m=n-1. Выберем любое из k!/(k-n+1)! размещений из k по n-1. Чисел, которые в нем не участвуют-(k-n+1). Приписывая их поочередно справа к выбранному размещению мы получим (k-n+1) вариантов. Перебирая все размещения:

(k!/(k-n+1)!)*(k-n+1)=k!/(k-n)!

Таким образом,число 4-значных чисел с цифрами от 1 до 6 без повторений равно A46=6*5*4*3=360, т.е. в 3 раза меньше, чем число вариантов, которые мы перебирали. Итак мы нашли один способ для оптимизации нашей программы: генерировать не все числа, а лишь те, которые не содержат повторяющихся цифр. Возьмем это на заметку, а сейчас попробуем оценить максимальное число шагов, за которое отгадывает лучший игрок. Вариантов ответа у нас:

Пусть угадано 4 цифры. Среди них могут быть 2,1,0 "быков". Пусть угаданы 3 цифры. Среди них могут быть 3,2,1,0 "быков". И так далее: получаем 3+4+2+1=10 вариантов.

Таким образом за каждый вопрос количество допустимых чисел уменьшается, если мы рассматриваем худший случай, не более чем в 10 раз. Число шагов, за которое угадывает лучший игрок, не менее чем [log10 360]+1=3

Ну а теперь попытаемся повысить эффективность работы программы. Как уже было отмечено выше, нам достаточно перебрать не 1096 комбинаций, а всего лишь 360. Это не отразится на быстроте угадывания, т.е. числе шагов, так как не изменим стратегии "первый попавшийся из подходящих", но уменьшит время обдумывания хода.

Генерировать числа будем следующим образом: для начала выберем множество цифр, которое в него входит, ну а затем будем переставлять элементы этого множества между собой. Множество цифр удобно, для наших целей, представить в виде массива длины 4, элементы которого расположены в порядке возрастания. Будем генерировать эти массивы в лексикографическом порядке, т.е. сначала сравниваются первые цифры, если они равны - вторые, и так далее. То есть:

2        3        4

2        3        5

2        3        6

2        4        5

2        4        6

2        5        6

3        4        5

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

{n-число цифр}

{A-массив который содержит текущие комбинации}:integer;

{номер элемента ,который увеличивается в данный момент}

Var:integer;i:=1 to n do

a[i]:=i;{Начальное значение}:=n;{увеличивается крайняя правая цифра}p>=1 do

{Write(A)}-{Последовательность готова};

for i:=k downto p do[i]:=A[p]+i-p+1;a[k]=n then dec(p);

else p:=k;;

Для генерирования всевозможных перестановок множества служит следующая идея: Пусть у нас сформированы всевозможные перестановки длины N-1. Вставляя оставшийся элемент в каждую перестановку во все возможные позиции, мы получим все комбинации длины n. Например, число 1 в перестановку 2 3 можно вставить следующими 3-мя способами:

1          2         3

            1         3

            3         1

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

1          2         3

            1         3

            3         1

            2         1

            1         2

            3         2

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

Куда он сейчас движется - вправо или влево.

Знать номер возможного из n-i+1 мест в перестановке длины n-i, которое он сейчас занимает.

Мы приходим к следующему алгоритму:

{B - массив элементов перестановки}

{Direc - массив направлений, i-й элемент равен TRUE,

если тело i движется вправо}

{Posit - массив положения i-го элемента

в перестановке n-i элементов}

for i:=1 to n do[i]:=i;[i]:=1;[i]:=TRUE;

end;[n]:=0;

Давайте попытаемся привести этот алгоритм к нерекурсивной форме. Для i-го элемента нам необходимо знать:

Куда он сейчас движется-вправо или влево.

Номер возможного из n-i+1 мест в перестановке длине n-i, которое он сейчас занимает.

Мы проходим к следующему алгоритму:

{В-массив элементов перестановки}

{Direc-массив направлений. i-й элемент равен true,

если число i движений вправо}

{Posit- массив положения i-го элемента в перестановке

n-i элементов}i:=1 to n do[i]:=i;[i]:=1;[i]:=true;;[n]:=0;:=1;i<n do[i]:=not direct[i];[i]:=1;direct[i] then inc(x);(i);i<n thenpirof[i] then k:=c[i]+xk:=n-i+1-c[i]+x;[k]<->b[k+1];(posit[i])

end;

И, наконец, новый вариант программы игры

Const MaxSgn=6;=4;s=1..MaxSgn; {цифра}=array[1..Sgn] of s;cows(n1,n2:Numb):byte;

{Сравнивает два числа и возвращает результат сравнения

в виде <количество быков>*10+<количество коров>}

var i1,i2 : 1..Sgn;: byte;

begin

{Необходимо сравнивать все цифры первого числа

со всеми цифрами второго}:=0;

for i1:=1 to Sgn doi2:=1 to Sgn don1[i1]=n2[i2] theni1=i2 then a:=a+10 {Встретился 'Бык'}inc(a);:=a;

end;Step = Record {Информация об одном вопросе - ответе}: Numb; {Спрошенное число}: byte; {Ответ}

end;= array[1..32] of step;

{Информация о всех вопросах - ответах}

var NStep:byte;:game;

{процедура проверяет, удовлетворяет ли входное число

ранним ответам, и, если да, то задает его в качестве вопроса.

В случае, если число угадано, заканчивает игру}

Var i:byte;i:=1 to nstep docows(n,info[i].n)<>info[i].answer then Exit;(Nstep);[nstep].n:=n;i:=1 to sgn do write(n[i]);(' ? ');(info[nstep].answer);info[nstep].answer=sgn*10 then;

{игра окончена}; {test number}

Var tset{текущее n-элементное подмножество}

,tn:number;,j,k,l:byte;:array[1..sgn] of boolean; posin:array[1..sgn] of byte;

{инициализация}:=0;i:=1 to sgn do tset[i]:=i; i:=sgn;i>=1 do:=tset;j:=1 to sgn do begin[i]:=1;[i]:=true;;[sgn]:=0;:=1;(tn);j<sgn do:=1;:=0;posit[j]=sgn-j+1 do[j]:=1;[j]:=not direct[j];direct[j] then inc(x);(j);;j<sgn thendirect[j] then l:=posit[j]+n;l:=sgn-j+1+posit[j]+k;[posit[j];;;

writeln('Плохая игра');end.

Заключение

Pascal - свободная реализация языка Паскаль, совместимая
с Borland Pascal и Object Pascal - Delphi, но при этом обладающая
и некоторыми дополнительными возможностями. Свободный компилятор Free Pascal - кросплатформенный продукт, реализованный, в частности, для операционных систем Linux и Windows.

Целью создания программы «Быки и коровы» является демонстрация умений и навыков, полученных в результате научно-исследовательской работы, заключающейся в изучении теории программирования и технологии разработки программных приложений, а также применении современных информационных технологий <http://pandia.ru/text/category/informatcionnie_tehnologii/> для решения практических задач обработки данных и математического моделирования.

Список использованных источников

1. Алексеев Е.Р., Чеснокова О.В., Кучер Т.В. Самоучитель по программированию на Free Pascal и Lazarus. - Донецк.: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2012. - 503

. Алексеев Е. Р., ЧесноковаО.В., КучерТ.В. Free Pascal и Lazarus: Учебник по программированию М.: ALT Linux ; Издательский дом ДМК-пресс, 2010. 440 с.

. Мансуров К.Т Основы программирования в среде Lazarus, 2010,773 с.

. Павлова Т.Ю. Структурное программирование в ИСР Free Pascal - Кемерово: 2010. -91с.

. Попов Е.А. Экспресс курс программирования в Lazarus ,2015

. Рудаков П.И., Федотов М.А. Основы языка Паскаль.-М:Радио и связь, 2000.

. Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль (версия 5.5).-М:МАИ, 1992.

. Турбо Паскаль 7.0. К:Торг.-изд.бюро BNV, 1996.

. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования: Учебное пособие. -М:Нолидж, 1997.

. А.П. Полищук, С.А. Семериков. Программирование в X Window средствами Free Pascal. -С.Пб:БХВ-Петербург, 2003.

. И.Л.Шихалев. Основы программирования для Win32 на Free Pascal. -М:Бином, 2005.