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