Реферат
Курсова робота, 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] ofReal; {тип масиву для розрахунк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 ] ofTMenuItem;{пукти}
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 thenHeight := 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:=getMaximalWidth + 4;
{ робимо заголовок}
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 ThenProcedureType(Items[N].Action);
end;
end;
End;
{додати пункт до меню}
Procedure TMenu.AddItem(Caption: String;Action: ProcedurePointer);
begin
If ItemsCount
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 — Lendiv 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] ofInteger;
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]
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]
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]
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
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
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
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
cnt := cnt + 1;
if (m > 0) AND (cnt
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
begin
if dj
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
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”.