Название: Створення програми "Шаховий кінь"
Вид работы: курсовая работа
Рубрика: Информатика и программирование
Размер файла: 248.43 Kb
Скачать файл: referat.me-140097.docx
Краткое описание работы: Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.
Створення програми "Шаховий кінь"
Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп’ютерних та інформаційних технологій і систем
Курсова робота
з дисципліни "Основи програмування та алгоритмічні мови"
Розробив cтудент
групи 101-ТН
Захарченко О.П.
Керівник роботи
д. т. н. Ляхов Олександр Логвінович
Полтава 2010
Зміст
Вступ
Постановка задачі
Розв’язання задачі
Алгоритм задачі
Демонстрація роботи програми
Висновок
Використана література
Вступ
Я маю завдання написати програму "Шаховий кінь". Для цього я використовую мову TurboPascal, бо програмування в середовищі MS-DOS набагато простіше ніж у MSWindows. Тому ця простота залишається головною причиною, чому тисячі та тисячі людей починають свій шлях у програмуванні з TurboPascal.
Мова зроблена наприкінці 60-х - на початку 70-х років ХХ-століття швейцарським професором Ніклаусом Віртом для навчання студентів основам програмування. Приставку Турбо мова отримала після створення А. Хейлсбергом, одним з учеників Вірта, компілятора, ща на той час відрізнявся рекордною швидкістю.
Система програмування TurboPascal являє собою єдність компілятора 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] of integer;
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;
procedure writeboard;
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 8 do
for b: =1 to 8 do
begin
rectangle (a*sz,b*sz, (a+1) *sz, (b+1) *sz);
if (a+b) mod 2=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 64 do
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+sz div 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;
procedure addknight;
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 8 do
begin
if move_num>=65 then
begin
exit;
end;
b: =i+ktmov1 [a] ;
e: =j+ktmov2 [a] ;
if (b<1) or (b>8) or (e<1) or (e>8) 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
Похожие работы
-
Автоматизований облік власників автомобілей
Розробка програми "Авто" для введення та збереження інформації про власників та їхні автомобілі. Побудова математичної моделі. Критерії вибору та пошуку даних. Структура введених та збережених у файлах програми даних. Алгоритм основної програми та її код.
-
Автоматизований аналіз злочинності
Створення програми "Аналізатор злочинності в регіоні". Структура зберігаючих даних. Неформальна постановка задачі. Алгоритм основної програми. Введення і збереження інформації. Можливість перегляду всіх існуючих документів. Вихідний код програми.
-
Автоматизоване нарахування заробітної плати
Методика та особливості створення програми "Автоматизоване нарахування платні" для збереження, перегляду та аналізу введеної інформації, її алгоритм та вихідний код. Аналіз факторів, які впливають на формування заробітної платні робітника підприємства.
-
Створення програми "Залізничний вузол"
Використання мови програмування Turbo Pascal, алгоритмів та графічних примітивів модуля Graph. Розробка та реалізація програми для сортування вагонів з довільного порядку в порядок через один. Присвоєння початкових значень та сортувальний алгоритм.
-
Створення програми гри "Шибениця"
Алгоритмічна мова програмування універсального призначення Turbo Pascal. Розробка і створення програми для гри "Шибениця". Алгоритм функціонування программи, блок-схема алгоритму. Використання додаткових модулів Graph та Crt у процессі створення програми.
-
Довідкова система по кримінальному праву
Створення довідкової системи по зменшенню витрат часу на здобуття інформації по кримінальному праву. Розробка алгоритму основної програми на мові програмування Turbo Pascal з підключенням модуля СRT, якій відповідає за графіку і DOS та працює з файлами.
-
База даних по приватним підприємствам регіону
Програма "Приватка" для збереження та перегляду всієї інформації, що стосується пошуку підприємства. Розробка алгоритму та програмування на мові Turbo Pascal. Формальна та неформальна постановка задачі. Структура зберігаючих даних. Вихідний код програми.
-
Основні принципи модульного програмування та стеки
Ініціалізація графічного режиму. Відображення координатних осей, асимптот, надписів. Відображення графіка. Перебір точок з абсцисами від лівого до правого кінця екрана. Визначення масштабу відображення точки на екрані. Визначення ординати точки. Черги та
-
Контроль доступу до вибраних файлів з веденням протоколу
Ведення протоколу роботи комп’ютера. Розробка програми для створення списку розширень файлів і занесення часу і дати доступу до них на мові програмування Асемблер. Виклик переривання 21h код-функції та занесення до регістрів. Алгоритм та лістинг програми.
-
Вирізання картинок з екрану та запис їх в BMP форматі (для графіки) і TXT форматі (для тексту)
Розробка резидентної програми за допомогою мови асемблер, яка дозволить перехопити зміст текстового та графічного екрану у файл (відповідно TXT і BMP). Вибір та обґрунтування методу розв'язки даної задачі. Алгоритм і реалізація програми, системні вимоги.