Програма для гри у шахи

1.Технічне завдання

На шаховій дошці розмірами M*N клітинок стоїть слон (фігура, що ходить по діагоналі). З’ясувати, чи може слон дійти до поля (х, у) Якщо може, то за яку найменшу кількість ходів; якщо кількість ходів більша за 1, то вказати, через які проміжні клітинки повинен пройти слон (якщо таких маршрутів кілька, вказати будь-який один з них). Поля шахової дошки кодуються парою натуральних чисел 1. M, 1. N, де перше число — номер горизонталі, а друге — номер вертикалі (1?M, N?1000). Технічні умови: Ви вводите з клавіатури через пропуск числа M, N, а далі координати початкового та кінцевого полів бажаного маршруту слона. Ви виводите на екран число К (мінімальна кількість ходів), а далі в К-1 рядках по 2 числа через пропуск — координати відвіданих полів. Якщо розв’язків немає, вивести 0.

Приклад:

Введення 10 10 1 1 1 7

Виведення 2 4 4

Рис.

2.Аналіз завдання

Розіб'ємо задачу на введення інформації, перевірку інформації за певних умов та виведення результату.

Для введення інформації використаємо діалог с користувачем. Поля шахової дошки кодуються парою натуральних чисел 1. M, 1. N, де перше число — номер горизонталі, а друге — номер вертикалі (1?M, N?1000). Просимо користувача ввести з клавіатури через пропуск числа M, N, а далі координати початкового та кінцевого полів бажаного маршруту слона.

Перевірка інформації полягає в двох аспектах. Перший, це відповідність умові. Другий, це пошук мінімального ходу за допомогою двох функцій: solve та show_result.

Після перевірки, програма виконується і виводиться мінімальна кількість ходів, або координата відвіданих полів.

комп’ютерний програма шахи

3.Алгоритм роботи програми

Таблиця 3.1 — опис констант та змінних.

Схема Схема Схема Основна програма:

2 — ввід даних, 3 — перевірка ввідних даних на валідність, 4 — якщо початкова і кінцева клітинки різних кольорів, 6 — якщо початкова та кінцева клітини збігаються, 8 — якщо ширина або висота дошки дорівнює одиниці, то слон не може рухатися.

void solve ()

2−3 — якщо ширина дошки довше її висоти, замінимо ці значення і координати кожної точки, а у відповіді знову замінимо х і у координати кожної точки, 4−5 — якщо на отриманій дошці, в якій вже висота (за задумом) точно довше висоти, пункт призначення нижче початкової позиції слона, замінимо ці точки ((х1; у1) і (х2; у2)) місцями, а у відповіді виведемо точки в зворотному порядку, 6 — поки слон не може потрапити з 1 ходу з поточною його позиції на кінцеву, шукаємо наступну позицію, 7−9 — перевіримо, чи можна за 2 ходи потрапити в кінцеву позицію для цього перевіримо чи можна з будь клітини, на яку можна перейти 1 ходом, потрапити одним ходом в кінцеву клітку в цьому випадку клітинка, що перевіряється буде збігатися з кліткою, на якій знаходиться слон, пропустимо її, 10−11 — значить можна з клітини (xb; у1) потрапити на клітку (х2; у2) за два ходи, перенесемо слона (xb; у1) на клітину (х; у), а в наступній перевірці циклу abs (xb — xe)! = abs (yb — ye) поверне false, і пошук закінчиться, 13 — якщо кроків n (і n> 1), проміжних клітин n — 1, а номер останнього кроку n — 2 (через нумерації з нуля), 14 — якщо з двох ходів не дійти, просто піднімемося вище.

void show_result ()

2 — номер першого на вивід проміжної клітини, останньою і крок для циклу, 3 — номери першої та другої на вивід координати, 3−5 — якщо початкова та кінцева клітина були змінені місцями, проміжні виводимо з останнього по перший.

bool check_input_data () — перевірка ввідних даних.

4.Текст програми

#include

#include

#include

using namespace std;

int m, n, xb, yb, xe, ye;

// будемо додавати по кроку кожного разу, коли слон не може з поточної

//позиції перейти на кінцеву клітинку

int steps = 1; // кількість кроків

int intermediate_steps[999][2]; // координати середніх ходів

bool m_and_n_was_swapped = false;

// begin і end — координати початку руху та кінцевого пункту

bool begin_and_end_was_swapped = false;

int abs (int x)

{

return x < 0? -x: x;

}

void show_result ()

{

// номер першої на вивід середньої клітинки, останньої та крок для

//циклу

int bg = 0, en = steps — 2, step = 1;

// номера першої та другої координати на вивід

int n1 = 0, n2 = 1;

// якщо початкова та кінцева клітинка помінялися місцями

// середні виводимо з останнього по перший

if (begin_and_end_was_swapped)

{

swap (bg, en);

step = -1;

}

if (m_and_n_was_swapped) swap (n1, n2);

cout << steps << endl;

for (int i = bg; i ≠ en + step; i += step)

{

cout << intermediate_steps[i][n1];

cout << ' ' << intermediate_steps[i][n2] << endl;

}

}

void solve ()

