Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп’ютерних та інформаційних технологій і систем
Курсова робота
з дисципліни «Основи програмування та алгоритмічні мови»
Розробив cтудент
групи 101-ТН
Захарченко О.П.
Керівник роботи
д. т. н. Ляхов ОлександрЛогвінович
Полтава 2010
Зміст
Вступ
Постановка задачі
Розв’язання задачі
Алгоритм задачі
Демонстрація роботи програми
Висновок
Використана література
Вступ
Я маю завдання написати програму«Шаховий кінь». Для цього я використовую мову Turbo Pascal, бо програмування всередовищі MS-DOS набагатопростіше ніж у MS Windows. Тому ця простота залишається головною причиною, чомутисячі та тисячі людей починають свій шлях у програмуванні з Turbo Pascal.
Мова зроблена наприкінці 60-х — на початку 70-х років ХХ-століття швейцарським професором Ніклаусом Віртом длянавчання студентів основам програмування. Приставку Турбо мова отримала післястворення А. Хейлсбергом, одним з учеників Вірта, компілятора, ща на той часвідрізнявся рекордною швидкістю.
Система програмування Turbo Pascalявляє собою єдність компілятора Pascal (мова названа начесть видатного французького математика та філософа Блеза Паскаля 1623-1662р. р)та інструментальної оболонки, що підвищує єфективність створення программ.
Постановка задачі
Умова задачі: «Шаховий кінь».
Написати програму, яка реалізуєрух коня по всім 64 кліткам шахової дошки так, щоб він сходив на кожне поле поодному разу. Розробити алгоритм з відходами назад. Необхідно, щоб рух коняспостерігався під час роботи програми. На пройдених клітках шахової дошкизаписуються номери ходів.
Розв’язанню цієї задачіприсвятили багато досліджень та існує багато різних методів вирішення. Цязадача відома як мінімум з XVIII століття, ЛеонардЄйлер посвятив їй велику роботу. Крім цього він розробив для інших фігураналогічні задачі.
В термінах теорії графів коженмаршрут коня, що проходить всі поля шахової дошки, відповідно гамільтоновомушляху (або циклу, якщо маршрут замкнутий) у графі, вершинами якого являютьсяполя дошки, то два останні поля з’єднані ребром, якщо з одного на друге можнапотрапити за один хід коня.
В цей час задача підрахунку всіхнезамкнених маршрутів набагато складніше і не вирішена. Ми візьмемо лише одиннайпростіший шлях.Розв’язання задачі
Задача зроблена алгоритмом звідходом назад. Використаємо два одновимірних масиви row[64] та col [64] для зберігання відповідних номеріврядків та стовпців, які кінь послідовно проходить по дошці.
Кінь, що знаходиться в позиції (i,j), може наступним ходом опинитисяв клітинках з кординатами (i-2, j+1), (i-1, j+2), (i+1, j+2), (i+2,,j+1), (i+2,,j-1),(i+1, j-2), (i-1, j-2), (i-2, j-1). Якщо кінь стоїть з краю дошки, то деякійого ходи можуть викликати переміщення за межі дошки, а це недопустимо. Вісімможливих переміщень даної фігури задані в вигляді двох масивів ktmov1 [8] та ktmov2 [8].
Виходячи з цього, кінь в позиції(i,j) може переміститися впозицію (i+ktmov [k], j+ktmov2 [k]), де k-значення з діапазону 1-8, щовибирається з умови, що кінь повинен бути на дошці.
У своїй программі, для виведеннячисел у графічному режимі в задані кординати я спочатку зберіг числа утекстовий файл, а потім зчитав у строкову змінну, так як процедура outtextxy () виводить лише символьні дані.
Программа генерує відповідно дозаданих початкових кординат маршрут руху коня, це може зайняти кілька секунд,залежно від процесора. Потім по натисканню кнопки виводить наступну точкумаршруту.
Алгоритм задачі
А. Початок
/>
Б. Виведення зображення
/>
В. Алгоритм пошуку
/>
Реалізація програми
program horse;
uses graph,crt;
var
arr: array [1. .8,1. .8] ofinteger;
row: array [1. .64] of integer;
col: array [1. .64] of integer;
i,j,move_num,d:integer;
ktmov1: array [1..8] of integer;
ktmov2: array [1..8] of integer;
procedurewriteboard;
var
a,d,m,b,sz,c: integer;
f: text;
n: string;
begin
sz: =32;
d: =detect;
initgraph (d,m,'');
setfillstyle (1,brown);
cleardevice;
for a: =1 to 8do
for b: =1 to 8do
begin
rectangle (a*sz,b*sz,(a+1) *sz, (b+1) *sz);
if (a+b) mod2=0 then floodfill (a*sz+3,b*sz+3,white);
end;
assign (f,'tmp.dta');
circle (row [1]*sz+sz div 2,col [1] *sz+sz div 2,10);
for c: =2 to 64do
begin
rewrite (f);
write (f,c);
close (f);
reset (f);
read (f,n);
close (f);
outtextxy (row[c] *sz+3,col [c] *sz+3,n);
circle (row [c]*sz+sz div 2,col [c] *sz+sz div 2,10);
line (row [c] *sz+szdiv 2,col [c] *sz+sz div 2,row [c-1] *sz+sz div 2,col [c-1] *sz+sz div 2);
readkey;
end;
readln;
closegraph;
end;
procedureaddknight;
var
a,b,e: integer;
begin
arr [i,j]: =1;
row [move_num]:=i;
col [move_num]:=j;
inc (move_num);
for a: =1 to 8do
begin
ifmove_num>=65 then
begin
exit;
end;
b: =i+ktmov1 [a];
e: =j+ktmov2 [a];
if (b8) or (e8) then
continue;
if (arr [b,e] =1)then
continue;
i: =b;
j: =e;
addknight;
end;
dec (move_num);
arr [row [move_num],col[move_num]]: =0;
dec (move_num);
i: =row [move_num];
j: =col [move_num];
inc (move_num);
end;
begin
ktmov1 [1]: =-2;
ktmov1 [2]: =-1;
ktmov1 [3]: =1;
ktmov1 [4]: =2;
ktmov1 [5]: =2;
ktmov1 [6]: =1;
ktmov1 [7]: =-1;
ktmov1 [8]: =-2;
ktmov2 [1]: =1;
ktmov2 [2]: =2;
ktmov2 [3]: =2;
ktmov2 [4]: =1;
ktmov2 [5]: =-1;
ktmov2 [6]: =-2;
ktmov2 [7]: =-2;
ktmov2 [8]: =-1;
i: =1;
j: =1;
move_num: =1;
addknight;
writeboard;
end.Демонстрація роботи програми
Робота программи:
/>
/>
Висновок
Дана програма дозволяє знаходитимаршрут обходу шахової дошки через алгоритм пошуку з відходами. Також можливовикористання цього алгоритму на дошках більшого розміру, але не менше ніж 5х5. Такяк програма перебирає всі можливі ходи, їй потрібен час на виконання.
Використана література
1. Ковалюк Т.В. Основи програмування — К., 2005