|
|
|
 |
Створення програми "Шаховий кінь" |
|
 |
БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Створення програми "Шаховий кінь"
Створення програми "Шаховий кінь"
13 Міністерство освіти і науки України Полтавський національний технічний університет імені Юрія Кондратюка Факультет інформаційних та телекомунікаційних технологій і систем Кафедра комп'ютерних та інформаційних технологій і систем Курсова робота з дисципліни "Основи програмування та алгоритмічні мови" Розробив 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;vararr: 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;vara,d,m,b,sz,c: integer;f: text;n: string;beginsz: =32;d: =detect;initgraph (d,m,'');setfillstyle (1,brown);cleardevice;for a: =1 to 8 dofor b: =1 to 8 dobeginrectangle (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 dobeginrewrite (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;vara,b,e: integer;beginarr [i,j]: =1;row [move_num]: =i;col [move_num]: =j;inc (move_num);for a: =1 to 8 dobeginif move_num>=65 thenbeginexit;end;b: =i+ktmov1 [a] ;e: =j+ktmov2 [a] ;if (b<1) or (b>8) or (e<1) or (e>8) thencontinue;if (arr [b,e] =1) thencontinue;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;beginktmov1 [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
|
|
 |
НОВОСТИ |
 |
|
| Изменения |
|
| Прошла модернизация движка, изменение дизайна и переезд на новый более качественный сервер |
|
