Министерствообразования и науки Российской Федерации
Агентство пообразованию
ТихоокеанскийГосударственный Экономический Университет
Экономическийинститут
Курсоваяработа
На тему: «Вычисление“Рыбы”»
Владивосток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;
Процедура DrawIMGH, рисующая результатывычисления на форме.
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+'\IMG\Horizontal\'+
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.SideBnext.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с.