Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп’ютерних та інформаційних технологій і систем
Курсова робота
з дисципліни "Основи програмування та алгоритмічні мови"
Розробив 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] 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
Другие работы по теме:
Цінова політика туристичних підприємств
МІНІСТЕРСТВО НАУКИ ТА ОСВІТИ УКРАЇНИ По ценовой политике На тему: «Цінова політика туристичних підприємств» м. Одеса 2011 р. ЗМІСТ Введення 1. Ціна в комплексі маркетингу туристичного підприємства. …1-2
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
Засвіт встали козаченьки Маруся Чурай
Автор: Народна творчість. Засвіт встали козаченьки В похід з полуночі, Заплакала Марусенька Свої ясні очі. Не плач, не плач, Марусенько, Не плач, не журися
Білий кінь Шептало
Автор: Дрозд Володимир. Ішов підпасок і тягнув позад себе батіг, потім хвацько стрельнув ним, сказавши дядькові Степану, що йому потрібен кінь для приводу. Шептало зіщулився від звуку батога, шарпнувся разом з іншими кіньми в закуток й гидливо підібрав губи, бо ненавидів табун, гурт і загорожі. Спочатку бригадні коні глузували з нього, потім самі стали його обходити.
Збірник афоризмів Пчола
Збірник афоризмів "Пчола" Автор: Народна творчість. (Златоструй //Древняя Русь X—ХIIІ веков.— М.: Молодая гвардия. 1990) Лагідне слово розрушить гнів.
Стоїть явір над водою
Автор: Народна творчість. Стоїть явір над водою, В воду похилився, На козака пригодонька: Козак зажурився. Не хилися, явороньку, Ще ж ти зелененький,
Смерть матері Юговичів
Автор: Народна творчість. Милий Боже, що за дивне диво! Ой зібралось військо на Косові, А в тім війську Юговичів дев’ять1, А десятий Юг-Богдан поважний.
Автоматизований облік власників автомобілей
Розробка програми "Авто" для введення та збереження інформації про власників та їхні автомобілі. Побудова математичної моделі. Критерії вибору та пошуку даних. Структура введених та збережених у файлах програми даних. Алгоритм основної програми та її код.
Розроблення програми на мові С для OS Windows
Технічне обґрунтування та етапи розроблення програми на мові С для OS Windows, яка виводить у вікно запропонованої таблиці інформацію при натисненні клавіш клавіатури. Проблеми систем програмування. Резервування додаткової пам’яті в структурi класу вiкна.
Програма HelloWin
Опрацювання роботи програми HelloWin, яка демонструє основні принципи створення вікна у OS Windows. Вивчення матеріалу, викладеного у файлі допомоги. Використання функцій для створення вікна, відображення у ньому тексту, відтворення звукових файлів.
Контроль доступу до вибраних файлів з веденням протоколу
Ведення протоколу роботи комп’ютера. Розробка програми для створення списку розширень файлів і занесення часу і дати доступу до них на мові програмування Асемблер. Виклик переривання 21h код-функції та занесення до регістрів. Алгоритм та лістинг програми.
Аналіз успішності групи
Розробка програми мовою Turbo Pascal для автоматизації процесу перевірки оцінок та аналізу успішності групи, для збереження і перегляду всієї інформації стосовно навчання. Формальна постановка задачі, створення алгоритму та вихідного коду програми.
Теорія множин. Операції над множинами та їх властивості
Теоретичні основи теорії множин. Основні операції над множинами та їх властивості. Складання програми для обчислення результуючої множини за вихідним і спрощеним виразами. Виконання операцій над множинами, застосування їх властивостей, спрощення виразів.
Проектування печатних плат в P-CAD для Windows
Основні принципи роботи з програмами PATTED та SYMED. Розстановка на робочому полі створених та стандартних компонентів за допомогою програми Schematic, їх з'єднання проводниками, розташування виводів та отримання схеми печатної плати. Перетворення схеми.
Діагностичні програми (Sysinfo, Speedisk)
Загальна характеристика та принцип дії діагностичних програм. Запуск програми Sysinfo, виписка інформації про систему ПК. Виклик меню Benchmark та порядок проведення тестування процесора на швидкодію, системної плати. Оптимізація жорсткого диску С:.
Автоматизований аналіз злочинності
Створення програми "Аналізатор злочинності в регіоні". Структура зберігаючих даних. Неформальна постановка задачі. Алгоритм основної програми. Введення і збереження інформації. Можливість перегляду всіх існуючих документів. Вихідний код програми.
Автоматизоване нарахування заробітної плати
Методика та особливості створення програми "Автоматизоване нарахування платні" для збереження, перегляду та аналізу введеної інформації, її алгоритм та вихідний код. Аналіз факторів, які впливають на формування заробітної платні робітника підприємства.
Задача про розміщення ферзів Дерево пошуку та його обхід
Реферат на тему: Задача про розміщення ферзів. Дерево пошуку та його обхід Розглянемо шахівницю, що має розміри не 8 8, а n n, де n>0. Як відомо, шаховий ферзь атакує всі клітини та фігури на одній з ним вертикалі, горизонталі та діагоналі. Будь-яке розташування кількох ферзів на шахівниці будемо називати їх
Огляд популярної поштової програми The Bat
РЕФЕРАТ на тему: «Огляд популярної поштової програми The Bat!» he Bat! дійсно могутній і зручний клієнт електронної пошти для Windows 95/98/Me/NT/2000 із приємним інтерфейсом і безліччю унікальних функцій, необхідних у роботі:
Аналіз та обчислення дужкових виразів
Реферат на тему: Аналіз та обчислення дужкових виразів У розділі 9 розглядалися дужкові арифметичні вирази, мова яких породжується розширеною LA(1)-граматикою G2:
Уява
Тема: Уява Функція уяви: створення нових образів – випереджуючі відображення реальності. Механізми уяви : дисоціація вражень і елементів у новій комбінації. У
Реферат з інформатиткии Програма Провідник
Призначення програми Файлова система ОС Windows 98 має деревоподібну ієрархічну структуру. Під час переміщення, наприклад, файла з папки, розташованої на диску, в іншу, розміщену на іншому диску, необхідно послідовно відкрити папки на першому диску, щоб досягти вихідної папки, а потім — на другому, щоб на екрані з’явилася цільова папка.
Табличний редактор Microsoft Excel
Теоретичні відомості 1.1. Табличний редактор Microsoft Excel Microsoft Excel – це складова частина пакето-прикладних програм Microsoft Office. Microsoft Excel – призначений для створення електронних таблиць і найбільшою перевагою є можливість досліджувати, аналізувати дані і виконувати обчислення.
Програми архіватори winzip winrar
РЕФЕРАТ на тему: ПРОГРАМИ АРХІВАТОРИ WinZIP, WinRAR. Для отримання копій файлів, використовують команди копіювання MS DOS. Але в цьому випадку копії будуть займати багато місця, що змушує мати велику кількість дискет. Більш доцільно використовувати для створення архівних копій спеціально розроблені програми.