Реферат

Курсова робота, 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:=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 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”.