Міністерство освіти і науки Російської Федерації
Агентство з освіти
Тихоокеанський Державний Економічний Університет
Економічний інститут
Курсова робота
На тему: «Обчислення" Риби "»
Владивосток 2009
Зміст
Введення
Постановка завдання. Неформальне опис
Формальна постановка задачі
Перевірка умови
Методи вирішення задачі. Опис методу
Алгоритм
Текст програми
Керівництво користувача. Вікно програми
Опис інтерфейсу
Висновок
Список літератури
Введення
Для написання курсової мною була обрана саме ця тема - «Обчислення" Риби "». І обрана не випадково, так як розробка варіантів перебору, безлічі можливостей вирішення мене приваблюють найбільше. У процесі виконання завдання я зіткнувся з багатьма труднощами, які пов'язані з тим, що завдання можна вирішити великою кількістю способів і «подспособов». І багато з них виявилися тупиковими, у зв'язку з чим, багато функцій переписувалися заново кілька разів.
Отже, мною було розроблено кілька варіантів рішення, один з яких я вважав найбільш вдалим. Про нього мова нижче.
Постановка завдання. Неформальне опис
Завдання поставлено таким чином: «Задано правильна послідовність кісток доміно. Підрахувати кількість різних правильних її продовжень, які є "Рибами" ».
З власного досвіду я можу стверджувати, що після першого прочитання завдання сприймається не дуже добре, важко уявити в голові вірне рішення. Для найкращого розуміння нижче наведена ілюстрація до задачі (рис. 1).
Рис. 1
На рис. 1 наведено приклад вірного рішення задачі: з 27 кісток отримана 'Риба'.
Формальна постановка задачі
Є 28 кісток доміно, кожна прономерована з лівого і правого боку.
Вони по черзі ставляться одна за одною відповідно до номерів зазначеними на сторонах. У разі якщо до вже використаним кістках не можна нічого додати то це називається «Риба».
Простіше за все створити об'єкт який буде відповідати необхідний вимогам: буде зберігати інформацію про номери кістки і матиме властивості за яким можна перевірити чи використовується дана кісточка. Нам знадобиться масив таких об'єктів. Отже, маємо масив array (1 .. 2 8).
Перевірка умови
Безпосередньо головне завдання полягає в тому, щоб згенерувати послідовність яка б відповідала необхідній умові:
Послідовність має генеруватися випадково.
Кісточки повинні бути відображені послідовно.
Розглянемо кожен пункт окремо.
Що стосується 1 пункту, то нам доведеться спочатку згенерувати можливі варіанти кісточок і вибрати з них випадкову послідовність і повторити все спочатку. Таким чином ми отримаємо випадкову послідовність.
Номер на правій стороні кістки, має відповідати номеру на лівій стороні наступної кістки.
Методи вирішення задачі. Опис методу
Завдання вирішується методом рішення з поверненням.
Метод полягає в повному переборі всіх можливих варіантів послідовностей кісточок, яку ми генеруємо випадково.
Алгоритм
Створити масив доміношек.
Створити масив об'єктів Т Image.
Створити масив для відповідних кісток.
Внести до масив відповідних кісток можливі варіанти.
Вибрати випадково один з варіантів.
Очистити масив відповідних кісток.
Створити масив використаних кісток.
Відображаємо отриману послідовність.
Відображаємо невикористані кістки.
Текст програми
У даній главі будуть наведені найбільш значущі функції, основні класи програми, їх методи і властивості.
Клас 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.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с.