{

// якщо ширина дошки довше її висоти, поміняємо ці значення

// координати кожної точки, а у відповіді знову поміняємо х і у

// координати кожної точки (або просто виведемо у вигляді (у; х)

if (m > n)

{

swap (m, n);

swap (xb, yb);

swap (xe, ye);

m_and_n_was_swapped = true;

}

// якщо на отриманій дошці, в якій вже висота (за задумом)

// точно довше висоти, пункт призначення нижче початкової позиції

// слона, поміняемо ці точки ((х1; у1) і (х2; у2)) місцями,

// а в відповіді виведемо точки в оберненому порядку

if (yb > ye)

{

swap (xb, xe);

swap (yb, ye);

begin_and_end_was_swapped = true;

}

// поки слон не може потрапити з 1 ходу з посаткової позиції

// на кінцеву, шукаємо наступну позицію

while (abs (xb — xe) ≠ abs (yb — ye))

{

// перевіримо, чи можна за 2 ходи потрапити в кінцеву позицію

// для цього перевіримо чи можна з будь клітини, на яку можна

// перейти 1 ходом слона, потрапити одним ходом в кінцеву клітинку

bool can_reach_in₂_steps = false;

for (int x = 1; x <= m && !can_reach_in₂_steps; x++)

{

// цьому випадку клітинка, що перевіряється буде збігатися з

// кліткою, на якый знаходився слон, пропустимо її

int y = abs (xb — x) + yb;

if (abs (x — xe) == abs (y — ye))

{

// значить можна з клітини (xb; у1) потрапити на клітку (х2; у2)

// за два ходи, перенесемо слона (xb; у1) на клітинку (х; у),

// а в наступній перевірці цикла abs (xb — xe) ≠ abs (yb — ye)

// поверне false, і пошук завершиться

can_reach_in₂_steps = true;

xb = x;

yb = y;

// додамо клітинку (х; у) в масив проміжних клітин

steps++;

// якщо кроків n (і n> 1), проміжних клітин n — 1,

// а номер останнього кроку n — 2 (через нумерації з нуля)

intermediate_steps[steps — 2][0] = x;

intermediate_steps[steps — 2][1] = y;

}

}

// якщо з двох ходів не дійти, просто піднімемося вище

if (!can_reach_in₂_steps)

{

if (xb — 1 > m — xb)

{

// якщо перший ряд далі, підемо вгору-вліво

// вгору підніметься на стільки клітин, на скільки і наліво

yb += xb — 1;

// а вліво до першого ряда

xb = 1;

}

else

{

// останній ряд далі, тому підемо вгору-вправо

// вгору підніметься на стільки клітин, на скільки і вправо

yb += m — xb;

// а вправо до першого ряда

xb = m;

}

// додамо клітку (xb; у1) в масив проміжних клітин

steps++;

// якщо кроків n (і n> 1), проміжних клітин n — 1,

// а номер останнього кроку n — 2 (через нумерації з нуля)

intermediate_steps[steps — 2][0] = xb;

intermediate_steps[steps — 2][1] = yb;

}

}

show_result ();

}

bool check_input_data ()

int main (void)

{

cin >> m >> n >> xb >> yb >> xe >> ye;

// перевірка ввідних даних на валідність

if (!check_input_data ())

{

cout << «Invalid input data» ;

return 0;

}

// якщо початкова і кінцева клітинки різних кольорів

if ((xb + yb + xe + ye) % 2) cout << 0;

// якщо початкова та кінцева клітини збігаються

else if (xb == xe && yb == ye) cout << 0;

// якщо ширина або висота дошки дорівнює одиниці,

// то слон не може рухатися

else if (m == 1 || n == 1) cout << 0;

// інакше шукаємо кількість ходів і проміжні клітини

else solve ();

return 0;

}

5.Контрольний приклад

Введення:

Поле розміром: 500? 500

Координати початку: (50;8)

Координати кінця: (124;45)

Рисунок 5.1 — Результат роботи програми, після введення 500 500 50 8 124 54

Виведення:

1. Виведення мінімальної кількості ходів:0 (ходів немає).

2. Виведення координат відвіданих полів, оскільки розв’язків немає то координати не виводяться.

Введення:

Поле розміром: 678? 567

Координати початку: (43;56)

Координати кінця: (223;446)

Рисунок 5.2 — Результат роботи програми, після введення 678 567 43 56 223 446

Виведення:

1. Виведення мінімальної кількості ходів:2 (2 ходи).

2. Виведення координат відвіданих полів: (328;341) (з координати (43;56) до (328;341) — перший хід, з (328;341) до (223;446) — другий).

Введення:

Поле розміром: 10? 10

Координати початку: (1;1)

Координати кінця: (7;7)

Виведення:

Рисунок 5.3 — Результат роботи програми, після введення 10 10 1 1 7 7

Виведення:

3. Виведення мінімальної кількості ходів:1 (1 хід).

4. Виведення координат відвіданих полів: не виводяться, оскільки хід лише 1.

Висновок

Програма розроблена для використання у грі в шахи. Вона зручна якщо гра не наживо з людиною, а через гру в інтернеті, або з комп’ютером (через додатак). Недолік цієї програми у тому, що вона має деякі умови для розрахунку, такі як початкові та кінцеві точки разташування, також не завжди кількість ходів буде задовольняти умовам гри, тому навряд чи дану програму можна застосовувати на практиці. У подальшому можна вдосконалити програму зробивши її універсальною, тобто зробити розрахунок для інших фігур (не тільки для слона) та їх комбінацій і використовувати її як порадник у грі.

Список використаних джерел

1. Основи програмування та алгоритмічні мови /[Парфьонов Ю.Е., Федорченко В. М., Лосєв М.Ю., Щербаков О.В.] - [частина 1-а] - Харків: ХНЕУ, 2008. — 127с.

2. Основи програмування та алгоритмічні мови /[Парфьонов Ю.Е., Федорченко В. М., Лосєв М.Ю., Щербаков О.В.] - [частина 2-а] - Харків: ХНЕУ, 2009. — 179с.

3.