Министерство образования и науки Российской Федерации
Агентство по образованию
Тихоокеанский Государственный ЭкономическийУниверситет
Экономический институт
Курсовая работа
На тему: «Вычисление “Рыбы”»
Владивосток 2009
Оглавление
Введение
Постановка задачи. Неформальное описание
Формальная постановка задачи
Проверка условия
Методы решения задачи. Описание метода
Алгоритм
Текст программы
Руководство пользователя. Окно программы
Описание интерфейса
Заключение
Список литературы
Введение
Для написания курсовой мной была выбрана именно эта тема – «Вычисление “Рыбы”». И выбрана неслучайно, так как разработка вариантов перебора, множества возможностей решения меня привлекают больше всего. В процессе решения задачи я столкнулся с рядом сложностей, которые связаны с тем, что задачу можно решить большим количеством способов и «подспособов». И многие из них оказались тупиковыми, в связи с чем, многие функции переписывались заново несколько раз.
Итак, мною было разработано несколько вариантов решения, один из которых я счел наиболее удачным. О нем речь ниже.
Постановка задачи. Неформальное описание
Задача поставлена следующим образом: «Задана правильная последовательность костей домино. Подсчитать количество различных правильных ее продолжений, которые являются “Рыбами”».
По своему опыту я могу утверждать, что после первого прочтения задача воспринимается не очень хорошо, трудно представить в голове верное решение. Для наилучшего понимания ниже приведена иллюстрация к задаче (рис. 1).
Рис. 1
На рис. 1 приведен пример верного решения задачи:из 27 костей получена ‘Рыба’.
Формальная постановка задачи
Есть 28 костей домино, каждая прономерована с левой и правой стороны.
Они поочередно ставятся одна за другой в соответствии с номерами указанными на сторонах. В случае если к уже использованным костям нельзя ничего добавить то это называется «Рыба».
Проще всего создать объект который будет отвечать необходим требованиям: будет хранить информацию о номерах кости и будет иметь свойства по которому можно проверить используется ли данная костяшка. Нам понадобится массив таких объектов. Итак, имеем массив array(1..28).
Проверка условия
Непосредственно главное задача состоит в том, чтобы сгенерировать последовательность которая бы отвечала необходимому условию:
1. Последовательность должна генерироваться случайно.
2. Костяшки должны быть отображены последовательно.
Рассмотрим каждый пункт в отдельности.
1) Что касается 1 пункта, то нам придется сначала сгенерировать возможные варианты костяшек и выбрать из них случайную последовательность и повторить все сначала. Таким образом мы получим случайную последовательность.
2) Номер на правой стороне кости, должен соответствовать номеру на левой стороне следующей кости.
Методы решения задачи. Описание метода
Задача решается методом решения с возвращением.
Метод заключается в полном переборе всех возможных вариантов последовательностей костяшек, которую мы генерируем случайно.
Алгоритм
1. Создать массив доминошек.
2. Создать массив объектов ТImage.
3. Создать массив для подходящих костей.
4. Внести в массив подходящих костей возможные варианты.
5. Выбрать случайно один из вариантов.
6. Очистить массив подходящих костей.
7. Создать массив использованных костей.
8. Отображаем полученную последовательность.
9. Отображаем неиспользованные кости.
Текст программы
В данной главе будут приведены самые значимые функции, основные классы программы, их методы и свойства.
КлассTDomino
.
TDomino = object
SideA,SideB:byte;
State:boolean;
end;
Класс TImage.
TImg = class (TImage)
private
State : boolean;
end;
А также класс формы, обрабатывающий интерфейс программы.
TForm1 = class(TForm)
Button1: TButton;
Button2: TButton;
Label2: TLabel;
DirectoryListBox1: TDirectoryListBox;
Label3: TLabel;
Image1: TImage;
Label1: TLabel;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure FormResize(Sender: TObject);
private
{ Private declarations }
public
Path : string;
end;
Проце
, рисующая результаты вычисления на форме.
Procedure DrawIMGH();
var
i,a,b,j:byte;
begin
j:=1;
for I := 1 to 28 do
if sp1[i].State=true then
begin
a:=sp1[i].SideA;
b:=Sp1[i].SideB;
Img[j].Left:=left+2+img[i].Width;
left:=img[j].Left;
If (left>form1.Width) or (left+img[i].Width>form1.Width-8) then
begin
form1.Width:=form1.Width+3;
left:=0;
Img[j].Left:=left;
top:=top+img[j].Height+5;
end;
img[j].Top:=top; img[j].Picture.LoadFromFile(Form1.Path+'IMGHorizontal'+
inttostr(A)+inttostr(B)+'.bmp');
img[j].State:=true;
inc(j);
end;
end;
Процедура Tform1.Button1Click
запускает обработку .
procedure TForm1.Button1Click(Sender: TObject);
var
i,j,count:byte;
begin
count:=0;
Label1.Caption:='00';
for i:=1 to 28 do
Img[i].Destroy;
for i:=1 to 28 do
Img2[i].Destroy;
CreateImgMass;
init;
curent.SideA:=0;
Curent.SideB:=0;
Curent.State:=true;
GetVariants;
For I:=1 to 28 do
If domino[i].State=false then
inc(count);
Label2.Caption:=inttostr(count);
end;
В процедуру GetVariants
мы поместили алгоритм, обрабатывающий все процессы. Это самая большая процедура.
Procedure GetVariants();
Var
i,id,count:byte;
st:boolean;
begin
count:=1;
repeat
st:=false;
if Getnext(curent)=true then
begin
st:=true;
id:=rand(r);
next:=sp2[id];
//****************
for I := 2 to 28 do
if (domino[i].SideA=next.SideA)and(domino[i].SideB=next.SideB) then
domino[i].State:=true;
//******************
prev:=curent;
if prev.SideB<>next.SideA then
if prev.SideB=next.SideB then
begin
next.SideB:=next.SideA;
next.SideA:=prev.SideB;
end;
curent:=next;
sp1[count]:=next;
inc(count);
Form1.Label1.caption:=Form1.Label1.Caption+'->';
Form1.Label1.caption:=Form1.Label1.Caption+inttostr(curent.SideA)+inttostr(curent.SideB);
end;
until (st=false);
end;
И, наконец, функция GetNext
(
cur
:
TDomino
):
boolean
, ищущая подходящие свободные костяшки.
Function GetNext(cur:TDomino):boolean;
Var
i ,j: byte;
begin
r:=0;
j:=1;
result:=false;
For I:=2 to 28 do
If Domino[i].State = false then
if (cur.SideB = Domino[i].SideB)
or (cur.SideB = Domino[i].SideA) then
begin
sp2[j]:=domino[i];
sp2[j].State:=true;
result:=true;
inc(r);
inc(j);
end;
end;
Руководство пользователя. Окно программы
Несмотря на то, что разработка программы – очень сложный и трудоемкий процесс, пользоваться ей очень просто. После запуска программы, мы видим это окно:
В нижней части формы мы видим пустое пространство и костяшку 0:0. Пустое пространство предназначено для построения одного из полученных вариантов “Рыбы”.
Сверху присутствует значение костей, которые не входят в полученную последовательность. А так же пространство, для их отображения.
Описание интерфейса
Программа предлагает случайно вычислить одну из последовательностей “Рыбы”
Кнопка «Расчитать» запускает процесс, который вычисляет “Рыбу” и выводит ее на экране в последовательность чисел.
Кнопка «Отобразить» графически показывает полученную последовательность, а так же не использованные домино, и через некоторое время (генерация занимает от 1-й до 4-х секунд) мы видим результат работы.
Кнопка «Выход» завершает программу.
Заключение
Разработав эту программу, я еще глубже изучил среду разработки Delphi 7, познакомился с особенностями создания интерфейсов для рабочей программы. Элементы управления должны быть разработаны таким образом, чтобы не мешать использованию программы, чтобы у человека не возникало вопросов, связанных с тем, что делать и как. Всё это было множество раз учтено, поэтому в итоге мы получили работающее приложение.
Список литературы
1.Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. – Владивосток: Изд-во ДВГТ, 2000. – 288с.
2.Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб. пособие. Владивосток: Изд-во ТГЭУ, 2006. – 92с.