Реферат
Курсова робота, 28 с., 2 мал., три джерела.
Розв’язок задачі про призначення мінімального вибору.
У роботі описані процес і результати розробки програмного засобу. В процесі розробки програмного засобу отримана цілком працездатна програма.
Робота програмного засобу можлива в операційній системі MS DOS на IBMPC-сумісних комп’ютерах.
Програмний засіб повинен визначати оптимальний варіант об’єднання ЕОМ в мережі, щоб час розв’язку був мінімальним.
Зміст
Вступ
Аналіз задачі, що вирішується
Вхідні дані
Вихідні дані
Вибір мови програмування
Опис роботи програми
Опис творчого процесу рішення задачі
Опис процедур
Лістинг програми
Керівництво користувача
Технічні вимоги до використання
Висновок
Довідкова література
Вступ
Розвиток і широке поширення засобів обчислювальної техніки в останні десятиліття послужило поштовхом до розробки програмного забезпечення різного рівня складності та різного за призначенням.
Для придбання вмінь та навичок розробки програмного забезпечення в процесі навчання вивчається предмет “Алгоритмічні мови та програмування”. Курсова робота є підсумком отриманих знань під час навчання.
Курсова робота “Розв’язок задачі про призначення” розроблена на алгоритмічній мові програмування Turbo Pascal з використанням графічного інтерфейсу та методів математичної обробки інформації.
Програма використовується для знайдення оптимального розподілу задачі по мережі, таким чином, щоб час розв’язку був мінімальним.
Отже, тема курсової роботи “Розв’язок задачі про призначення” носить практичний характер і є досить актуальною.
Аналіз задачі, що вирішується
Розробка розв’язку задачі про призначення мінімального вибіру.
Потрібно, щоб програма призначила кандидатів таким чином, щоб сумарна збитковість була мінімальною.
Одержуючи від користувача певну дію, програма повинна зчитати дані з файлу або вони повинні бути введені користувачем. Після введення користувач повинен вибрати: записувати результат у файл чи виводити його на екран.
Для рішення цієї задачі був обраний угорський метод та мова програмування Pascal.
Вхідні дані
Вхідними даними для даного програмного засобу є матриця вагів, яка зчитується з файлу, або кожен елемент якої вводиться власноруч.
Вихідні дані
Програма обчислює розподіл задач в мережі об’єднання між машинами ЕОМ, а також рахує і виводить на екран оптимальний варіант.
Вибір мови програмування
В даний час ми є свідками бурхливого розвитку обчислювальної техніки і її упровадження в багатьох сферах людської діяльності. Особливо чітко ці тенденції виявляються, коли мова заходить про персональний ЕОМ.
Інтерес до персональних комп'ютерів постійно росте, а коло їх користувачів безупинно розширюється. У число користувачів ПЕОМ втягують як новачки в комп'ютерній справі, так і фахівці з інших класів ЕОМ.
Хоча на ПЕОМ можуть використовуватись багато різних мов програмування (Бейсік, Паскаль, C++, Асемблер), використання мови програмування Турбо Паскаль найбільш еффективне.
Мова Бейсік входить до складу програмного забезпечення майже усіх ПЕОМ, що випускаються в дійсний час. Розроблювачі ПЕОМ, як правило, включають у реалізовану версію мови засоби, що дозволяють використовувати всі можливості, надані апаратурою конкретної ПЕОМ. Завдяки цьому для користувача, який не є професійним програмістом (а таких користувачів ПЕОМ більшість), Бейсік виконує роль базової мови, подібно мові Асемблер для професійного програміста.
Мова C++ - універсальна мова загального призначення, область додатків якої - програмування систем у самому широкому змісті. Крім цього С++ успішно використовується як у багатьох додатках, так і в могутніх операційних системах. Реалізація C++ здійснена для машин у діапазоні від найпростіших персональних комп'ютерів до самих могутніх суперкомп'ютерів і для всіх операційних систем.
Мова Асемблер - мова, найбільш близька до машинної. Вона дозволяє програмісту найближче познайомитися з машиною (на відміну від мов програмування високого рівня), і тому вивчення Асемблера означає також вивчення самого мікропроцесора 8086. Як правило програма, написана на Асемблері, виконується набагато швидше програми, написаної на будь-якій іншій мові. Звичайно програми на Асемблері виконуються в 2-3 рази швидше, ніж еквівалентні програми С++ чи Паскаля, і в 15 і більше разів швидше, ніж програми, покроково інтерпритуємі Бейсіком. Асемблерні програми також значно менші за розміром.
Програми на Асемблері відкривають програмісту повний доступ до можливостей комп'ютера.
Мова Турбо Паскаль - це одна з найпоширеніших мов програмування. Вона розроблена фірмою "Борланд" як діалект стандартної мови Паскаль, але завдяки своїй популярності сама стала стандартом мови програмування.
Найважливішими перевагами мови Турбо Паскаль є невеликий розмір компілятора, висока ступінь відповідності стандартному Паскалю, дуже швидка компіляція програм, об'єднання компілятора з інтерактивним екранним редактором, попередження про помилки на рівні вихідної програми, велика бібліотека підпрограм і корисні розширення, що спрощують системне програмування.
Але найголовнішим є те, що мова Турбо Паскаль підходить для навчання починаючих програмістів гарному стилю програмування.
Опис роботи програми
Програма розроблена у середовищі програмування Турбо Паскаль. Вона призначена для свого використання операційною системою MS DOS. До неї підключені стандартні бібліотеки Турбо Паскаля: crt, graph та dos.
На початку роботи програми на екрані з’являється головне меню, яке містить кнопки “Данные”, “Результат” и “?”. При натисненні кнопки “Данные” на екрані з’являються підпункти “Из файла”, “Вручную” та “Выход”. Користувач обирає метод введення матриці вагів – зчитування її з файлу Input.txt чи введення власноруч. Користувач виходить з програми, вибравши підпункт “Выход”. “Результат” складається з підпунктів “На экран” та “В файл”. Обравши один з цих підпунктів, користувач автоматично обирає, як саме виводити результати – на екран чи записавши їх у файл Output.txt відповідно. Пункт меню “?” містить лише підпункт “Справка”, який містить довідку про програму та її автора.
Опис творчого процесу рішення задачі
Користувач може керувати програмою за допомогою меню. Структурна схема меню представлена на мал.1.
Мал.1.
Алгоритм роботи програми приведений на мал.2.
Мал.2.
Опис процедур
procedure Init
Ініціалізація кнопки меню.
Вхідін дані - координати кнопки.
procedure Show
Виведення на екран кнопки меню.
Вхідні дані - колір.
procedure ChoiceMein
Вибір в головному меню.
Вхідні дані - номер виділеної кнопки.
procedure Mein
Виведення на екран головного меню.
procedure ShowAll
Виведення підменю.
Вхідні дані - номер підменю.
procedure ChoiceM
Вибір у підменю.
procedure PHelp
Виведення допомоги.
procedure MsgError
Виведення повідомлення про помилку.
Вхідні дані - рядок повідомлення.
procedure InitMatrix
Ініціалізація масиву з координатами кнопок.
Вхідні дані - потрібний пункт меню.
procedure ChoiceResult
Перевірка натиснутої кнопки меню і виконання відповідної дії.
Вхідні дані - номер кнопки меню.
Лістинг програми:
Program Lenna;{iм"я програми}
Uses crt, dos, graph ;{пiдключаємо модулi}
Const MaxMenuItems = 10;{максимальна кiлькiсть пунктiв меню}
GM = MAXINT;{"нескiнченно велике число"}
MAXN = 10;{максимальна кiлькiсть комп"ютерiв у мережi}
Const Huge = MaxInt;{те саме що i ГМ}
Type MyArray = Array[1..MaxN, 1..MaxN] of Real; {тип масиву для розрахункiв}
MySimpleArray = Array[1..MaxN] of Real; {тип масиву для розрахункiв}
Type ProcedureType = Procedure;{процедурний тип}
Type ProcedurePointer = ^ProcedureType; {покажчик на процедурний тип (для меню) }
Type TMenuItem = Record{тип пункту меню}
Caption : String;{текст пункту (назва) }
Action : ProcedurePointer; {покажчик на процедуру}
Selected: Boolean;{пункт видiленоi}
end;
{загальний опис структури меню та короткий довiдник}
Type TMenu = Object {об"єкт меню}
Items: Array [ 1..MaxMenuItems ] of TMenuItem;{пукти}
ItemsCount: Integer;{кiлькiсть пунктiв}
Active: Boolean;{меню активнеi взагалi це поле не вик.}
Procedure AddItem(Caption: String; Action: ProcedurePointer); {метод. додати пукт до меню}
Procedure ExecuteAction;{виконати дiю: передати керування процедурi на яку вказує покажчик видiленого пункту}
Function getMaximalWidth: Integer; {знайти найширший пункт}
Procedure Print;{вивести меню на екран}
procedure Activate;{передати керування у меню}
end;
var Num: Integer;
Input: MyArray;
i, j: integer;
OriginalMode : Word; {для перемикання текстових режимiв}
ScreenWidth : Integer;{ширина екрану}
ScreenHeight : Integer;{висота екрану}
CharBuffer : Char;{непотрiбно :)}
Menu: TMenu;{об"єкт меню}
{процедура створення текстового вiкна з параметрами кольору фону та тексту}
Procedure CreateTextWindow( X, Y, Width, Height: Integer;
BackgroundColor, ForegroundColor: Integer);
begin
If (X + Width) > ScreenWidth then Width := ScreenWidth - X;
If (Y + Height) > ScreenHeight then Height := ScreenHeight - Y;
Window(X, Y, Width, Height);
TextBackground(BackgroundColor);
TextColor(ForegroundColor);
ClrScr;
end;
{активацiя меню}
Procedure TMenu.Activate;
var CommandKey: Char;
I: Integer;
begin
{виводимо меню}
Print;
{читаємо команди}
Repeat
CommandKey := ReadKey;
{Enter -- виконати}
Case Ord(CommandKey) Of
13: ExecuteAction;
{вибрати наступний униз}
75: Begin
For i := 1 to ItemsCount do
If items[i].selected then break;
Items[I].Selected := False;
If i = 1 then I := ItemsCount Else
I:=I-1;
Items[I].Selected := True;
End;
{вибрати наступний угору}
77: Begin
For I:=1 to ItemsCount do
If Items[i].selected then break;
Items[i].Selected := False;
If I = Itemscount then I:=1 else I:=I+1;
Items[I].Selected := True;
end;
end;
{надрукувати меню на екран}
Print;
{якщо Еск -- вийти}
Until Ord(CommandKey) = 27;
end;
{вивiд меню на екран}
Procedure TMenu.Print;
var i:integer;
width: integer;
Position: Integer;
TempText: String;
begin
{тiльки якщо пункти є}
If ItemsCount > 0 then
Begin
Width:=getMaxim
{ робимо заголовок}
TempText:='ЗАДАЧА О НАЗНАЧЕНИЯХ';
CreateTextWindow(1, 1, 80, 4, LightGray, Black);
GotoXY(ScreenWidth div 2 - Length(TempText) div 2, 2);
Write(TempText);
{робимо меню i друкуємо його}
CreateTextWindow(1, 4, 80, 6,green, White);
For I:=1 to ItemsCount do
begin
GotoXY( Width * I - Width div 2 - Length(Items[i].Caption) div 2, 2);
If Items[I].Selected then TextColor(Yellow) Else TextColor(White);
Write(Items[I].Caption);
end;
End;
end;
{знайти найширший пункт}
Function TMenu.getMaximalWidth: Integer;
var max: integer;
i: integer;
begin
if ItemsCount > 0 then
begin
max := Length(Items[1].Caption);
For I:=1 to ItemsCount do
begin
If Length(Items[i].Caption) > max then
Max := Length(Items[i].Caption);
end;
end;
getMaximalWidth := max;
end;
{виконати дiю}
Procedure TMenu.ExecuteAction;
Var N: Integer;
Begin
if ItemsCount > 0 then
begin
For N:=1 to ItemsCount do
begin
If Items[N].Selected Then ProcedureType(Items[N].Action);
end;
end;
End;
{додати пункт до меню}
Procedure TMenu.AddItem(Caption: String; Action: ProcedurePointer);
begin
If ItemsCount < MaxMenuItems then
begin
ItemsCount := ItemsCount + 1;
Items[ItemsCount].Caption := Caption;
If ItemsCount = 1 Then
Items[ItemsCount].Selected := True
Else Items[ItemsCount].Selected := False;
Items[ItemsCount].Action := Action;
end;
end;
{встановити потрiбний текстовий режим та знайти ширину i висоту екрану}
Procedure ScreenInitialization;
Begin
CheckBreak := False;
OriginalMode := LastMode;
TextMode( Lo(LastMode) + Font8x8);
ScreenWidth := Lo(WindMax) + 1;
ScreenHeight := Hi(WindMax) + 1;
TextBackground(Black);
TextColor(White);
End;
{процедура виходу}
Procedure ExitProc;
begin
Halt;
end;
{вивiд допомоги}
Procedure PrintHelp;
var s: file of char;
buffer:char;
begin
CreateTextWindow(1, 7, ScreenWidth, ScreenHeight, Black, White);
assign(s, 'help.txt');
reset(s);
while not eof(s) do
begin
read(s, buffer);
write(buffer);
end;
end;
{запит з клавiатури значення (1)}
Function InputValue(Comment: String): Integer;
Var Temp: Integer;
Len: Integer;
I, J: Integer;
begin
Len:= Length(comment);
J := 1;
While J <> 0 do
begin
CreateTextWindow( ScreenWidth div 2 - Len div 2 - 2,
ScreenHeight div 2 - 6 div 2,
ScreenWidth div 2 + Len div 2+ 2,
ScreenHeight div 2 + 6 div 2,
Blue, White);
TextColor(Yellow);
GotoXY( 3, 3); Write(Comment);
TextColor(White);
Window( ScreenWidth div 2 - Len div 2,
ScreenHeight div 2 + 2 div 2,
ScreenWidth div 2 + Len div 2,
ScreenHeight div 2 + 4 div 2);
TextColor(White);
{$I-}
Readln(Temp);
{$I+}
If IOResult <> 0 then J:=1 Else J:=0;
end;
CreateTextWindow(1, 7, ScreenWidth, ScreenHeight, Black, White);
InputValue := Temp;
end;
Procedure ASSIGMENTPROBLEM(N: Integer; C: MyArray);
var I, J0,m,m0,h2, I0,j1,last,up,low, J, k, cnt, s, ss: Integer;
V, u, d: MySimpleArray;
VJ, v0,h, dj, min,z : Real;
x,y, Col, free, lab: array[1..MaxN] of Integer;
label 41, 50, 43, 60, 55, 70, 80, 999;
begin
For I:=1 to N do
X[i] := 0;
For J0:=1 to N do
begin
J:=N - J0 + 1;
VJ := C[j,1];
I0 := 1;
For I:= 2 To N do
If C[i,j] < vj Then begin vj := C[i,j]; I0 := i; end;
V[j] := vj;
Col[j] := j;
If X[i0] = 0 then begin x[i0]:=j; y[j]:=i0; end
else begin x[i0] := -1 * ABS( X[i0] ); y[j]:=0; end;
end;
m:=0;
For I:=1 to N do
begin
If x[i] = 0 then
begin
m:=m+1;
free[m]:=i;
break;
end; {if}
If x[i] < 0 then
x[i]:=-1*x[i]
else
begin
j1:=x[i]; min:=Huge;
For J:=1 to N do
begin
If j = j1 then break;
If c[j,i] - v[j] < min then Min := c[j,i] - v[j];
end; {for}
v[j1] := v[j1] - min;
end;{else}
end;
Cnt:=0;
If m = 0 then goto 999;
41:
m0:=m; k:=1; m:=0;
50:
i:=free[k]; k:=k+1;
v0 := c[1, i] - v[1];
j0:=1; vj:=Huge;
For j:=2 to N do
begin
h:=c[j,i] - v[j];
If H < vj then
begin
if H >= v0 then
begin vj := h; j1 := j; end
else begin vj:=v0; v0 := h; j1:=j0; j0:=j; end;
end;
end;
i0:=y[j0];
if v0 < vj then
v[j0] := v[j0] - vj + v0
else
begin
if i0 = 0 then goto 43;
j0:=j1; i0 := y[j1];
end;
if i0 = 0 then goto 43;
if v0 < vj then
begin
k := k - 1;
free[k]:=i0;
end else
begin
m:=m+1;
free[m]:=i0;
end;
43:
x[i] := j0;
y[j0] := i;
if k <= m0 then goto 50;
cnt := cnt + 1;
if (m > 0) AND (cnt < 2) then Goto 41;
m0 := m;
For M:=1 to M0 do
begin
i0:=free[m];
For J:=1 to N do
begin
d[j]:=c[j,i0] - v[j];
lab[j]:=i0;
end;
up:=1;
low := 1;
60:
last:=low - 1;
min := d[col[up]];
up := up+1;
for k:=up to n do
begin
j := col[k];
dj := d[j];
if dj <=min then
begin
if dj < min then begin min:=dj; up:=low; end;
col[k]:=col[k];
col[up] := j;
up := up+1;
end;
end;
for h2:=low to up - 1 do
begin
j:=col[h2];
if y[j] = 0 then Goto 70;
end;
55:
j0:=col[low];
low:=low+1;
i:=y[j0];
h:=c[j0, i] - v[j0] - min;
for k:=up to n do
begin
j:=col[k];
vj:=c[j,i] - v[j] - h;
if vj < d[j] then
begin
d[j] := vj;
lab[j]:=i;
if vj = min then
begin
if y[j] = 0 then Goto 70;
col[k]:=col[up];
col[up]:=j;
up:=up+1;
end;
end;
end;
if low = up then goto 60;
goto 55;
70:
for k:=1 to last do
begin
j0 := col[k];
v[j0] := v[j0] + d[j0] - min;
end;
80:
i:=lab[j];
y[j]:=i;
k:=j;
j:=x[i];
x[i]:=k;
if i0 <> i then Goto 80;
end;
999:
z := 0;
For I:=1 to N do
begin
u[i]:=c[x[i],i] - v[x[i]];
z:=z+c[x[i],i];
end;
Writeln;
TextColor(LightBlue);
For I:=1 to N do begin
Writeln(' ДЛя комп"ютера ', I, ' задача ', y[i], ' найкраще пiдiйде.');
end;
end;
procedure PROG;
var i, j: integer;
si, sj: string;
begin
Num:=InputValue('Введiть кiлькiсть комп"ютерiв:');
For I:=1 to Num do
For J:=1 to Num do
begin
str(i, si);
str(j, sj);
Input[I,J]:=InputValue('Коефiцiєнт ' + si + '-ї задачi на комп"ютерi ' + sj);
end;
ASSIGMENTPROBLEM(num, input);
end;
procedure priklad;
var
FC: File of Char;
I, J: Integer;
BUFFER: Char;
begin
CreateTextWindow(1, 7, ScreenWidth, ScreenHeight, Black, White);
Assign(FC, 'EXAMPLET.TXT');
Reset(FC);
While not EOF(FC) do
begin
Read(FC, BUFFER);
Write(Buffer);
end;
close(FC);
Num:=5;
Input[1,1]:=9; Input[2,1]:=20; Input[3,1]:=60; Input[4,1]:=15; Input[5,1]:=21;
Input[1,2]:=38; Input[2,2]:=71; Input[3,2]:=69; Input[4,2]:=49; Input[5,2]:=60;
Input[1,3]:=28; Input[2,3]:=13; Input[3,3]:=80; Input[4,3]:=28; Input[5,3]:=34;
Input[1,4]:=58; Input[2,4]:=34; Input[3,4]:=13; Input[4,4]:=37; Input[5,4]:=25;
Input[1,5]:=30; Input[5,5]:=3; Input[2,5]:=53; Input[3,5]:=20; Input[4,5]:=21;
ASSIGMENTPROBLEM(num, input);
end;
begin
{встановлюємо екран}
ScreenInitialization;
{додаємо до меню пунктики}
With Menu do
begin
AddItem('Prog', @PROG);
AddItem('Справка', @printHelp);
AddItem('Пример', @priklad);
AddItem('Выход', @exitProc);
Activate;
end;
end.
Керівництво користувача
Дана програма призначена для використання в операційній системі MS DOS.
Для запуску програми потрібно запустити файл Lena.exe. Після запуску програми на екрані з’являється меню, яке містить три пункти – “Данные”, “Результат” та “?”. Пункт меню “Данные” складається з підпунктів “Из файла”, “Вручную”, “Выход”. Вибравши “Из файла”, ви вводите матрицю вагів, збережену в якомусь файлі. Вибравши “Выход”, програма закривається. “Результат” має підпункти “На экран” і “В файл”. Вибравши один з цих підпунктів, ви або виводите результат на екран, або відповідно зберігаєте його у файл. Пункт меню “?” має підпункт “Справка”.
Технічні вимоги до використання
Для запуску даної програми необхідна наявність персонального комп’ютера IBM PC.
Мінімальні вимоги до ПК:
Intel Pentium 100 мГц;
операційна система MS DOS;
пам’ять 288 байт;
дисковод або CD ROM;
клавіатура.
Висновок
У цій курсовій роботі вирішена задача про призначення.
Розроблено алгоритм рішення поставленої задачі.
Програма складена і налагоджена у середовищі програмування Турбо Паскаль.
У процесі налагодження була отримана цілком працездатна програма.
Проведено тестування програми. Аналіз результатів показав, що задача успішно виконана.
Довідкова література
1. Б.Іванов “Дискретная математика. Алгоритмы и программы”.
2. Н.Вірт “Алгоритми + Структури даних = Програма”.
3. Т.Рюттен, Г.Франкен “Турбо Паскаль 6.0”.