Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп’ютерних та інформаційних технологій і систем
Курсова робота
з дисципліни «Основи програмування та алгоритмічні мови»
Розробив cтудент
групи 101-ТН
Керівник роботи
Полтава 2010
Зміст
Вступ
Постановка задачі
Розв’язання задачі
Алгоритм задачі
Реалізація програми
Демонстрація роботи програми
Висновок
Використана література
Вступ
Щоб написати цю програмупотрібні знання мови програмування Turbo Pascal, а точніше знання алгоритмівта вміння використовувати графічні примітиви модуля Graph.
Turbo Pascal — мова програмування навчального призначення. Належить до Алгол-подібних мов. Маєжорстку типізацію, тобто ціле значення можна присвоїти лише цілій змінній.
Цю мову створено 1970 рокуНіклаусом Віртом, як алгоритмічна мова. Існує безліч різних версій з підтримкоюоб'єктно-орієнтованого програмування. Також є функції для відладки програми (нагляд,покрокове виконання та інші).
У моїй програмі потрібнопосортувати вагони з довільного порядку в порядок через один. Для цього у нас єнабір вагонів, що знаходиться зправа, стек — для проміжних вагонів, та лівасторона для результату. Для виконання ми можемо користуватися трьома оперіціями:МИМО, В, ІЗ. За один крок можна переміщати лише один вагон.
Постановка задачі
«Залізничний вузол»
Залізнодорожний сортувальнийвузол зроблений так, як показано на малюнку. На правій стороні зібрано увипадковому порядку декілька вагонів двох типів по Nштук. Тупік може вміщати всі вагони. Користуючись трьома сортувальнимиоперціями В, ІЗ, МИМО, зібрати вагони на лівій стороні так, щоб воничергувалися. Для вирішення задачі достатньо 3N-1операцій. По запиту користувача программа повинна продемонструвати правильнесортування вагонів.
/>Розв’язання задачі
У задачі є три положення вагонів:
На початку
В стеку
В кінці
Мій алгоритм спочатку виконуєоперацію МИМО, так як не вказано який вагон повинен бути першим. Потім слідуєголовна чатина алгоритму поки стек та початок не спорожніють.
Головний алгоритм перевіряєсочатку стек на присутність вогону другого типу. Якщо перший вагон не такий якостанній, то виконати операцію "ІЗ". У випадку коли не підходить,виконати пошук у початку. Якщо перший вагон «не такий» то виконатиоперацію «В» та продовжити пошук доки не знайдеться другий тип тавиконати «МИМО».
У програмі замість того, щобздвигати при добавленні-вилученні вагона всі елементи реалізовано змінні, яківказують на останній елемент, тобто розмірність масиву.
Всі три положення у виглядімасиву змінних цілого типу. Можуть приймати значення 0-пусто, 1-перший тип,2-другий тип.
Для графічного зображенняпроцесу сортування використано модуль Graph. tpu. Спочатку зображуються чотири лінії: дві горизонтальні,які утворюють ліву та праву частини, та дві вертикальні — стек.
При зображенні вагоніввикористано цикл із зміщенням. Вагои зображуюються червоним та зеленимкольорами.
У програмі присутній почаковийнабір даних, але є можливість вводу з текстового файлу «rail.dat». Цей режим присутній у вигляді неактивноготексту.
При виконанні операційсортування вимальовуються підказки у вигляді стрілок та напису виконаноїоперації.
У кінці роботи програма виводитькількість виконаних операцій та число 3N-1 яке ємаксильмальною кількістю операцій.
Алгоритм задачі
Присвоєння початкових значень тасортувальний алгоритм
/>
Алгоритм графіки
/>
Алгоритм функцій «В»,"ІЗ", «МИМО»
/>
Реалізація програми
program railway;
uses graph,crt;
var
left: array [1. .1000] ofinteger;
right: array [1. .1000] ofinteger;
stok: array [1. .1000] ofinteger;
f1: text;
l,r,s: integer;
n,op: integer;
d,m,z: integer;
procedure anim (i: integer);
var j: integer;
begin
clearviewport;
SetLineStyle (DottedLn, 0,NormWidth);
line (10,50,630,50);
line (10,80,630,80);
line (295,50,295,470);
line (325,50,325,470);
SetLineStyle (SolidLn, 0,NormWidth);
setcolor (green);
for j: =r downto 1 do
begin
if right [j] 0 then
begin
if right [j] =2then setcolor (red);
rectangle (335+r*35-j*35,50,365+r*35-j*35,80);
if right [j] =2then setcolor (green);
end;
end;
for j: =1 to l do
begin
if left [j] =2then setcolor (red);
rectangle (10+j*35,50,40+j*35,80);
if left [j] =2then setcolor (green);
end;
for j: =1 to s do
begin
if stok [j] =2then setcolor (red);
rectangle (295,85+j*35,325,115+j*35);
if stok [j] =2then setcolor (green);
end;
setcolor (white);
case i of
1: begin
line (200,40,440,40);
line (200,40,220,45);
line (200,40,220,35);
outtextxy (200,25,'MIMO');
end;
2: begin
line (335,100,335,250);
line (335,250,330,230);
line (335,250,340,230);
outtextxy (345,240,'B');
end;
3: begin
line (285,100,285,250);
line (285,100,290,120);
line (285,100,280,120);
outtextxy (265,100,'IZ');
end;
end;
delay (20000);
end;
procedure P_OP(i: integer);
begin
case i of
1:
begin
inc (l);
left [l]: =right [r] ;
right [r]: =0;
dec (r);
end;
2:
begin
inc (s);
stok [s]: =right [r] ;
right [r]: =0;
dec (r);
end;
3:
begin
inc (l);
left [l]: =stok [s] ;
stok [s]: =0;
dec (s);
end;
end;
inc (op);
anim (i);
end;
begin
right [1]: =2;
right [2]: =2;
right [3]: =1;
right [4]: =1;
right [5]: =1;
right [6]: =2;
n: =6;
{assign (f1,'rail. dat');
reset (f1);
while not eof (f1) do
begin
read (f1,right [n]);
inc (n);
end;
close (f1); }
d: =detect;
initgraph (d,m,'');
r: =n;
l: =0;
s: =0;
p_op (1);
while (r+s>0) do
begin
if s>0 then
if left [l] stok[s] then
p_op (3);
while left [l] =right[r] do
p_op (2);
if r>0 thenp_op (1);
end;
anim (0);
readln;
closegraph;
clrscr;
writeln ('Operations:',op,'
readln;
end.Демонстрація роботи програми
Операція «МИМО»
/>
Операція «В»
/>
Операція "ІЗ"
/>
Висновок
Дана програма дозволяє сортувативагони двох типів найкоротшим шляхом. Також, виконавши деякі зміни, можназбільшити кількість типів вагонів.
Написанням цієї программи яотримав гарні навики розробки графічних завдань в Turbo Pascal. Особливо цікаво булорозробити процедуру для зображення процесу сортування.
Використана література
1. Ковалюк Т.В. Основи програмування — К., 2005