Редактирование: Информатика: Расстановка шахматных фигур
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
− | '''[[ | + | '''[[Лебедев Станислав]]''' |
− | ''' | + | '''Функционал программы''': получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n; |
− | ''' | + | '''Идея алгоритма''': рекурсивно вызывается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается. |
− | + | Скачать можно [http://tm.spbstu.ru/Файл:Шахматы.rar тут]. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
<div class="mw-collapsible mw-collapsed" style="width:100%" > | <div class="mw-collapsible mw-collapsed" style="width:100%" > | ||
− | <syntaxhighlight lang="cpp" line start="1" enclose="div" | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> |
− | |||
#include <iostream> | #include <iostream> | ||
− | #include | + | #include <math.h> |
− | #include < | + | #include <cmath> |
+ | |||
using namespace std; | using namespace std; | ||
− | int | + | int n,type, *a, *stak, variant, maxst = 0; |
− | |||
− | |||
− | void | + | void king(int x, int &top) //отметить битые клетки королем |
{ | { | ||
− | + | // 012 | |
+ | // 345 | ||
+ | // 678 | ||
+ | |||
+ | //0 | ||
+ | if (((x % n) > 1) && ((x / n) > 1)) | ||
{ | { | ||
− | + | int ii = x - n - 1; | |
− | + | if (a[ii] != -2) | |
− | |||
− | |||
− | |||
{ | { | ||
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
+ | top++; | ||
} | } | ||
} | } | ||
− | + | ||
− | + | //1 | |
+ | if ((x / n) > 0) | ||
{ | { | ||
− | + | int ii = x - n; | |
− | + | if (a[ii] != -2) | |
− | |||
{ | { | ||
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
− | + | top++; | |
− | |||
− | |||
− | |||
} | } | ||
− | |||
− | |||
− | |||
} | } | ||
− | + | //2 | |
− | + | if (((x % n) < (n - 1)) && ((x / n) > 0)) | |
− | |||
− | |||
− | |||
− | if (((x | ||
{ | { | ||
− | + | int ii = x - n + 1; | |
− | + | if (a[ii] != -2) | |
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | |||
− | |||
− | |||
− | + | //3 | |
− | + | if ((x % n) > 0) | |
{ | { | ||
− | + | int ii = x - 1; | |
+ | if (a[ii] != -2) | ||
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | //5 | ||
+ | if ((x % n) < (n - 1)) | ||
{ | { | ||
− | + | int ii = x + 1; | |
+ | if (a[ii] != -2) | ||
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | //6 | ||
+ | if (((x % n ) > 0) && ((x / n) < (n - 1))) | ||
{ | { | ||
− | + | int ii = x + n - 1; | |
− | + | if (a[ii] != -2) | |
− | + | { | |
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | //7 | ||
+ | if ((x / n ) < (n - 1)) | ||
{ | { | ||
− | + | int ii = x + n; | |
+ | if (a[ii] != -2) | ||
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | //8 | ||
+ | if (((x % n ) < (n - 1)) && ((x / n) < (n - 1))) | ||
{ | { | ||
− | + | int ii = x + n + 1; | |
− | + | if (a[ii] != -2) | |
− | + | { | |
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
+ | top++; | ||
+ | } | ||
} | } | ||
} | } | ||
− | int | + | void bishop(int x, int &top) //отметить битые клетки слоном |
− | |||
{ | { | ||
− | for (int x=0; | + | //вверх влево |
+ | for (int i = (x - (n + 1)); ((i >= 0) && ((i%n) != (n-1))); i -= (n+1)) | ||
{ | { | ||
− | + | if (a[i] != -2) | |
− | |||
{ | { | ||
− | + | a[i]++; | |
− | + | stak[top] = i; | |
− | + | top++; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | } | |
− | + | ||
+ | //вниз вправо | ||
+ | for (int i = (x + (n + 1)); ((i < n*n) && ((i%n) != 0)); i += (n+1)) | ||
+ | { | ||
+ | if (a[i] != -2) | ||
{ | { | ||
− | + | a[i]++; | |
− | + | stak[top] = i; | |
+ | top++; | ||
} | } | ||
} | } | ||
− | |||
− | |||
− | + | //вверх вправо | |
− | + | for (int i = x - (n - 1); ((i >= 0) && ((i%n) != 0)); i -= (n-1)) | |
− | |||
− | |||
− | |||
{ | { | ||
− | + | if (a[i] != -2) | |
− | + | { | |
+ | a[i]++; | ||
+ | stak[top] = i; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | |||
− | |||
− | |||
− | + | //вниз влево | |
− | + | for (int i = x + (n - 1); ((i < n*n) && ((i%n) != (n-1))); i += (n-1)) | |
{ | { | ||
− | + | if (a[i] != -2) | |
+ | { | ||
+ | a[i]++; | ||
+ | stak[top] = i; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | } | |
+ | |||
+ | void knight(int x, int &top) //отметить битые клетки конем | ||
+ | { | ||
+ | if (((x%n) > 0) && (x/n) > 1) | ||
{ | { | ||
− | + | int ii = x - 2*n - 1; | |
+ | if (a[ii] != -2) | ||
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | if (((x%n) > 1) && (x/n) > 0) | ||
{ | { | ||
− | + | int ii = x - n - 2; | |
+ | if (a[ii] != -2) | ||
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | if (((x%n) > 1) && (x/n) < (n - 1)) | ||
{ | { | ||
− | + | int ii = x + n - 2; | |
+ | if (a[ii] != -2) | ||
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | if (((x%n) > 0) && (x/n) < (n - 2)) | ||
{ | { | ||
− | + | int ii = x + 2*n - 1; | |
+ | if (a[ii] != -2) | ||
+ | { | ||
+ | a[ii]++; | ||
+ | stak[top] = ii; | ||
+ | top++; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | if (((x%n) < (n - 1)) && (x/n) < (n - 2)) | ||
{ | { | ||
− | + | int ii = x + 2*n + 1; | |
− | + | if (a[ii] != -2) | |
− | + | { | |
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
+ | top++; | ||
+ | } | ||
} | } | ||
− | |||
− | + | if (((x%n) < (n - 2)) && (x/n) < (n - 1)) | |
− | |||
− | |||
− | |||
{ | { | ||
− | int | + | int ii = x + n + 2; |
− | + | if (a[ii] != -2) | |
{ | { | ||
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
− | + | top++; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
} | } | ||
− | |||
− | |||
− | + | if (((x%n) < (n - 2)) && (x/n) < 0) | |
− | + | { | |
− | + | int ii = x - n + 2; | |
− | + | if (a[ii] != -2) | |
− | + | { | |
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
− | + | top++; | |
− | + | } | |
− | + | } | |
− | + | ||
− | + | if (((x%n) < (n - 1)) && (x/n) < 1) | |
− | + | { | |
− | + | int ii = x - 2*n + 1; | |
− | + | if (a[ii] != -2) | |
− | + | { | |
− | + | a[ii]++; | |
− | + | stak[top] = ii; | |
− | + | top++; | |
− | + | } | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | } | ||
− | |||
− | |||
} | } | ||
− | int | + | void rook(int x, int &top) //отметить битые клетки ладьей |
{ | { | ||
− | + | int k = x - (x % n); | |
+ | while ((k/n) == (x/n)) | ||
{ | { | ||
− | + | ||
− | + | if ((k != x) && (a[k] != -2)) | |
{ | { | ||
− | + | a[k]++; | |
− | + | stak[top] = k; | |
− | + | top++; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | if ( | + | k ++; |
+ | } | ||
+ | |||
+ | k = (x % n); | ||
+ | while (((k/n)) != n) | ||
+ | { | ||
+ | if ((k != x) && (a[k] != -2)) | ||
{ | { | ||
− | + | a[k]++; | |
+ | stak[top] = k; | ||
+ | top++; | ||
} | } | ||
+ | k += n; | ||
} | } | ||
− | + | ||
} | } | ||
− | + | void set_figure(int x, int &top) //ставим фигуры на доску | |
− | + | { | |
− | { | + | //отмечаем "битые" клетки |
− | + | switch (type) | |
− | + | { | |
− | + | //король | |
− | { | + | case 1: |
− | |||
{ | { | ||
− | + | king(x,top); | |
− | + | break; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | |||
+ | //слон | ||
+ | case 2: | ||
+ | { | ||
+ | bishop(x,top); | ||
+ | break; | ||
+ | } | ||
− | + | //конь | |
− | + | case 3: | |
− | + | { | |
− | + | knight(x,top); | |
− | { | + | break; |
− | + | } | |
− | + | //ладья | |
− | + | case 4: | |
− | |||
{ | { | ||
− | + | rook(x,top); | |
− | + | break; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | //ферзь | |
+ | case 5: | ||
{ | { | ||
+ | rook(x,top); | ||
+ | bishop(x,top); | ||
break; | break; | ||
} | } | ||
} | } | ||
− | + | //отмечаем,что в данной клетке стоит фигура | |
+ | a[x] = -1; | ||
+ | stak[top] = x; | ||
+ | top++; | ||
} | } | ||
− | int | + | void step(int top,int x,int st) |
− | { int | + | { |
− | + | int xtop = top; | |
− | + | switch (variant) | |
− | + | { | |
− | + | case 1: | |
− | + | { | |
− | + | if (st != (n - 1)) | |
− | + | { | |
− | + | set_figure(x,top); | |
− | + | for (int i = 0; i < (n*n); i++) | |
− | + | if (a[i] == 0) | |
− | + | step(top,i,st + 1); | |
− | + | } | |
− | + | else[[:File:Шахматы.rar]] | |
− | + | { | |
− | + | set_figure(x,top); | |
− | + | cout << endl; | |
− | + | for (int i = 0; i < (n*n); i++) | |
− | + | { | |
− | + | cout.width(3); | |
− | + | if (((i % n) == 0) && (i != 0)) | |
− | + | cout << endl; | |
− | + | if (a[i] == -1) | |
− | + | cout << 1; | |
− | + | else | |
− | + | cout << 0; | |
− | + | } | |
− | + | cout << endl; | |
+ | } | ||
+ | break; | ||
+ | } | ||
+ | case 2: | ||
+ | { | ||
+ | set_figure(x,top); | ||
+ | if ((st+1) > maxst) | ||
+ | maxst = st + 1; | ||
+ | for (int i = 0; i < (n*n); i++) | ||
+ | if (a[i] == 0) | ||
+ | step(top,i,st+1); | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | // обратный ход | ||
+ | for (int i = xtop; i < top; i++) | ||
+ | { | ||
+ | if ((a[stak[i]] != -1) && (a[stak[i]] != -2)) | ||
+ | a[stak[i]]--; | ||
+ | else | ||
+ | //не забываем отметить,что фигура уже здесь стояла(чтобы избежать повторов) | ||
+ | if (a[stak[i]] == -1) | ||
+ | a[stak[i]] = -2; | ||
+ | // cerr << " Back " << stak[i] << endl; | ||
+ | } | ||
} | } | ||
− | int | + | int main() |
{ | { | ||
− | + | ||
+ | //cin >> n >> type >> variant; | ||
+ | n = 5; | ||
+ | type = 4; | ||
+ | variant = 1; | ||
+ | a = new int[n*n]; | ||
+ | stak = new int[n*n*4]; | ||
+ | |||
+ | for (int i = 0; i < (n*n); i++) | ||
{ | { | ||
− | + | for (int j = 0; j < (n*n); j++) | |
− | for ( | + | a[j] = 0; |
− | + | if (variant == 1) | |
− | + | cout << "__________________________________" << endl; | |
− | + | step(0,i,0); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | return | + | if (variant == 2) |
+ | cout << maxst; | ||
+ | return 0; | ||
} | } | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''[[Иванова Яна]]''' | |
− | + | ||
+ | '''Краткое описание алгоритма''': Функция, которая выполняет поиск расстановок, пытается поставить фигуру в каждую клетку. В случае неудачи программа отмечает клетки, в которых фигура уже побывала, но постановка не удалась, отрицательной величиной, равной по модулю шагу, на котором эта постановка была испробована. В случае пустой клетки она отмечается нулем, в случае успеха клетка отмечается положительным числом, равным шагу, соответствующему попытке постановки. | ||
+ | Также программа аналитически просчитывает максимальное количество фигур для каждого размера доски. | ||
+ | |||
+ | '''Инструкция''': В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей. Он вводит размер доски и тип фигуры. | ||
+ | Если он выбирает максимальное число расстановок, то программа выводит их количество, а также предлагает вывести все расстановки на экран. Другой вариант работы программы - вывод расстановок N фигур. | ||
+ | |||
+ | Посмотреть программу можно [http://tm.spbstu.ru/Файл:chess(1).zip здесь] | ||
− | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
− | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | #include <iostream> | |
− | } | + | #include <algorithm> |
− | + | #include <exception> | |
+ | #include <string> | ||
+ | #include <algorithm> | ||
+ | |||
+ | //пусть для определенности максимальный размер доски - 128 клеток | ||
+ | #define MAX_SIZE 128 | ||
+ | |||
+ | // перечисление для определения типа фигуры | ||
+ | enum figure_type | ||
+ | { | ||
+ | KING, | ||
+ | QUEEN, | ||
+ | ROOK, | ||
+ | BISHOP, | ||
+ | KNIGHT | ||
+ | }; | ||
+ | |||
+ | // класс для создания доски и расстановки фигур | ||
+ | class chess_board | ||
+ | { | ||
+ | public: | ||
+ | // конструктор (принимает только размеры) | ||
+ | chess_board(const int &size) | ||
{ | { | ||
− | if ( | + | if (size >= 0 && size <= MAX_SIZE) |
+ | { | ||
+ | size_ = size; | ||
+ | clean_board(); | ||
+ | } | ||
+ | |||
+ | else | ||
{ | { | ||
− | cout<<" | + | std::cout << "wrong size" << std::endl; |
− | + | throw std::string("wrong size"); | |
− | + | } | |
− | + | } | |
− | + | ||
− | + | ||
− | + | // функция очистки доски (занулить все клетки) | |
− | + | void clean_board() | |
− | + | { | |
− | + | //обнулить счетчик количества фигур на доске | |
− | + | figures_on_board_ = 0; | |
− | + | //присвоить всем клеткам значение 0 | |
− | + | for (int i = 0; i < size_; ++i) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | for (int j = 0; j < size_; ++j) | |
− | for (int | ||
{ | { | ||
− | + | board_[i][j] = 0; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
} | } | ||
− | |||
} | } | ||
− | + | ||
+ | // функция, принимающая размер доски | ||
+ | int get_size() | ||
{ | { | ||
− | if ( | + | return size_; |
+ | } | ||
+ | // функция, обновляющая количество фигур на доске | ||
+ | int get_figures_number() | ||
+ | { | ||
+ | return figures_on_board_; | ||
+ | } | ||
+ | |||
+ | //функция, пытающаяся поставить фигуру на свободное место и возвращающая | ||
+ | //истину в случае успеха и ложь в случае неудачи | ||
+ | bool put_figure (const figure_type& figure, const int& x, const int& y, const int& step) | ||
+ | { | ||
+ | if (board_[x][y] > 0 || board_[x][y] < -step) | ||
{ | { | ||
− | + | //если здесь уже стоит фигура или мы когда-то пытались ее сюда поставить, вернуть ложь | |
− | + | return false; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if (check_figure(figure, x, y)) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | board_[x][y] = step; | |
− | + | ++figures_on_board_; | |
− | + | return true; | |
− | + | } | |
− | + | else | |
− | + | { | |
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | |||
} | } | ||
− | + | ||
+ | //отметить клетку как ранее пройденную функцией | ||
+ | //вычесть единицу из количества фигур на доске | ||
+ | void remove_figure(const int& x, const int& y) | ||
+ | { | ||
+ | board_[x][y] *= -1; | ||
+ | --figures_on_board_; | ||
+ | } | ||
+ | |||
+ | //функция печати доски на экран | ||
+ | void print() const | ||
{ | { | ||
− | + | using namespace std; | |
+ | cout << "==========================================" << endl; | ||
+ | for (int i = 0; i < size_; ++i) | ||
{ | { | ||
− | + | for (int j = 0; j < size_; ++j) | |
− | |||
− | |||
{ | { | ||
− | + | //если фигура стоит в клетке, то вывести "*", если нет - вывести "-" | |
− | + | cout << (board_[i][j] > 0?"*":"-") << " "; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | cout << endl; | ||
} | } | ||
− | + | cout << "==========================================" << endl; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | ||
+ | private: | ||
+ | |||
+ | //функция, проверяющая возможность или невозможность постановки фигуры на данную клетку | ||
+ | bool check_figure(const figure_type& figure, const int& x, const int& y) | ||
{ | { | ||
− | + | //выбор следующего действия в зависимости от типа фигуры | |
+ | switch (figure) | ||
+ | { | ||
+ | case KING: | ||
+ | return check_king(x, y); | ||
+ | case QUEEN: | ||
+ | return check_queen(x, y); | ||
+ | case ROOK: | ||
+ | return check_rook(x, y); | ||
+ | case BISHOP: | ||
+ | return check_bishop(x, y); | ||
+ | case KNIGHT: | ||
+ | return check_knight(x, y); | ||
+ | //в случае ошибки ввода вернуть ложь | ||
+ | default: | ||
+ | return false; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | //поиск расстановок короля | ||
+ | bool check_king(const int& x, const int& y) | ||
+ | { | ||
+ | int min_x = std::max(x - 1, 0); | ||
+ | int max_x = std::min(x + 1, size_ - 1); | ||
+ | int min_y = std::max(y - 1, 0); | ||
+ | int max_y = std::min(y + 1, size_ - 1); | ||
+ | |||
+ | for (int i = min_x; i <= max_x; ++i) | ||
{ | { | ||
− | + | for (int j = min_y; j <= max_y; ++j) | |
− | |||
− | |||
{ | { | ||
− | + | if (board_[i][j] > 0) | |
{ | { | ||
− | + | return false; | |
− | |||
} | } | ||
} | } | ||
− | + | } | |
+ | return true; | ||
+ | } | ||
+ | |||
+ | //поиск расстановок ладьи | ||
+ | bool check_rook(const int& x, const int& y) | ||
+ | { | ||
+ | for (int i = 0; i < size_; ++i) | ||
+ | { | ||
+ | if (board_[i][y] > 0) | ||
{ | { | ||
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
} | } | ||
− | + | for (int j = 0; j < size_; ++j) | |
{ | { | ||
− | + | if (board_[x][j] > 0) | |
− | |||
{ | { | ||
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
} | } | ||
− | + | return true; | |
} | } | ||
− | + | ||
+ | //поиск расстановок слона | ||
+ | bool check_bishop(const int& x, const int& y) | ||
{ | { | ||
− | + | bool check = true; | |
− | |||
− | |||
− | |||
+ | int k_start_1 = -std::min(x, y); | ||
+ | int k_end_1 = std::min( size_ - x, size_ - y) - 1; | ||
− | + | int k_start_2 = -std::min( x, size_ - y - 1); | |
− | + | int k_end_2 = std::min( y, size_ - x - 1); | |
− | |||
− | |||
− | |||
− | + | for (int k = k_start_1; k <= k_end_1; ++k) | |
+ | { | ||
+ | check = check_coord(x + k, y + k) && check ; | ||
+ | } | ||
+ | for (int k = k_start_2; k <= k_end_2; ++k) | ||
+ | { | ||
+ | check = check_coord(x + k, y - k) && check; | ||
+ | } | ||
− | + | return check; | |
+ | } | ||
− | |||
− | + | //поиск расстановок коня | |
+ | bool check_knight(const int& x, const int& y) | ||
+ | { | ||
+ | bool check = | ||
+ | check_coord(x - 2, y - 1) && | ||
+ | check_coord(x - 2, y + 1) && | ||
+ | check_coord(x - 1, y - 2) && | ||
+ | check_coord(x - 1, y + 2) && | ||
+ | check_coord(x + 1, y - 2) && | ||
+ | check_coord(x + 1, y + 2) && | ||
+ | check_coord(x + 2, y - 1) && | ||
+ | check_coord(x + 2, y + 1); | ||
+ | return check; | ||
+ | } | ||
− | + | //поиск расстановок королевы | |
+ | bool check_queen(const int& x, const int& y) | ||
+ | { | ||
+ | return check_rook(x, y) && check_bishop(x, y); | ||
+ | } | ||
− | + | //функция поиска расстановок, в случае, когда на доске что-то стоит, вернуть ложь | |
+ | //иначе поставить вернуть истину | ||
+ | bool check_coord(const int& x, const int& y) | ||
+ | { | ||
+ | if (x >= 0 && x < size_ && y >= 0 && y < size_) | ||
+ | { | ||
+ | if (board_[x][y] > 0) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | } | ||
+ | return true; | ||
+ | } | ||
− | + | // if board_[x][y] == 0 | |
+ | // клетка свободна | ||
+ | // if board_[x][y] == s | ||
+ | // фигура была поставлена на шаге S | ||
+ | // if board_[x][y] == -s | ||
+ | // клетка свободна, но была попытка поставить фигуру на шаге S | ||
+ | int board_[MAX_SIZE][MAX_SIZE]; | ||
+ | int size_; | ||
+ | int figures_on_board_; | ||
+ | }; | ||
− | + | //функция расчета максимума для любой доски в зависимости от типа фигуры | |
− | + | int get_max_figures (const figure_type& figure, const int& size) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | int | ||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | switch (figure) | |
− | |||
− | |||
{ | { | ||
− | + | case KING: | |
− | + | return (size + 1) / 2; | |
− | + | case QUEEN: | |
− | + | if (size <= 2) | |
− | return | + | { |
− | + | return 1; | |
− | } | + | } |
− | + | else if (size == 3) | |
− | + | { | |
− | + | return 2; | |
− | + | } | |
− | + | else | |
− | + | { | |
− | + | return size; | |
− | + | } | |
− | + | case ROOK: | |
− | + | return size; | |
− | + | case BISHOP: | |
− | + | if (size == 1) | |
− | + | { | |
− | + | return size; | |
− | + | } | |
+ | else | ||
+ | { | ||
+ | return 2 * (size - 1); | ||
+ | } | ||
+ | case KNIGHT: | ||
+ | if (size <= 2) | ||
+ | { | ||
+ | return size * size; | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | return (size * size + 1) / 2; | ||
+ | } | ||
+ | default: | ||
+ | return 1; | ||
} | } | ||
− | |||
− | |||
− | |||
} | } | ||
− | void | + | //функция для расстановки максимального числа фигур на доске |
+ | void place_figures_for_max(chess_board &board, const figure_type& figure, const int& max_figures, int step) | ||
{ | { | ||
− | + | ++step; | |
− | + | const int size = board.get_size(); | |
− | for (int | + | for (int i = 0; i < size; ++i) |
{ | { | ||
− | for(int | + | for (int j = 0; j < size; ++j) |
{ | { | ||
− | + | //если мы можем поставить фигуру, то добавляем к максимуму единицу и запускаем цикл снова | |
+ | if (board.put_figure(figure, i, j, step)) | ||
+ | { | ||
+ | //если число фигур на доске достигло максимума, то вывести доску | ||
+ | if (board.get_figures_number() == max_figures) | ||
+ | { | ||
+ | board.print(); | ||
+ | } | ||
+ | //если число фигур не достигло максимума, продолжить выполнение функции | ||
+ | else | ||
+ | { | ||
+ | place_figures_for_max(board, figure, max_figures, step); | ||
+ | } | ||
+ | board.remove_figure(i, j); | ||
+ | } | ||
} | } | ||
− | |||
} | } | ||
− | |||
− | |||
} | } | ||
− | // | + | //функция, принимающая ввод с клавиатуры как строковый тип данных |
− | + | figure_type get_figure_type(const std::string& str) | |
{ | { | ||
+ | using namespace std; | ||
− | + | figure_type figure; | |
+ | if (str == string("king")) | ||
{ | { | ||
− | if( | + | figure = KING;} |
− | { | + | else if (str == string("queen")) |
− | + | { | |
− | } | + | figure = QUEEN;} |
+ | else if (str == string("rook")) | ||
+ | { | ||
+ | figure = ROOK; | ||
+ | } | ||
+ | else if (str == string("bishop")) | ||
+ | { | ||
+ | figure = BISHOP; | ||
+ | } | ||
+ | else if (str == string("knight")) | ||
+ | { | ||
+ | figure = KNIGHT; | ||
} | } | ||
− | + | //вывести ошибку в случае неверного ввода | |
− | + | else | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | cout << "wrong figure type" << endl; | |
− | + | throw string("wrong figure type"); | |
− | |||
− | |||
} | } | ||
− | return | + | return figure; |
− | |||
} | } | ||
− | + | int main() | |
− | |||
{ | { | ||
+ | //использовать стандартное пространств имен | ||
+ | using namespace std; | ||
+ | |||
+ | int size; | ||
+ | string type_of_figure; | ||
+ | string type_of_action; | ||
+ | figure_type figure; | ||
+ | |||
+ | cout << "Возможные фигуры: king, queen, rook, bishop, knight" << endl; | ||
+ | cout << "Возможные действия: max, placing" << endl; | ||
+ | cout << "----------------------------------------------------" << endl; | ||
+ | |||
+ | cout <<"Введите размер доски: "; | ||
+ | cin >> size; | ||
+ | chess_board board(size); | ||
+ | |||
+ | cout << "Введите тип фигуры: "; | ||
+ | cin >> type_of_figure; | ||
+ | figure = get_figure_type(type_of_figure); | ||
+ | |||
+ | cout << "Введите необходимое действие: "; | ||
+ | cin >> type_of_action; | ||
− | + | if (type_of_action == string("max")) | |
{ | { | ||
− | + | ||
+ | int max_figures = get_max_figures(figure, size); | ||
+ | cout << "Max figures: " << max_figures << endl; | ||
+ | |||
+ | cout << "Хотите ли вы просмотреть все варианты? (yes/no) "; | ||
+ | string answer; | ||
+ | cin >> answer; | ||
+ | //если нужно вывести все расстановки, то применить непосредственно функцию поиска расстановок максимума | ||
+ | if (answer == string("yes")) | ||
{ | { | ||
− | + | int step = 0; | |
+ | place_figures_for_max(board, figure, max_figures, step); | ||
} | } | ||
} | } | ||
− | + | //иначе если нужно расставить определенное количество фигур, то применить функцию поиска расстановок | |
− | + | //относительно введенного числа | |
+ | else if (type_of_action == string("placing")) | ||
{ | { | ||
− | + | int figures_to_place; | |
− | + | cout << "Сколько фигур нужно расставить: "; | |
− | + | cin >> figures_to_place; | |
− | |||
− | |||
− | + | int step = 0; | |
− | + | place_figures_for_max(board, figure, figures_to_place, step); | |
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | //иначе вывести ошибку действия | |
− | + | else | |
{ | { | ||
− | + | cout << "wrong type of action" << endl; | |
− | + | throw string("wrong type of action"); | |
− | |||
− | |||
} | } | ||
− | + | return 0; | |
− | |||
} | } | ||
− | |||
− | |||
− | |||
− | + | </syntaxhighlight> | |
− | + | </div> | |
− | |||
− | |||
− | + | '''[[Андреева Полина]]''' | |
− | + | '''Краткое описание алгоритма''':если шахматную доску представить в виде одной строчки(вторую поставить следом за первой, третью за второй и тд), то получится двоичное число. Максимальное число которое может получиться если 111...111 перевести в десятичное ,это число М*М. Тогда абсолютно ВСЕ варианты расстановки фигур это двоичные записи чисел от 0 до М*М. В программе есть цикл, который рассматривает каждый вариант для числа от 0 до М*М, переводит его в двоичную форму. Программа рассматривает каждую клетку, где стоит фигура. Если эта фигура бьет других, то цикл прерывается, нам такой вариант не подходит. Если никакая фигура не бьет никакую другую, то идет подсчет количества фигур на доске. Если фигур столько, сколько нужно, то вывод на экран. | |
− | + | '''Инструкция''': На экране показано соответствие каждому номеру типа фигуры. Пользователь выбирает тип фигуры, испольуя номер. Дальше нужно ввести размер доски. Затем на экране появляется два варианта количества фигур на доске: максимальное или введенное пользователем. Пользователь выбирает вариант. Если второй, то затем надо будет ввести количество фигур. | |
− | + | [http://tm.spbstu.ru/Файл:ШахматыАП.rar Программа] | |
− | /// | ||
− | |||
− | |||
− | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
− | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
+ | #include <cstring> | ||
+ | #include <iostream> | ||
+ | #include"math.h" | ||
+ | #include <fstream> | ||
+ | using namespace std; | ||
− | + | int M, N; // M-размер доски, N-коичество шахмат. | |
− | + | int sum;//нужно в процессе для подсчета количества шахмат | |
− | + | int **ChessBoard= new int* [M]; | |
− | |||
− | + | void ChessBoards(int k) //создание доски, k-число, которое переводим в двоичную запись, чтобы отобразить на доске расстановку фигур, 1-фигура есть, 0-нет. | |
− | + | { | |
− | + | for (int i=0; i<M; i++) //создание массива | |
− | + | { | |
− | + | ChessBoard[i] = new int[M]; | |
+ | } | ||
+ | for (int x=(M-1); x>=0; x=x-1)//заполнение массива фигурами (переводя k в двоичную форму) | ||
+ | { | ||
+ | for (int y=(M-1); y>=0; y=y-1) | ||
+ | { | ||
+ | ChessBoard[x][y]=(k%2); | ||
+ | k=k/2; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | void print (char filename[] ) ///создание функции вывода массива в файл | ||
+ | { | ||
+ | ofstream fout(filename, ios::app); | ||
− | + | for (int x=0; x<M; ++x) | |
+ | { | ||
+ | for(int y=0; y<M; ++y) | ||
{ | { | ||
− | + | fout << ChessBoard[x][y]<<" "; ///вывод массива в файл | |
− | |||
} | } | ||
− | + | fout <<'\n'; | |
− | |||
} | } | ||
+ | fout <<"\n\n"; | ||
+ | fout.close(); | ||
} | } | ||
− | |||
− | bool | + | |
+ | bool CheckHorse(int x, int y)//проверка для коня в клетке с номером x, y | ||
{ | { | ||
− | if ( | + | if (((x+1)<M) && ((y+2)<M) && (ChessBoard[x+1][y+2]==1))//если в клетке, куда может сходить конь (х+1,у+2) уже есть фигура, то этот вариант не подходит, так как один конь бьет другого. |
− | + | { | |
− | + | return false; | |
− | |||
− | + | } | |
+ | else if (((x+1)<M ) && ((y-2)>=0) && (ChessBoard[x+1][y-2]==1))//то же самое и в остальных случаях проверяем бьет ли один конь другого. | ||
+ | { | ||
+ | return false; | ||
− | } | + | } |
− | + | else if (((x-1)>=0) && ((y+2)<M) && (ChessBoard[x-1][y+2]==1)) | |
− | + | { | |
− | + | return false; | |
− | + | } | |
− | + | else if (((x-1)>=0) && ((y-2)>=0) && (ChessBoard[x-1][y-2]==1)) | |
− | { | + | { |
− | + | return false; | |
− | + | } | |
+ | else if (((x+2)<M) && ((y+1)<M) && (ChessBoard[x+2][y+1]==1)) | ||
{ | { | ||
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | else if (((x+2)<M ) && ((y-1)>=0) && (ChessBoard[x+2][y-1]==1)) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | if ( | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | return false; | |
− | |||
} | } | ||
− | + | else if (((x-2)>=0 ) && ((y+1)<M) && (ChessBoard[x-2][y+1]==1)) | |
− | else | ||
{ | { | ||
− | + | return false; | |
− | |||
} | } | ||
− | + | else if (((x-2)>=0 ) && ((y-1)>=0) && (ChessBoard[x-2][y-1]==1)) | |
− | |||
− | |||
{ | { | ||
− | + | return false; | |
− | + | } | |
− | + | else //в итоге, если конь, стоящий в данной клетке никого не бьет, то этот вариант подходит | |
− | + | { | |
− | + | return true; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | |||
} | } | ||
− | /// | + | int Horse(int k)//k-то число которое нужно будет перевести в двоичную форму, это делается в main'е |
− | + | //в этой функции считаем количество фигур, если он равно введенному или максимальному,то доска подходит и выводится в файл (все это в main'е) | |
{ | { | ||
− | + | for (int x=0; x<M; x++) | |
+ | { | ||
+ | int y; | ||
+ | for (y=0; y<M; y++) | ||
+ | { | ||
+ | if (ChessBoard[x][y]==1)//если в данной клетке стоит конь, то нужно проверить, | ||
+ | // бьет оно кого-то или нет... | ||
+ | //если в клетке нет коня, то ее проверять не нужно | ||
+ | { | ||
+ | if (CheckHorse(x,y))//...делаем это с помощью этой функции,если конь в данной клетке х;у | ||
+ | //никого не бьет, то прибавляем 1 к количеству шахмат на доске и считаем дальше | ||
+ | { | ||
+ | sum=sum+1; | ||
+ | } | ||
+ | else //а если бьет, то выходим из цикла, на данной этапе выйдем только из внуреннего | ||
+ | { | ||
+ | sum=0;//количество фигур обнуляем | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | if (y<M)//если из внутреннего цикла вышли раньше, значит у досчитался не до конца, | ||
+ | //то есть он меньше своего максимального значения М | ||
+ | { | ||
+ | |||
+ | break;//тогда выходим и из внешнего цикла | ||
+ | } | ||
+ | } | ||
+ | return sum; //возвращаем количество фигур | ||
} | } | ||
− | + | bool CheckKing(int x, int y) //все то же самое для проверки короля, стоящего в клетке х,у | |
− | bool | ||
{ | { | ||
− | + | if (((x+1)<M) && ((y+1)<M) && (ChessBoard[x+1][y+1])==1)//если в клетке куда может сходить король | |
+ | //уже есть фигура, то клетка не подходит и т.д | ||
{ | { | ||
− | + | return false; | |
− | + | ||
− | |||
− | |||
− | |||
} | } | ||
+ | else if (((x+1)<M ) && (ChessBoard[x+1][y]==1)) | ||
+ | { | ||
+ | return false; | ||
− | return true; | + | } |
− | + | else if (((x+1)<M) && ((y-1)>=0) && (ChessBoard[x+1][y-1]==1)) | |
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | else if (((x-1)>=0) && ((y-1)>=0) && (ChessBoard[x-1][y-1]==1)) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | else if (((x-1)>=0) && ((y+1)<M) && (ChessBoard[x-1][y+1]==1)) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | else if (((x-1)>=0) && (ChessBoard[x-1][y]==1)) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | else if (((y+1)<M) && (ChessBoard[x][y+1]==1)) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | else if (((y-1)>=0) && (ChessBoard[x][y-1]==1)) | ||
+ | { | ||
+ | return false; | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | return true; | ||
+ | } | ||
} | } | ||
− | // | + | int King(int k) //так же как и для коня, проверяем каждую клетку |
− | // | + | //подходит-прибавляем к количеству фигур sum единичку, нет-обнуляем сумму и выходим из цикла |
− | |||
− | |||
{ | { | ||
− | + | for (int x=0; x<M; x++) | |
− | |||
{ | { | ||
− | + | int y; | |
− | + | for (y=0; y<M; y++) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | if (ChessBoard[x][y]==1) | |
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | if (CheckKing(x,y)) | |
− | + | { | |
+ | sum=sum+1; | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | sum=0; | ||
+ | break; | ||
+ | } | ||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | if (y<M) | |
+ | { | ||
+ | break; | ||
+ | } | ||
} | } | ||
− | + | return sum; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | int CheckQueen(int x, int y)///проверка для королевы, принцип тот же, королева стит в клеке x,y | |
− | + | ///1 значит как true в bool (как в коне или короле), 0 - false | |
− | + | { int returnn=1;//начала true, дальше если будет false, то return примет значение 0, а если все пдходит | |
− | + | ///то так и стается 1 | |
− | + | int m; | |
− | + | for (m=1; m<M; m++) | |
− | + | { //проверяем для диагоналей | |
− | + | ///если по диагонале клетки х,у стоит еще королва, то такой вариант не подходит, выходим из цикла | |
− | + | ///разбито на 4 услвия, так как если не разбивать, то клетка в кторой стоит данная королева | |
− | + | ///тоже будет считаться и выходить из цикла | |
− | + | if (((x+m)<M)&&((y+m)<M)) | |
− | + | { | |
− | /// | + | if (ChessBoard[x+m][y+m]==1) |
− | + | {returnn=0; | |
− | + | break; | |
− | { | + | } |
− | + | } | |
− | + | if (((x-m)>=0)&&((y+m)<M)) | |
− | + | { | |
− | + | if (ChessBoard[x-m][y+m]==1) | |
− | + | {returnn=0; | |
− | + | break;} | |
− | + | } | |
− | + | if (((x+m)<M)&&((y-m)>=0)) | |
− | + | { | |
− | + | if (ChessBoard[x+m][y-m]==1) | |
− | + | {returnn=0; | |
− | + | break;} | |
− | + | } | |
− | + | if (((x-m)>=0)&&((y-m)>=0)) | |
− | + | { if (ChessBoard[x-m][y-m]==1) | |
− | + | {returnn=0; | |
− | + | break;} | |
− | + | } | |
− | + | if (m!=x) ///тут считаем по вертикали и горизонтали, так как длаем в цикле для m, то m меняется | |
− | + | ///и в какой-то момент может стать х, и тогда роверятьбуде клетку в которой стоит ДАННАЯ и выходить | |
− | + | ///это не нужно так что выходим только если m не равен x | |
− | + | { | |
− | if ( | + | if (ChessBoard[m][y]==1) //если по горизонтали есть какая-о клетка, где стоит королева, то выходим |
{ | { | ||
− | + | returnn=0; | |
− | + | break; | |
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | if (m!=y)//то же по вертикали | ||
+ | { | ||
+ | if (ChessBoard[x][m]==1) | ||
+ | { | ||
+ | returnn=0; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | return returnn; | ||
+ | } | ||
− | + | int Queen(int k)//тут также как и для коня и короля | |
− | + | { | |
− | + | for (int x=0; x<M; x++) | |
− | |||
{ | { | ||
− | + | int y; | |
− | for ( | + | for (y=0; y<M; y++) |
{ | { | ||
− | + | if (ChessBoard[x][y]==1)//если в клетке королева, проверяем подходи ли она нам | |
− | if( | ||
{ | { | ||
− | + | if (CheckQueen(x,y)) | |
− | |||
− | |||
− | |||
− | |||
− | if ( | ||
{ | { | ||
− | + | sum=sum+1; | |
− | |||
} | } | ||
− | + | else | |
− | + | { | |
− | + | sum=0; | |
− | + | break; | |
− | } | + | } |
− | + | } | |
} | } | ||
+ | if (y<M) | ||
+ | { | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | return sum; | ||
+ | } | ||
+ | |||
+ | int CheckRook(int x, int y)///ладья, просто берем ту часть из проверки королевы, где проверка по горизонтали и вертикали | ||
+ | { int returnn=1; | ||
+ | int m; | ||
+ | for (m=0; m<M; m++) | ||
+ | { | ||
+ | if (m!=x) | ||
+ | { | ||
+ | if (ChessBoard[m][y]==1) | ||
+ | { | ||
+ | returnn=0; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | if (m!=y) | ||
+ | { | ||
+ | if (ChessBoard[x][m]==1) | ||
+ | { | ||
+ | returnn=0; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
} | } | ||
+ | |||
+ | return returnn; | ||
} | } | ||
− | int | + | int Rook(int k)//все то же самое, количество фигур на доске |
{ | { | ||
− | + | for (int x=0; x<M; x++) | |
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | int y; | |
− | + | for (y=0; y<M; y++) | |
− | + | { | |
+ | if (ChessBoard[x][y]==1) | ||
+ | { | ||
+ | if (CheckRook(x,y)==1) | ||
+ | { | ||
+ | sum=sum+1; | ||
− | + | } | |
+ | else | ||
+ | { | ||
+ | sum=0; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | if (y<M) | ||
+ | { | ||
+ | break; | ||
+ | } | ||
+ | } | ||
− | + | return sum; | |
− | + | } | |
− | + | int CheckElephant(int x, int y)//для слона берем ту часть прроверки королевы, где по диагонали | |
− | + | { int returnn=1; | |
− | + | for (int i=1; i<M; i++) | |
− | + | { | |
− | + | if (((x+i)<M)&&((y+i)<M)) | |
− | + | { | |
− | + | if (ChessBoard[x+i][y+i]==1) | |
− | + | {returnn=0; | |
− | + | break; | |
− | + | } | |
− | + | } | |
+ | if (((x-i)>=0)&&((y+i)<M)) | ||
+ | { | ||
+ | if (ChessBoard[x-i][y+i]==1) | ||
+ | {returnn=0; | ||
+ | break;} | ||
+ | } | ||
+ | if (((x+i)<M)&&((y-i)>=0)) | ||
+ | {if (ChessBoard[x+i][y-i]==1) | ||
+ | {returnn=0; | ||
+ | break;} | ||
+ | } | ||
+ | if (((x-i)>=0)&&((y-i)>=0)) | ||
+ | { if (ChessBoard[x-i][y-i]==1) | ||
+ | {returnn=0; | ||
+ | break;} | ||
+ | } | ||
+ | } | ||
+ | return returnn; | ||
+ | } | ||
− | + | int Elephant(int k)///считаем кличесво фигур | |
− | + | { | |
+ | for (int x=0; x<M; x++) | ||
{ | { | ||
− | + | int y; | |
− | + | for (y=0; y<M; y++) | |
− | + | { | |
+ | if (ChessBoard[x][y]==1) | ||
+ | { | ||
+ | if (CheckElephant(x,y)) | ||
+ | { | ||
+ | sum=sum+1; | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | sum=0; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | if (y<M) | ||
+ | { | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | return sum; | ||
+ | } | ||
+ | |||
+ | int main () | ||
+ | { | ||
+ | ofstream MyFile("MyFile", ios::trunc); | ||
+ | MyFile.close(); // очищаем файл, чтоб при новой записи не было из рошлого запуска | ||
− | /// | + | int figure, z; |
− | if ( | + | cout<<"enter a figure 1-queen, 2-king, 3-rook , 4-horse or 5-elephant "; |
+ | cin>>figure;///тип фигуры, 1 - королевА, 2-король,3-ладья,4-конь,6-слон | ||
+ | cout << "\n enter a size of a board M - even number ";///ввести ЧЕТНЫЙ размер доски М | ||
+ | cin >> M; | ||
+ | if ( M%2 != 0)///проверка М на четность, с помощью остатка от деления на 2 | ||
{ | { | ||
− | + | while (M%2 != 0) | |
− | + | { | |
− | + | cout<<" you need EVEN number, enter one more time "; | |
+ | cin>>M; | ||
+ | } | ||
} | } | ||
− | + | ||
+ | cout<<"\n choose 1- max amount or 2 - your amount of figures "; | ||
+ | cin>>z;///z-один из вариантов 1-максимаьное число фигур на доске,2-пользователь сам вводит | ||
+ | |||
+ | switch (figure)///выбираем фигуру | ||
{ | { | ||
− | + | case 1:///королева | |
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | for(int i = 0; i<2* | + | if (z==2)///пользоватеь сам вводит количество |
− | + | { | |
− | + | cout<<"\n enter an amount of figures "; | |
− | + | cin >> N;///ввести количество | |
− | + | if (N>M)///проверка на то, сможет ли такое количество уместиться на доске в правильном виде | |
− | + | { | |
− | + | while (N>M) | |
− | + | { | |
− | + | cout<<" too many figures, enter one more time "; | |
− | + | cin>>N; | |
− | + | } | |
− | + | } | |
− | + | ///вот ниже i- те числа которые нужно перевести в двоичную форму | |
+ | for (int i=0; i<=pow(2,(M*M)); i++)///каждый i-новый вариант расстановик фигур | ||
+ | { | ||
+ | sum=0; | ||
+ | int k=i; | ||
+ | ChessBoards(k); | ||
+ | if (Queen(k)==N)///если в данной варианте фигур столько. сколько ввел пользователь, то выводим | ||
+ | { | ||
+ | print("MyFile"); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | else ///вариант максимального числа фигур на доске | ||
+ | { ///так же как и в предыдущем пункте, только количество фигур N максимально, | ||
+ | /// в случае королевы оно равно размеру доски | ||
+ | N=M; | ||
+ | for (int i=0; i<=pow(2,(M*M)); i++) | ||
+ | { | ||
+ | sum=0; | ||
+ | int k=i; | ||
+ | ChessBoards(k); | ||
+ | if (Queen(k)==N) | ||
+ | { | ||
+ | print("MyFile"); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | break; | ||
} | } | ||
− | + | case 2:///то же самое для короля | |
− | + | { | |
− | + | if (z==2) | |
− | < | + | { |
− | + | cout<<"\n enter an amount of figures "; | |
− | + | cin >> N; | |
− | + | if ( N>(M*M)/4) | |
− | + | { | |
− | + | while (N>(M*M)/4) | |
− | + | { | |
− | + | cout<<" too many figures, enter one more time "; | |
− | + | cin>>N; | |
− | + | } | |
− | + | } | |
− | + | for (int i=0; i<=pow(2,(M*M)); i++) | |
− | + | { | |
− | + | sum=0; | |
− | + | int k=i; | |
− | + | ChessBoards(k); | |
− | + | if (King(k)==N) | |
− | + | { | |
− | + | print("MyFile"); | |
− | + | } | |
− | + | } | |
− | + | } | |
− | + | else | |
− | + | { | |
− | + | N=(M*M)/4; | |
− | + | for (int i=0; i<=pow(2,(M*M)); i++) | |
− | + | { | |
− | + | sum=0; | |
− | + | int k=i; | |
− | + | ChessBoards(k); | |
+ | if (King(k)==N) | ||
+ | { | ||
+ | print("MyFile"); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | break; | ||
+ | } | ||
+ | case 3:///для ладьи | ||
+ | { | ||
+ | if (z==2) | ||
+ | { | ||
+ | cout<<"\n enter an amount of figures "; | ||
+ | cin >> N; | ||
+ | if (N>M) | ||
+ | { | ||
+ | while (N>M) | ||
+ | { | ||
+ | cout<<" too many figures, enter one more time "; | ||
+ | cin>>N; | ||
+ | } | ||
+ | } | ||
− | + | for (int i=0; i<=pow(2,(M*M)); i++) | |
− | + | { | |
− | + | sum=0; | |
− | + | int k=i; | |
+ | ChessBoards(k); | ||
+ | if (Rook(k)==N) | ||
+ | { | ||
+ | print("MyFile"); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | N=M; | ||
+ | for (int i=0; i<=pow(2,(M*M)); i++) | ||
+ | { | ||
+ | sum=0; | ||
+ | int k=i; | ||
+ | ChessBoards(k); | ||
+ | if (Rook(k)==N) | ||
+ | { | ||
+ | print("MyFile"); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | break; | ||
+ | } | ||
+ | case 4:///конь | ||
+ | { | ||
+ | if (z==2) | ||
+ | { | ||
+ | cout<<"\n enter an amount of figures "; | ||
+ | cin >> N; | ||
+ | if (N>(M*M)/2) | ||
+ | { | ||
+ | while (N>(M*M)/2) | ||
+ | { | ||
+ | cout<<" too many figures, enter one more time "; | ||
+ | cin>>N; | ||
+ | } | ||
+ | } | ||
− | + | for (int i=0; i<=pow(2,(M*M)); i++) | |
− | < | + | { |
− | + | sum=0; | |
− | + | int k=i; | |
− | + | ChessBoards(k); | |
− | + | if (Horse(k)==N) | |
− | + | { | |
− | + | print("MyFile"); | |
− | + | } | |
− | + | } | |
− | + | } | |
− | + | else | |
− | |||
− | |||
− | { | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | { | ||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | N=(M*M)/2; | |
− | + | for (int i=0; i<=pow(2,(M*M)); i++) | |
− | + | { | |
− | + | sum=0; | |
− | + | int k=i; | |
− | + | ChessBoards(k); | |
− | + | if (Horse(k)==N) | |
− | + | { | |
+ | print("MyFile"); | ||
+ | } | ||
+ | } | ||
} | } | ||
+ | break; | ||
} | } | ||
− | + | case 5:///слон | |
− | |||
− | // | ||
− | |||
{ | { | ||
− | + | if (z==2) | |
− | |||
− | |||
− | |||
{ | { | ||
− | + | cout<<"\n enter an amount of figures "; | |
+ | cin >> N; | ||
+ | if (N>2*M-2) | ||
{ | { | ||
− | + | while (N>2*M-2) | |
+ | { | ||
+ | cout<<" too many figures, enter one more time "; | ||
+ | cin>>N; | ||
+ | } | ||
+ | } | ||
+ | for (int i=0; i<=pow(2,(M*M)); i++) | ||
+ | { | ||
+ | sum=0; | ||
+ | int k=i; | ||
+ | ChessBoards(k); | ||
+ | if (Elephant(k)==N) | ||
+ | { | ||
+ | print("MyFile"); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | N=2*M-2; | ||
+ | for (int i=0; i<=pow(2,(M*M)); i++) | ||
+ | { | ||
+ | sum=0; | ||
+ | int k=i; | ||
+ | ChessBoards(k); | ||
+ | if (Elephant(k)==N) | ||
+ | { | ||
+ | print("MyFile"); | ||
+ | } | ||
} | } | ||
} | } | ||
+ | break; | ||
} | } | ||
− | + | default : ///а это еси пользоватеь ввел цифру, которая не соответстует ни одной фигуре | |
− | // | ||
− | |||
{ | { | ||
− | + | cout<<"NOOOOO"; | |
− | + | break; | |
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | }; | ||
+ | |||
− | + | return 0; | |
− | // | + | } |
− | + | </syntaxhighlight> | |
− | + | </div> | |
− | + | ||
− | + | '''[[Бальцер Анастасия]]''' | |
− | |||
− | |||
− | |||
− | + | '''Краткое описание алгоритма''': Для каждой фигуры написана отдельная функция, выполняющая поиск расстановок. После выбора типа фигуры, соответствующая функция выполняет поиск возможных расстановок. Она проходя по строкам двумерного массива пытается поставить фигуру в каждую клетку. Проходя по массиву она маркирует клетки, ставит 0 (если клетка свободна), 1 (если клетка находится под ударом), 2 (если клетка занята). Программа аналитически считает максимальное количество фигур для заданного размера доски, возможное число расстановок для заданных типа фигуры, размера доски и количества фигур. | |
− | + | ||
− | + | '''Инструкция''': При запуске программы появляется меню, в котором каждому типу фигуры сопоставлен номер, с помощью которого пользователь и выбирает тип фигуры. Затем пользователю на выбор предлагается 2 режима работы программы: первый выводит число возможных расстановок на экран, а список возможных расстановок в отдельный файл (при этом пользователь дополнительно выбирает число фигур); второй выводит на экран максимальное число фигур выбранного типа, которые можно расставить на заданной доске. | |
− | + | ||
− | + | Посмотреть программу можно [http://tm.spbstu.ru/Файл:Расстановка.zip тут] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''[[Васильева Анастасия]]''' | |
− | + | '''Краткое описание алгоритма''': Доска представлена в виде динамического массива, по ходу программы, в зависимости от алгоритмов для разных фигур, функции заполняют доску числами 0-место свободно, 1-находится под ударом и 2-занято фигурой, потом массив преобразовывается к нормальному виду 0 и 1-фигура. Так программа прогоняет все возможные варианты расстановок. Также программа аналитически просчитывает максимальное количество фигур для каждого размера доски. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''Инструкция''': Сначала программа просит выбрать фигуру, с которой будем работать. Затем 2 варианта развития событий: 1 - вывод в файл всех расстановок, 2 - максимальное количество фигур. В зависимости от выбора, в первом случае еще нужно ввести количество фигур, и программа запишет в файл все возможные варианты и выведет на экран число расстановок, а во втором - на экране появится максимальное кол-во фигур. | |
− | + | Скачать можно [http://tm.spbstu.ru/Файл:Задача1.zip тут]. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''[[Белоусова Екатерина]]''' | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''Краткое описание алгоритма''': доска представлена в виде динамического массива, заполненного 1 и 0. 1-стоит фигура, 0-пустое место. Программа при помощи рекурсии вызывает функцию, которая ставит фигуру в пустую клетку и проверяет, находится ли эта фигура под ударом других. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''Инструкция''': пользователь вводит четный размер доски М*М, затем выбирает, какую фигуру он хочет расставить на этой доске, после чего ему предлагается выбрать количество фигур(в скобках указывается максимальное количество фигур, которые можно расставить на доске М*М).Программа выводит на экран всевозможные расстановки, пронумеровывая каждую, и сохраняет их в файл. | |
− | |||
− | |||
− | |||
− | + | Скачать можно [http://tm.spbstu.ru/Файл:задача_1.zip тут]. | |
− | |||
− | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
− | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
+ | #include <iostream> | ||
+ | #include <stdlib.h> | ||
+ | #include <stdio.h> | ||
+ | #include <string> | ||
+ | #include <cstring> | ||
+ | #include <fstream> | ||
+ | #include <locale.h> | ||
+ | #include<iomanip> | ||
+ | #include<math.h> | ||
+ | using namespace std; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | int n, figureID, figura, maxCount; /// n - размер доски, figureID - номер фигуры, figura - колическтво фигур, maxCount - максимальное возможное количество фигур | |
− | + | int results_count = 0; /// определяем тип и задаем начальное значение results_count(номер результата) | |
+ | int **mass; /// определяем двумерный массив | ||
+ | ///создаем массив размером n*n | ||
+ | int** create_mass(int n) | ||
+ | { | ||
− | + | int **mass = new int* [n]; | |
− | + | for (int a=0; a<n; ++a) | |
{ | { | ||
− | + | mass[a] = new int [n]; | |
− | + | memset((char*)mass[a],0,n*sizeof(int)); ///зануление массива | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | return mass; | |
− | + | ||
+ | } | ||
+ | |||
+ | ///функция вывода массива | ||
+ | void output_mass () | ||
+ | { | ||
+ | |||
+ | for (int a=0; a<n; ++a)///заполнение ячеек массива от 0 до n по горизонтали | ||
{ | { | ||
− | |||
− | |||
− | + | for(int b=0; b<n; ++b)///заполнение ячеек массива от 0 до n по вертикали | |
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | cout << mass[a][b]<<" "; ///вывод массива на экран | |
− | |||
− | |||
− | |||
} | } | ||
− | |||
− | |||
− | + | cout << '\n'; | |
− | + | ||
− | + | } | |
− | + | ||
− | / | + | cout << "Result #" << ++results_count <<"\n\n"; /// вывод номера результата |
− | + | ||
− | + | } | |
− | |||
− | |||
− | } | ||
− | // | + | void zapis (char Zapis[] ) ///функции записи решений в файл |
− | |||
{ | { | ||
− | + | ofstream fout(Zapis, ios::app);///запись в фаил "Zapis" | |
+ | |||
+ | for (int x=0; x<n; ++x)///заполнение ячеек массива от 0 до n по горизонтали | ||
{ | { | ||
− | + | for(int y=0; y<n; ++y)///заполнение ячеек массива от 0 до n по вертикали | |
− | + | { | |
− | + | fout<< mass[x][y]<<" "; ///вывод решений в файл | |
− | + | } | |
− | + | fout<<'\n'; | |
− | + | } | |
− | + | fout<<"\n\n"; | |
− | + | fout.close(); | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | } | ||
− | // | + | ///проверяем наличие фигуры в строке а |
− | + | bool isEmptyHorisontal(int a) | |
{ | { | ||
− | + | ||
− | + | for(int i=0; i<n; ++i)///создаем цикл от 0 до n | |
− | for (int i = 0; i < | ||
{ | { | ||
− | + | if(mass[a][i])///в каждой ячейке массива [a][i] | |
{ | { | ||
− | // | + | return false;///неверно |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
} | } | ||
+ | |||
+ | return true;///в остальных случаях верно | ||
+ | |||
} | } | ||
− | // | + | ///проверяем наличие фигур в столбце b |
− | + | bool isEmptyVertical(int b) | |
{ | { | ||
− | |||
− | + | for(int i=0; i<n; ++i)///создаем цикл от 0 до n | |
− | |||
{ | { | ||
− | + | if(mass[i][b])///в каждой ячейке массива [i][b] | |
− | + | { | |
− | + | return false;///неверно | |
− | + | } | |
− | |||
− | |||
− | |||
} | } | ||
− | + | ||
+ | return true;///в остальных случаях верно | ||
+ | |||
+ | } | ||
+ | |||
+ | ///проверяем наличие фигур на диагоналях | ||
+ | bool isEmptyDiagonales(int a, int b) | ||
+ | { | ||
+ | |||
+ | for(int i=1; a-i>=0 && b-i>=0; ++i)///диагональ влево-вверх | ||
{ | { | ||
− | + | if(mass[a-i][b-i])///в каждой ячейке массива [a-i][b-i] | |
+ | { | ||
+ | return false;///неверно | ||
+ | } | ||
} | } | ||
− | + | ||
+ | for(int i=1; a+i<n && b+i<n; ++i)///диагональ вправо-вниз | ||
{ | { | ||
− | + | if(mass[a+i][b+i])///в каждой ячейке массива [a+i][b+i] | |
+ | { | ||
+ | return false;///неверно | ||
+ | } | ||
} | } | ||
− | // | + | |
− | + | for(int i=1; a+i<n && b-i>=0; ++i)///диагональ влево-вниз | |
{ | { | ||
− | + | if(mass[a+i][b-i])///в каждой ячейке массива [a+i][b-i] | |
− | + | { | |
+ | return false;///неверно | ||
+ | } | ||
} | } | ||
− | + | for(int i=1; a-i>=0 && b+i<n; ++i)///диагональ вправо-вверх | |
− | + | { | |
− | + | if(mass[a-i][b+i])///в каждой ячейке массива [a-i][b+i] | |
− | + | { | |
− | { | + | return false;///неверно |
− | + | } | |
− | + | } | |
− | + | return true;///в остальных случаях верно | |
− | |||
− | |||
− | |||
− | + | } | |
− | |||
− | |||
− | + | ///проверяем наличие фигур по горизонтали, вертикали и диагоналям | |
− | + | bool tryQueen(int a, int b) | |
− | + | { | |
− | + | if (!isEmptyHorisontal(a) || !isEmptyVertical(b) || !isEmptyDiagonales(a,b))///если не выполняются эти условия, | |
− | + | ///т.е. постановка фигуры не удовлетворяет расстановке | |
− | + | ///по горизонтали, или по вертикали, или по диагонали | |
+ | return false;///неверно | ||
− | + | return true;///в остальных случаях верно | |
− | |||
− | + | } | |
− | |||
− | + | /// функция поиска результатов решений. | |
− | + | /// row - номер очередной строки в которую нужно поставить очередного ферзя. | |
+ | /// count - количество фигур, поставленое к данному моменту | ||
+ | void setQueen(int row, int count) | ||
+ | { | ||
+ | |||
+ | for(int column=0; column<n; ++column)///двигаемся по столбцу сверху вниз | ||
+ | { | ||
− | + | if(tryQueen(row, column))/// проверка, если поставить ферзя в ячейку [row][column], | |
− | + | ///будет ли он единственным в этих строке, столбце и диагоналях | |
− | |||
− | |||
− | |||
{ | { | ||
− | int | + | mass[row][column]=1; |
− | + | ||
+ | if(count+1==figura) /// нужное количество фигур поставлено | ||
+ | { | ||
+ | output_mass(); /// вызов функции вывода массива на экран | ||
+ | zapis("Zapis");///записываем в файл | ||
+ | } | ||
+ | |||
+ | else | ||
+ | { | ||
+ | for(int i = row + 1; i<n; i++)/// ставим следующего ферзя в одну из следующих строк | ||
+ | setQueen(i,count+1);///и повторяем цикл | ||
+ | } | ||
+ | |||
+ | mass[row][column]=0; | ||
+ | |||
} | } | ||
+ | |||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | bool tryRook(int a, int b)///проверка на наличие фигур по вертикали и горизонтали | ||
+ | { | ||
− | + | if (!isEmptyHorisontal(a) || !isEmptyVertical(b))///если не выполняются эти условия, | |
− | + | ///т.е. постановка фигуры не удовлетворяет расстановке | |
+ | ///по горизонтали, или по вертикали | ||
+ | return false;///неверно | ||
+ | return true;///в остальных случаях верно | ||
+ | } | ||
− | + | /// функция поиска результатов решений. | |
+ | /// row - номер очередной строки в которую нужно поставить очередную ладью | ||
+ | /// count - количество фигур, поставленое к данному моменту | ||
+ | void setRook(int row, int count) | ||
+ | { | ||
− | + | for(int column=0; column<n; ++column)///двигаемся по столбцу сверху вниз | |
+ | { | ||
− | + | if(tryRook(row, column))/// проверка, если поставить ладью в A[row][column], будет ли она единственной в этих строке и столбце | |
+ | { | ||
− | + | mass[row][column]=1; | |
− | + | if(count+1==figura) /// нужное количество фигур поставлено | |
+ | { | ||
+ | output_mass(); /// вызов функции вывода массива на экран | ||
+ | zapis("Zapis");///записываем в файл | ||
+ | } | ||
− | + | else | |
− | + | { | |
+ | for(int i = row + 1; i<n; i++)/// ставим следующую ладью в одну из следующих строк | ||
+ | setRook(i,count+1);///и повторяем цикл | ||
+ | } | ||
− | + | mass[row][column]=0; | |
− | + | } | |
− | + | } | |
− | + | } | |
− | + | bool tryElephant(int a, int b) ///проверка на наличие фигур по диагоналям. | |
+ | { | ||
− | + | if (!isEmptyDiagonales(a,b))///если не выполняется это условие, | |
+ | ///т.е. постановка фигуры не удовлетворяет расстановке по диагоналям | ||
+ | return false; | ||
− | + | return true; | |
− | + | } | |
− | + | /// функция поиска результатов решений. | |
− | + | /// diagonale - номер диагонали в которую нужно поставить очередного слона | |
− | + | /// count - количество фигур, поставленое к данному моменту | |
− | + | void setElephant(int diagonale, int count) | |
− | + | { | |
− | + | int a, b; /// опорная точка диагонали (крайняя левая) | |
− | + | if (diagonale < n)///если номер диагонали меньше n | |
+ | { | ||
+ | a = diagonale;///значению а присвоить значенье номера диагонали | ||
+ | b = 0;///значению b присвоить значение 0 | ||
+ | } | ||
− | + | else///иначе | |
− | { | + | { |
− | + | a = n-1;///значению а присвоить значение n-1 | |
− | + | b =(diagonale % n)+1;///значению b присвоить значение целого частного от деления номера диагонали на n прибавив к нему 1 | |
− | + | } | |
− | // | + | /// перебираем все "столбцы" текущей диагонали |
− | + | for(int dcolumn=0; a-dcolumn>=0 && b+dcolumn < n; ++dcolumn) | |
{ | { | ||
− | int | + | |
− | if ( | + | /// рассчёт координат клетки по координатам крайней точки диагонали и "столбца" в диагонали |
+ | int x = a-dcolumn; | ||
+ | int y = b+dcolumn; | ||
+ | |||
+ | if(tryElephant(x, y))/// проверка, если поставить слона в A[row][column], будет ли он единственным по диагоналям | ||
{ | { | ||
− | + | ||
− | + | mass[x][y]=1; | |
− | + | ||
+ | if(count+1==figura) /// нужное количество фигур поставлено | ||
+ | { | ||
+ | output_mass(); /// вызов функции вывода массива на экран | ||
+ | zapis("Zapis");///запись в файл | ||
+ | } | ||
+ | |||
+ | else | ||
+ | { | ||
+ | for(int i = diagonale + 1; i<2*n-1; i++)/// ставим следующего слона в одну из следующих диагоналей | ||
+ | setElephant(i,count+1);///и повторяем цикл | ||
+ | } | ||
+ | |||
+ | mass[x][y]=0; | ||
+ | |||
} | } | ||
+ | |||
} | } | ||
− | + | } | |
− | + | ||
− | + | /// проверка на наличие фигуры на позиции x,y | |
− | + | bool isFigure(int x, int y) | |
− | + | { | |
− | + | return 0 <= x && x < n && 0 <= y && y < n && mass[x][y]; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | + | ///проверка на наличие короля в квадрате 3 на 3 | |
− | + | bool tryKing(int a, int b) | |
− | + | { | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | // | + | for(int i = a-1; i <= a+1; i++)///для ячеек находящихся слева и справа от поставленного короля |
− | |||
{ | { | ||
− | int | + | for(int j = b-1; j <= b+1; j++)///для ячеек находящихся снизу и сверху от поставленного короля |
− | |||
{ | { | ||
− | + | if (isFigure(i,j))///если выполняется это условие | |
− | + | return false;///неверно | |
− | |||
} | } | ||
} | } | ||
− | // | + | return true;///в остальных случаях верно |
− | + | ||
+ | } | ||
+ | |||
+ | ///функция поиска результатов решений | ||
+ | /// count - количество фигур, поставленое к данному моменту | ||
+ | ///x,y - позиция, начиная с которой разрешено ставить фигуры (все предшествующие позиции уже точно определены) | ||
+ | void setKing(int count, int x, int y) | ||
+ | { | ||
+ | |||
+ | if(count==figura)///figura - количество фигур, вводимых пользователями. | ||
{ | { | ||
− | + | output_mass();/// вызов функции вывода массива на экран | |
− | + | zapis("Zapis");///записываем в файл | |
− | + | return; | |
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | if (x == n) /// строки закончились | |
− | if | + | return; |
+ | |||
+ | /// обрабатываем текущую строку | ||
+ | for (int j=y; j<n; ++j) | ||
{ | { | ||
− | + | ||
− | if ( | + | if(tryKing(x, j)) |
{ | { | ||
− | + | mass[x][j]=1; | |
− | + | /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки | |
− | + | int nextX = x, nextY = j+1; | |
− | + | ||
− | + | if (nextY == n)///если столбец последний | |
+ | { | ||
+ | nextY = 0;///идем сначала по столбцам | ||
+ | nextX++;///к строке прибавляем 1 | ||
+ | } | ||
+ | |||
+ | /// ставим следующего короля | ||
+ | setKing(count+1,nextX,nextY); | ||
+ | mass[x][j]=0; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | |||
} | } | ||
− | // | + | /// обрабатываем прямоугольник ниже текущей строки |
− | + | for(int i=x+1; i<n; ++i) | |
{ | { | ||
− | int | + | |
− | + | for (int j=0; j<n; ++j) | |
{ | { | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if(tryKing(i, j)) | |
− | { | + | { |
− | + | mass[i][j]=1; | |
− | + | /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки | |
− | + | int nextX = i, nextY = j+1; | |
− | + | ||
− | + | if (nextY == n)///если столбец последний | |
− | + | { | |
− | + | nextY = 0;///идем сначала по столбцам | |
− | + | nextX++;///к строке прибавляем 1 | |
+ | } | ||
+ | |||
+ | /// ставим следующего короля | ||
+ | setKing(count+1,nextX,nextY); | ||
+ | mass[i][j]=0; | ||
+ | |||
+ | } | ||
+ | |||
} | } | ||
+ | |||
} | } | ||
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | bool tryHorse(int a, int b) ///проверка на коней по всем направлениям | |
− | + | { | |
− | + | ||
− | + | if (isFigure(a-1,b-2) || isFigure(a-1,b+2) || isFigure(a+1,b-2) || isFigure(a+1,b+2) || isFigure(a-2,b-1) || isFigure(a-2,b+1) || isFigure(a+2,b-1) || isFigure(a+2,b+1)) | |
− | + | ///если выполняются эти условия, | |
− | + | ///т.е. фигара стоит на одной из этих позиций | |
− | + | return false;///неверно | |
− | + | ||
− | + | return true;///в остальных случаях верно | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | void | + | ///функция поиска результатов решений |
+ | /// count - количество фигур, поставленое к данному моменту. | ||
+ | void setHorse(int count, int x, int y) | ||
{ | { | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | if ( | + | if(count==figura)///figura - количество фигур, вводимых пользователями. |
{ | { | ||
− | + | output_mass();/// вызов функции вывода массива на экран | |
− | + | zapis("Zapis");///записываем в файл | |
− | + | return; | |
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | if | + | if (x == n)/// строки закончились |
+ | return; | ||
+ | |||
+ | /// обрабатываем текущую строку | ||
+ | for (int j=y; j<n; ++j) | ||
{ | { | ||
− | + | ||
− | if ( | + | if(tryHorse(x, j)) |
{ | { | ||
− | + | ||
− | + | mass[x][j]=1; | |
− | + | /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки | |
+ | int nextX = x, nextY = j+1; | ||
+ | |||
+ | if (nextY == n)///если столбец последний | ||
+ | { | ||
+ | nextY = 0;///идем сначала по столбцам | ||
+ | nextX++;///к строке прибавляем 1 | ||
+ | } | ||
+ | |||
+ | /// ставим следующего коня | ||
+ | setHorse(count+1,nextX,nextY); | ||
+ | mass[x][j]=0; | ||
+ | |||
} | } | ||
+ | |||
} | } | ||
− | + | /// обрабатываем прямоугольник ниже текущей строки | |
+ | for(int i=x+1; i<n; ++i) | ||
{ | { | ||
− | int | + | |
− | + | for (int j=0; j<n; ++j) | |
{ | { | ||
− | + | ||
− | + | if(tryHorse(i, j)) | |
− | + | { | |
+ | |||
+ | mass[i][j]=1; | ||
+ | /// смещаем разрешённую позицию на 1 вправо или в начало следующей строки | ||
+ | int nextX = i, nextY = j+1; | ||
+ | |||
+ | if (nextY == n)///если столбец последний | ||
+ | { | ||
+ | nextY = 0;///идем сначала по столбцам | ||
+ | nextX++;///к строке прибавляем 1 | ||
+ | } | ||
+ | |||
+ | setHorse(count+1,nextX,nextY); | ||
+ | mass[i][j]=0; | ||
+ | |||
+ | } | ||
+ | |||
} | } | ||
+ | |||
} | } | ||
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | int main() | |
− | + | { | |
− | + | setlocale(LC_ALL,"RUS"); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ofstream Zapis("Zapis", ios::trunc);///сохраняем в файл | |
− | + | Zapis.close(); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | do | |
{ | { | ||
− | + | cout << "Введите размер доски (четный): "; | |
− | + | cin >> n; ///ввод пользователем размера доски | |
− | + | }while (n%2 != 0); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | mass=create_mass(n); ///создаём двумерный массив | |
− | + | ||
− | + | cout<<"Queen-1, Rook-2, Elephant-3, King-4, Horse-5"<< endl; | |
− | + | cin >> figureID; ///выбор пользователем фигуры | |
− | |||
− | + | /// устанавливаем максимальное количество в зависимости от фигуры | |
− | + | if (figureID==1) | |
− | + | maxCount=n; | |
− | + | if (figureID==2) | |
− | + | maxCount=n; | |
− | + | if (figureID==3) | |
− | + | maxCount=2*n-2; | |
− | + | if (figureID==4) | |
+ | maxCount=(n*n)/4; | ||
+ | if (figureID==5) | ||
+ | maxCount=(n*n)/2; | ||
− | + | /// запрашиваем количество фигур | |
− | + | do | |
{ | { | ||
− | + | cout << "Введите количество фигур (максимальное количество - " << maxCount << "): "; | |
− | + | cin >> figura; | |
− | + | }while (figura>maxCount); | |
− | + | ||
− | + | /// запускаем перебор | |
− | } | + | if (figureID==1) |
− | + | { | |
+ | for(int i = 0; i<n; i++) | ||
+ | setQueen(i,0); | ||
+ | zapis("Zapis"); | ||
+ | } | ||
+ | if (figureID==2) | ||
+ | { | ||
+ | for(int i = 0; i<n; i++) | ||
+ | setRook(i,0); | ||
+ | zapis("Zapis"); | ||
+ | } | ||
+ | if (figureID==3) | ||
+ | { | ||
+ | for(int i = 0; i<2*n-1; i++) | ||
+ | setElephant(i,0); | ||
+ | zapis("Zapis"); | ||
} | } | ||
− | + | if (figureID==4) | |
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | setKing(0,0,0); | |
− | + | zapis("Zapis"); | |
− | + | } | |
− | + | if (figureID==5) | |
− | + | { | |
− | + | setHorse(0,0,0); | |
− | + | zapis("Zapis"); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | system("PAUSE"); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
− | + | '''[[Тимошенко Валентина]]''' | |
− | |||
− | |||
− | |||
− | |||
− | + | '''Краткое описание алгоритма''': доска представлена в виде динамического массива, при выводе на экран пустые клетки обозначаются точками, а клетки, заполненные фигурами, обозначаются буквами (каждая буква соответствует первой букве названия фигуры на английском языке). Для каждой фигуры написаны функции проверки на возможность установки фигуры и функции расстановки. Кроме того, программа аналитически считает максимальное количество фигур для доски заданного пользователем размера и, при наличии команды пользователя, выводит все возможные расстановки рассчитанного максимального количества фигур на экран. | |
− | + | ||
− | + | '''Инструкция''': при запуске программа предлагает пользователю ввести размер доски, при этом число должно быть четным (если же пользователь вводит нечетное число, программа предлагает ввести размер еще раз, и так до тех пор, пока не будет введено четное число). Далее пользователь выбирает режим работы программы - либо расстановка фигур, либо расчет максимального количества фигур. В режиме расстановки фигур программа предлагает выбрать тип фигуры, выводит максимальное число фигур для доски заданного размера и предлагает ввести желаемое число фигур для расстановки (если оно больше максимального, предлагается повторная попытка ввода). В режиме расчета максимального числа программа предлагает выбрать тип фигуры, выводит рассчитанное число и задает вопрос о необходимости вывода всех возможных расстановок максимального количества для данной фигуры. Оба режима работают (т.е. все запросы повторяются) до тех пор, пока пользователь не даст команду на завершение цикла. Кроме того, в программе есть возможность изменения размера доски после выхода из всех циклов. При положительном ответе пользователя и изменении размера доступны оба режима работы. | |
− | + | ||
− | + | Скачать можно [http://tm.spbstu.ru/Файл:Chessboard.zip здесь]. | |
− | + | ||
− | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
− | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
− | + | ||
− | + | #include <iostream> ///расстановка одинаковых шахматных фигур одного цвета на доске произвольного размера так, чтобы они друг друга не били | |
− | + | #include <cstring> | |
− | + | #include <cstdlib> | |
− | + | #include <ctime> | |
− | + | ||
− | + | using namespace std; | |
− | + | int result_count = 0; ///переменная, в которую закладывается номер варианта расстановки фигур | |
− | + | int N; ///то количество фигур для расстановки, которое задает пользователь | |
− | + | int **Board; ///двумерный массив для отображения шахматной доски | |
− | + | int M; /// размер шахматной доски | |
− | + | ||
− | + | ///Функция вывода доски | |
− | + | void showBoard(string F) ///данная функция отображает доску | |
− | + | { | |
− | + | for(int i = 0; i < M; ++i) /// цикл, прогоняющий значения по строкам | |
− | + | { | |
− | + | for(int j = 0; j < M; ++j) /// цикл, прогоняющий значения по столбцам | |
− | + | cout << ((Board[i][j]) ? F : "."); ///заполнение как строки, так и столбца символом, который обозначает позицию на шахматной доске | |
− | + | cout << endl; ///точка - если данная клетка пустая, буква - если в клетке стоит соответствующая фигура | |
− | + | } | |
− | + | cout << "Result # " << ++result_count << "\n\n"; ///вывод номера варианта расположения с последующим переходом на новую строку | |
− | + | return; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | ///Функции проверки и установки для ферзя | ||
− | + | bool tryQueen(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец | |
− | // | + | { |
− | for (int i = | + | for (int i = 0; i < M; ++i) ///проверка единственности ферзя в строке |
{ | { | ||
− | if ( | + | if(Board[a][i]) |
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | |||
− | int | + | for(int i = 0; i < M; ++i) ///проверка единственности ферзя в столбце |
− | + | { | |
+ | if(Board[i][b]) | ||
+ | return false; | ||
+ | } | ||
− | + | for(int i = 1; a-i >= 0 && b-i >= 0; ++i)///проверка единственности ферзя по диагонали влево-вверх | |
− | + | { | |
− | + | if(Board[a-i][b-i]) | |
− | + | return false; | |
− | + | } | |
− | |||
− | for (int i = | + | for(int i = 1; a+i < M && b+i < M; ++i)///проверка единственности ферзя по диагонали вправо-вниз |
{ | { | ||
− | + | if(Board[a+i][b+i]) | |
− | + | return false; | |
− | |||
− | |||
− | |||
} | } | ||
− | + | ||
− | + | for(int i = 1; a+i < M && b-i >= 0; ++i)///проверка единственности ферзя по диагонали влево-вниз | |
− | return | + | { |
+ | if(Board[a+i][b-i]) | ||
+ | return false; | ||
+ | } | ||
+ | |||
+ | for(int i = 1; a-i >= 0 && b+i < M; ++i)///проверка единственности ферзя по диагонали вправо-вверх | ||
+ | { | ||
+ | if(Board[a-i][b+i]) | ||
+ | return false; | ||
+ | } | ||
+ | |||
+ | return true; ///если в ходе проверки ферзей и угроз не обнаружилось, в данную клетку можно поставить фигуру | ||
} | } | ||
− | |||
− | |||
− | + | void setQueen(int a, int count) ///функция расстановки ферзей; a - очередная строка, count - счетчик количества фигур, которое необходимо расставить | |
+ | { | ||
+ | for(int b = 0; b < M; ++b) ///b - очередной столбец, расстановка идет по строкам | ||
+ | { | ||
+ | if(tryQueen(a, b)) ///проверка данной клетки на возможность установки фигуры | ||
+ | { | ||
+ | Board[a][b] = 1; ///установка ферзя в первую клетку поля, присваивание ей значения 1 (true) | ||
− | + | for(int i = a + 1; i < M; ++i) ///расстановка указанного пользователем количества фигур | |
+ | setQueen(i,count+1); | ||
− | + | if(count+1 == N) /// если нужное количество фигур поставлено, то | |
+ | showBoard("Q"); /// вызов функции вывода шахматной доски на экран | ||
− | + | Board[a][b]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку | |
+ | } | ||
+ | } | ||
+ | } | ||
− | + | ///Функции проверки и установки для ладьи | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | bool tryRook(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | for (int i = 0; i < M; ++i) ///проверка единственности ладьи в строке | |
− | + | { | |
− | + | if(Board[a][i]) | |
− | + | return false; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | } | ||
+ | for(int i = 0; i < M; ++i) ///проверка единственности ладьи в столбце | ||
+ | { | ||
+ | if(Board[i][b]) | ||
+ | return false; | ||
+ | } | ||
− | + | return true; ///если в ходе проверки ладей и угроз не обнаружилось, в данную клетку можно поставить фигуру | |
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | // | + | void setRook(int a, int count) ///функция расстановки ладей; a - очередная строка, count - счетчик количества фигур, которое необходимо расставить |
− | |||
{ | { | ||
− | + | for(int b = 0; b < M; ++b) ///b - очередной столбец, расстановка идет по строкам | |
− | + | { | |
− | + | if(tryRook(a, b)) ///проверка данной клетки на возможность установки фигуры | |
− | + | { | |
− | + | Board[a][b] = 1; ///установка ладьи в первую клетку, присваивание ей значения 1 (true) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | for(int i = a + 1; i < M; ++i) ///расстановка указанного пользователем количества фигур | |
− | + | setRook(i,count+1); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if(count+1 == N) /// если нужное количество фигур поставлено, то | |
− | + | showBoard("R"); /// вызов функции вывода шахматной доски на экран | |
− | + | ||
− | + | Board[a][b]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку | |
− | + | } | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | // | + | ///Функции проверки и установки для слона |
− | + | ||
+ | bool tryEl(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец | ||
{ | { | ||
− | + | for(int i = 1; a-i >= 0 && b-i >= 0; ++i)///проверка единственности слона по диагонали влево-вверх | |
− | + | { | |
− | + | if(Board[a-i][b-i]) | |
− | + | return false; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | + | for(int i = 1; a+i < M && b+i < M; ++i)///проверка единственности слона по диагонали вправо-вниз | |
− | + | { | |
− | + | if(Board[a+i][b+i]) | |
− | + | return false; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | for(int i = 1; a+i < M && b-i >= 0; ++i)///проверка единственности слона по диагонали влево-вниз | |
− | + | { | |
− | + | if(Board[a+i][b-i]) | |
− | + | return false; | |
− | + | } | |
− | |||
− | |||
− | |||
− | } | ||
− | + | for(int i = 1; a-i >= 0 && b+i < M; ++i)///проверка единственности слона по диагонали вправо-вверх | |
− | + | { | |
− | + | if(Board[a-i][b+i]) | |
− | + | return false; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | return true; ///если в ходе проверки слонов и угроз не обнаружилось, в данную клетку можно поставить фигуру | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | void setEl(int dia, int count) ///функция расстановки слонов; line - очередная строка, count - счетчик количества фигур, которое необходимо расставить | ||
+ | { | ||
+ | ///dia - очередная диагональ, которую нужно исследовать на наличие фигуры и угрозы | ||
+ | int a, b; ///клетка, с которой начинается расстановка, a- очередная строка, b- очередной столбец | ||
+ | if (dia < M) ///условие, что клеткa данной диагонали лежат на доске | ||
+ | { | ||
+ | a = dia; ///начало отсчёта диагоналей, цикл движется по строке | ||
+ | b = 0; ///обнуление переменной для столбца, цикл движется по столбцу | ||
+ | } | ||
+ | else ///если клеткa данной диагонали выходит за размер доски (когда цикл по строке доберется до конца | ||
+ | { | ||
+ | a = M-1; ///самая последняя диагональ | ||
+ | b =(dia % M)+1; ///соответственно расчёт переменной для столбца этой диагонали | ||
+ | } | ||
− | int | + | for(int i=0; a-i>=0 && b+i < M; ++i)/// цикл движется по строкам и столбцам снизу слева вправо вверх |
− | + | { | |
− | + | int line = a-i; ///строковая координата данной клетки диагонали | |
− | + | int column = b+i; ///столбцовая координата данной клетки диагонали | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if(tryEl(line, column))/// проверка на единственность слона по диагоналям | |
− | + | { | |
− | + | Board[line][column]=1; ///установка слона в первую клетку, присваивание ей значения 1 (true) | |
− | |||
− | + | for(int i = dia + 1; i<2*M-1; ++i) ///расстановка указанного пользователем количества фигур | |
− | + | setEl(i,count+1); | |
− | + | if(count+1 == N) /// если нужное количество фигур поставлено, то | |
+ | showBoard("E"); /// вызов функции вывода шахматной доски на экран | ||
+ | Board[line][column]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку | ||
+ | } | ||
+ | } | ||
+ | } | ||
− | + | ///Функции проверки и установки для коня | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | bool tryHorse(int a, int b) /// проверка на возможность поставить фигуру в данную клетку, a- очередная строка, b- очередной столбец | |
− | |||
{ | { | ||
− | + | ///проверка на наличие фигур и угроз во всех 8 точках, которые могут быть под ударом в квадрате 5х5 вокруг установленной фигуры | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if ((a-1) >=0 && (b-2)>=0 && Board[a-1][b-2]) | |
− | + | return false; | |
− | + | ||
− | + | if ((a-1)>=0 && (b+2) < M && Board[a-1][b+2]) | |
− | + | return false; | |
− | + | ||
− | + | if ((a+1) < M && (b-2) >=0 && Board[a+1][b-2]) | |
− | + | return false; | |
− | + | ||
− | + | if ((a+1) < M && (b+2) < M && Board[a+1][b+2]) | |
− | + | return false; | |
− | + | ||
− | + | if ((a-2) >=0 && (b-1) >=0 && Board[a-2][b-1]) | |
− | + | return false; | |
− | + | ||
+ | if ((a-2) >=0 && (b+1) < M && Board[a-2][b+1]) | ||
+ | return false; | ||
+ | |||
+ | if ((a+2) < M && (b-1) >= 0 && Board[a+2][b-1]) | ||
+ | return false; | ||
+ | |||
+ | if ((a+2) < M && (b+1) < M && Board[a+2][b+1]) | ||
+ | return false; | ||
+ | return true; ///если в ходе проверки коней и угроз не обнаружилось, в данную клетку можно поставить фигуру | ||
} | } | ||
− | + | void setHorse(int count, int a, int b) ///функция расстановки коней; a - очередная строка, b - очередной столбец, count - счетчик количества фигур, которое необходимо расставить | |
{ | { | ||
− | + | if(count==N) /// если нужное количество фигур поставлено, то | |
− | + | { | |
− | + | showBoard("H"); /// вызов функции вывода шахматной доски на экран | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if (a == M) ///условие необходимо; прогоняет алгоритм по всем строкам | |
+ | return; | ||
+ | for (int j=b; j<M; ++j) ///установка коней в первой строке | ||
+ | { | ||
+ | if(tryHorse(a, j)) ///проверка данной клетки на возможность установки фигуры | ||
+ | { | ||
+ | Board[a][j]=1; ///установка коня в первую клетку, присваивание ей значения 1 (true) | ||
+ | int line = a, b = j+1; ///смещение в строке на одну позицию вправо, переобозначение строки на line | ||
+ | if (b == M) ///если данный столбец - самый крайний | ||
+ | { | ||
+ | b = 0; ///обнуление переменной, чтобы использовать ее при заполнении следующей строки | ||
+ | line++; ///то переход на следующую строку и дальнейшее ее заполнение | ||
+ | } | ||
+ | setHorse(count+1,line,b); ///установка фигуры, увеличение счетчика | ||
+ | Board[a][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку | ||
+ | } | ||
+ | } | ||
+ | for(int i=a+1; i<M; ++i) ///дальнейшее заполнение оставшихся строк | ||
+ | { | ||
+ | for (int j=0; j<M; ++j) | ||
+ | { | ||
+ | if(tryHorse(i, j)) ///проверка данной клетки на возможность установки фигуры | ||
+ | { | ||
+ | Board[i][j]=1; ///установка коня в первую клетку, присваивание ей значения 1 (true) | ||
+ | int line = i, b = j+1; ///смещение в строке на одну позицию вправо | ||
− | + | if (b == M) ///если данный столбец - самый крайний | |
− | + | { | |
− | + | b = 0; | |
− | + | line++; ///то переход на следующую строку и дальнейшее ее заполнение | |
− | + | } | |
+ | setHorse(count+1,line,b); ///установка фигуры, увеличение счетчика | ||
+ | Board[i][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
− | + | ///для короля | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | bool | + | bool tryKing(int a, int b) /// проверка на возможность поставить фигуру в квадрате 3х3, a- очередная строка, b- очередной столбец |
{ | { | ||
− | + | ///проверка на наличие фигур и угроз во всех 8 точках, которые могут быть под ударом в квадрате 3х3 вокруг установленной фигуры | |
− | + | ||
− | + | for(int i = a-1; i <= a+1; ++i) ///проверка по строкам | |
− | + | { | |
− | + | for(int j = b-1; j <= b+1; ++j) ///проверка по столбцам | |
− | + | { | |
− | + | if (a>=0 && a < M && b>=0 && b < M && Board[a][b]) ///условие наличия клетки в пределах доски | |
− | + | return false; | |
− | + | ||
− | + | if ((a+1) < M && (b-1) >=0 && Board[a+1][b-1]) | |
− | + | return false; | |
− | + | ||
− | + | if ((a+1) < M && Board[a+1][b]) | |
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if ((a+1) < M && (b+1) < M && Board[a+1][b+1]) | |
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if ((b+1) < M && Board[a][b+1]) | |
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | + | if ((a-1)>=0 && (b+1) < M && Board[a-1][b+1]) | |
− | + | return false; | |
− | + | if ((a-1) >=0 && Board[a-1][b]) | |
− | + | return false; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if ((a-1) >=0 && (b-1)>=0 && Board[a-1][b-1]) | |
− | + | return false; | |
− | |||
+ | if ((b-1) >= 0 && Board[a][b-1]) | ||
+ | return false; | ||
+ | } | ||
+ | } | ||
− | + | return true; ///если в ходе проверки королей и угроз не обнаружилось, в данную клетку можно поставить фигуру | |
− | + | } | |
− | |||
− | + | void setKing (int count, int a, int b) ///функция расстановки коней; a - очередная строка, b - очередной столбец, count - счетчик количества фигур, которое необходимо расставить | |
− | + | { | |
− | + | for (int j=b; j<M; ++j) ///установка королей в первой строке | |
− | + | { | |
− | + | if(tryKing(a, j)) ///проверка данной клетки на возможность установки фигуры | |
− | + | { | |
− | + | Board[a][j]=1; ///проверка данной клетки на возможность установки фигуры | |
− | + | setKing(count+1,a,j); ///расстановка фигур в первой строке | |
− | + | Board[a][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку | |
− | + | } | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | for(int i=a+1; i<M; ++i) ///установка фигур в оставшуюся часть шахматной доски по строкам | |
− | + | { | |
− | + | for (int j=0; j<M; ++j) | |
− | + | { | |
− | { | + | if(tryKing(i, j)) ///проверка данной клетки на возможность установки фигуры |
− | + | { | |
− | + | Board[i][j]=1; ///проверка данной клетки на возможность установки фигуры | |
− | + | setKing(count+1,i,j); ///расстановка фигур | |
+ | Board[i][j]=0; ///обнуление переменной для установки следующей фигуры в следующую клетку | ||
+ | } | ||
+ | } | ||
+ | } | ||
− | + | if(count==N) /// если нужное количество фигур поставлено, то | |
− | + | { | |
− | + | showBoard("K");/// вызов функции вывода шахматной доски на экран | |
− | + | return; | |
− | + | } | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | + | int main() | |
− | + | { | |
− | + | char s; ///переменная, будет использована в цикле | |
− | + | do /// цикл, выводящий на экран данные в зависимости от введенных пользователем значений переменных | |
− | + | { | |
− | + | do ///цикл для считывания введенного пользователем размера доски | |
− | + | { | |
− | + | cout << "Input the size of the board: " << endl; ///ввод размера доски | |
− | + | cin >> M; | |
− | |||
− | |||
− | + | if ( (M%2) == 1) ///цикл, работающий только в том случае, если пользователь введет нечетное число | |
− | + | { | |
− | + | cout << '\n' << "The number must be even, so try to input the size again" << '\n' << endl; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | } | |
− | + | while (M%2 !=0); ///пока пользователь не введет допуcтимое число, цикл не прерывается | |
− | + | Board = new int*[M]; ///создание двумерного массива для отображения шахматной доски | |
− | + | for (int i = 0; i<M; i++) | |
− | < | + | Board[i] = new int[M]; ///создание первую строку доски |
− | </ | + | for (int i = 0; i<M; i++) |
+ | for (int j = 0; j<M; j++) | ||
+ | Board[i][j] = 0; ///зануление массива | ||
− | '' | + | int V; ///пользователь выбирает один из двух вариантов работы программы |
− | + | cout << '\n' << "Input your choice: 1=placing of figures, 2=for max amount of figures" << endl; | |
− | + | cin >> V; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if (V==1) ///цикл, расставляющий фигуры по введенным пользователем данным | |
− | + | { | |
− | + | char k; ///переменная, будет использована в цикле | |
− | '' | + | do /// цикл, выводящий на экран данные в зависимости от введенных пользователем значений переменных |
− | + | { | |
− | + | int T; ///пользователь выбирает фигуру | |
− | + | cout << '\n' << "Input type of figure: 1-queen, 2-king, 3-horse, 4-rook, 5-elephant"<< endl; | |
− | + | cin >> T; | |
− | |||
− | |||
− | + | int maximum; ///переменная, хранящая максимальное количество фигур, которое можно расставить на заданной доске | |
+ | if (T==1) ///максимальное количество фигур на заданной доске для ферзя | ||
+ | { | ||
+ | maximum=M; | ||
+ | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | ||
+ | } | ||
+ | if (T==2) ///максимальное количество фигур на заданной доске для короля | ||
+ | { | ||
+ | maximum=0.25*M*M; | ||
+ | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | ||
+ | } | ||
+ | if (T==3) ///максимальное количество фигур на заданной доске для коня | ||
+ | { | ||
+ | maximum=0.5*M*M; | ||
+ | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | ||
+ | } | ||
+ | if (T==4) ///максимальное количество фигур на заданной доске для ладьи | ||
+ | { | ||
+ | maximum=M; | ||
+ | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | ||
+ | } | ||
+ | if (T==5) ///максимальное количество фигур на заданной доске для слона | ||
+ | { | ||
+ | maximum=2*M-2; | ||
+ | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | ||
+ | } | ||
− | / | + | do ///цикл, считывающий количество фигур, заданное пользователем |
− | + | { | |
− | + | cout << "Input the amount of figures, it must be less than max amount or equals that" << endl; | |
− | + | cin >> N; | |
− | + | } | |
− | + | while (N>maximum); ///пока пользователь не введет допуcтимое число, цикл не прерывается | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl; | |
− | |||
− | + | if (T==1) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для ферзя | |
− | + | { | |
+ | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | ||
+ | for (int i=0; i <M; ++i) | ||
+ | setQueen(i,0); | ||
+ | } | ||
+ | if (T==2) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для короля | ||
+ | { | ||
+ | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | ||
+ | setKing(0,0,0); | ||
+ | } | ||
+ | if (T==3) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для коня | ||
+ | { | ||
+ | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | ||
+ | setHorse(0,0,0); | ||
+ | } | ||
+ | if (T==4) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для ладьи | ||
+ | { | ||
+ | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | ||
+ | for (int i=0; i <M; ++i) | ||
+ | setRook(i,0); | ||
+ | } | ||
+ | if (T==5) ///цикл, вызывающий на экран все варианты расстановки заданного пользователем числа фигур для слона | ||
+ | { | ||
+ | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | ||
+ | for(int i = 0; i<2*M-1; ++i) | ||
+ | setEl(i,0); | ||
+ | } | ||
− | + | cout << '\n' << "If you want continue placing figures, input +, if not, input -" << endl; | |
− | + | cin >> k; | |
+ | } | ||
+ | while (k != '-'); ///цикл работает до тех пор, пока пользователь не даст команду на его завершение | ||
+ | } | ||
− | + | else if (V==2) ///цикл, вычисляющий максимальное количество фигур по введенным пользователем данным | |
− | + | { | |
− | + | char z; ///переменная, будет использована в цикле | |
− | + | do /// цикл, выводящий на экран данные в зависимости от введенных пользователем значений переменных | |
− | + | { | |
+ | int T; ///переменная для выбора фигуры пользователем | ||
+ | cout << '\n' << "Input type of figure: 1-queen, 2-king, 3-horse, 4-rook, 5-elephant"<< endl; | ||
+ | cin >> T; | ||
+ | char d; ///переменная, будет использована в циклах | ||
+ | int maximum; ///переменная, хранящая максимальное количество фигур, которое можно расставить на заданной доске | ||
+ | if (T==1) ///максимальное количество фигур на заданной доске для ферзя | ||
+ | { | ||
+ | maximum=M; ///формула расчёта максимального количества фигур для заданной доски | ||
+ | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | ||
+ | cout << "If you want to see all locations of max amount, input +, if not, input -" << endl; | ||
+ | cin >> d; | ||
+ | cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl; | ||
+ | if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры | ||
+ | { | ||
+ | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | ||
+ | N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше | ||
+ | for (int i=0; i < M; ++i) | ||
+ | setQueen(i,0); | ||
+ | } | ||
− | + | } | |
− | + | if (T==2) ///максимальное количество фигур на заданной доске для короля | |
− | + | { | |
− | + | maximum=0.25*M*M; ///формула расчёта максимального количества фигур для заданной доски | |
− | + | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | |
− | + | cout << "If you want to see all locations of max amount, input +, if not, input -" << endl; | |
− | + | cin >> d; | |
− | + | cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl; | |
− | + | if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры | |
− | + | { | |
− | + | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | |
− | + | N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше | |
− | + | setKing(0,0,0); | |
− | + | } | |
− | + | } | |
− | + | if (T==3) ///максимальное количество фигур на заданной доске для коня | |
− | + | { | |
− | + | maximum=0.5*M*M; ///формула расчёта максимального количества фигур для заданной доски | |
− | + | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | |
− | + | cout << "If you want to see all locations of max amount, input +, if not, input -" << endl; | |
− | + | cin >> d; | |
− | + | cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl; | |
− | + | if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры | |
− | + | { | |
− | + | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | |
− | + | N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше | |
− | + | setHorse(0,0,0); | |
− | + | } | |
− | + | } | |
− | + | if (T==4) ///максимальное количество фигур на заданной доске для ладьи | |
− | + | { | |
− | + | maximum=M; ///формула расчёта максимального количества фигур для заданной доски | |
− | + | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | |
− | + | cout << "If you want to see all locations of max amount, input +, if not, input -" << endl; | |
− | + | cin >> d; | |
− | + | cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl; | |
− | + | if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры | |
− | + | { | |
− | + | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | |
− | + | N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше | |
− | + | for (int i=0; i <M; ++i) | |
− | + | setRook(i,0); | |
− | + | } | |
− | + | } | |
− | + | if (T==5) ///максимальное количество фигур на заданной доске для слона | |
− | + | { | |
− | + | maximum=2*M-2; ///формула расчёта максимального количества фигур для заданной доски | |
− | + | cout << '\n' << "Max amount of figures for this board = " << maximum << '\n' << endl; | |
− | + | cout << "If you want to see all locations of max amount, input +, if not, input -" << endl; | |
− | + | cin >> d; | |
− | + | cout << '\n' << "All possible variants for this amount of figures on this board:" << '\n' << endl; | |
− | + | if (d=='+') ///по выбору пользователя вывод всех возможных расстановок для максимального количества для данной фигуры | |
− | + | { | |
− | + | result_count=0; ///обнуление переменной, выводящей номер решения; необходимо при повторной работе цикла | |
− | + | N=maximum; ///приравниваем количество фигур для установки максимально возможному, рассчитанному по формуле выше | |
− | + | for(int i = 0; i<2*M-1; ++i) | |
− | + | setEl(i,0); | |
− | + | } | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | // | ||
− | < | ||
− | "'' | ||
− | < | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | // | ||
− | |||
− | |||
− | / | ||
− | // | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | } | ||
− | + | cout << '\n' << "If you want continue counting, input +, if not, input -" << '\n' << endl; | |
− | + | cin >> z; | |
− | + | } | |
− | + | while (z != '-'); ///цикл работает до тех пор, пока пользователь не даст команду на его завершение | |
− | + | } | |
− | + | cout << '\n' << "If you want to change the size of board, input +, if not, input -" << endl; | |
− | + | cin >> s; | |
− | + | if (s=='-') | |
− | + | { | |
− | + | cout << '\n' << "The program is finished." << '\n' << endl; ///вывод на экран сообщения о завершении работы программы | |
− | + | } | |
− | + | } | |
− | + | while (s != '-'); ///цикл работает до тех пор, пока пользователь не даст команду на его завершение, а также на завершение всей программы | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | </syntaxhighlight> | |
− | + | </div> | |
− | |||
− | + | '''[[Александр Сюрис]]''' | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Программа работает в двух режимах: поиск максимального числа фигур для заданного поля и количество возможных расстановок заданного числа фигур для заданного поля. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''Алгоритм:''' | |
− | |||
− | + | #Для поиска количества возможных расстановок заданного числа фигур для заданного поля – Проверяется, возможно ли поставить фигуру в данную клетку, рекурсивно перебирает для каждой клетки поля, как начальной клетки, все варианты расстановки заданного количества фигур относительно нее и выводит на экран все расстановки, которые подходят условиям. | |
− | + | #Для поиска максимального числа фигур для заданного поля – Проверяется, можно ли поставить одну фигуру, две, три и так далее, пока фигур больше поставить будет нельзя. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Скачать можно [http://mech.spbstu.ru/File:%D0%A8%D0%B0%D1%85%D0%BC%D0%B0%D1%82%D1%8B(%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%A1%D1%8E%D1%80%D0%B8%D1%81).zip тут]. | |
− | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | " | ||
<syntaxhighlight lang="cpp" line start="1" enclose="div"> | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | ||
− | + | #include <vector> | |
− | + | #include <iostream> | |
− | + | #include <algorithm> | |
− | |||
− | |||
− | |||
− | |||
− | |||
using namespace std; | using namespace std; | ||
− | + | int n,k, o, m, l, g, maxi, a, sum=0,y, mozno=1;//mozno=1 если можно поставить n фигур | |
− | + | vector<vector<int> > matrix;// двухмерный вектор | |
− | + | bool ladia(int x, int y) { //проверка, можно ли в эту клетку поставить ладью | |
− | + | for(int i = 0; i<n; i++) | |
− | + | if(matrix[x][i] == 1) | |
− | + | return false; | |
− | + | for(int j=0; j<n; j++) | |
− | + | if(matrix[j][y]==1) | |
− | + | return false; | |
− | + | return true; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | bool slon(int x, int y) { // --//-- слона | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | for (int i=x, j=y;i<n && j>=0; i++, j--) | |
− | + | if(matrix[i][j] == 1) | |
− | + | return false; | |
− | + | for (int i=x, j=y;i>=0 && j>=0; i--, j--) | |
− | + | if(matrix[i][j] == 1) | |
− | + | return false; | |
− | + | for (int i=x, j=y;i>=0 && j<n; i--, j++) | |
− | + | if(matrix[i][j] == 1) | |
− | + | return false; | |
− | + | for (int i=x, j=y;i<n && j<n; i++, j++) | |
− | + | if(matrix[i][j] == 1) | |
− | + | return false; | |
− | |||
− | |||
− | |||
− | + | return true; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
+ | bool fruz(int x, int y){ // --//-- ферзя | ||
+ | if(slon(x,y) && ladia(x,y)) | ||
+ | return true; | ||
− | + | return false; | |
− | |||
− | + | } | |
− | + | bool kon(int x, int y) { // --//-- коня | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if (x-1>=0 && y-2>=0 && matrix[x-1][y-2]==1) | |
− | + | return false; | |
− | + | if (y-2>=0 && x+1<n && matrix[x+1][y-2]==1) | |
− | + | return false; | |
− | + | if (x-2>=0 && y-1>=0 && matrix[x-2][y-1]==1) | |
+ | return false; | ||
+ | if (x+2<n && y-1>=0 && matrix[x+2][y-1]==1) | ||
+ | return false; | ||
+ | if (x-2>=0 && y+1<n && matrix[x-2][y+1]==1) | ||
+ | return false; | ||
+ | if (x+2<n && y+1<n && matrix[x+2][y+1]==1) | ||
+ | return false; | ||
+ | if (x-1>=0 && y+2<n && matrix[x-1][y+2]==1) | ||
+ | return false; | ||
+ | if (x+1<n && y+2<n && matrix[x+1][y+2]==1) | ||
+ | return false; | ||
+ | return true; | ||
+ | } | ||
+ | bool king(int x, int y) { // --//-- короля | ||
+ | |||
+ | if (x-1>=0 && y-1>=0 && matrix[x-1][y-1]==1) | ||
+ | return false; | ||
+ | if (x-1>=0 && matrix[x-1][y]==1) | ||
+ | return false; | ||
+ | if (y+1<n && x-1>=0 && matrix[x-1][y+1]==1) | ||
+ | return false; | ||
+ | if (y+1<n && matrix[x][y+1]==1) | ||
+ | return false; | ||
+ | if (y+1<n && x+1>n && matrix[x+1][y+1]==1) | ||
+ | return false; | ||
+ | if (x+1<n && matrix[x+1][y]==1) | ||
+ | return false; | ||
+ | if (x+1<n && y-1>=0 && matrix[x+1][y-1]==1) | ||
+ | return false; | ||
+ | if (y-1>=0 && matrix[x][y-1]==1) | ||
+ | return false; | ||
+ | return true; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | int mass() { // вывод доски на экран | |
− | { | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | for(int i = 0; i<n; i++) | |
− | + | { | |
− | |||
− | |||
− | |||
− | for(int | + | for(int j = 0; j<n; j++) |
− | + | cout<<matrix[i][j]<<" "; | |
− | |||
− | |||
− | |||
− | + | cout<<endl; | |
− | |||
− | |||
− | |||
} | } | ||
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | + | int del() { // очистка доски(все нули) | |
− | + | ||
− | + | for (int i=0; i<n; i++) { | |
− | |||
− | |||
− | + | for (int j=0; j<n; j++) | |
+ | matrix[i][j]=0; | ||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | void | + | void vsevarintyrasstavitnfigur(int x,int y){ // рекурсивный поиск всех вараинтов расстановок заданнного количества фигур (x - номер фигуры в доске, если ее растянуть в линию, y - кол-во фигур) |
− | + | if(y==0) { | |
− | + | if (a==1){ | |
− | + | mass(); | |
− | if | + | cout<<'\n'; |
− | + | } | |
− | + | if(a==2) { | |
− | + | mozno = 1; //mozno=1 если можно поставить n фигур | |
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | |||
− | |||
− | + | return; | |
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | for(int i = | + | for(int i=x;i<n*n;i++){ |
− | |||
− | |||
− | |||
− | |||
− | + | if (o==1) | |
− | + | if(fruz(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;} | |
− | |||
− | |||
− | |||
− | + | if (o==2) | |
− | + | if(ladia(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;} | |
− | if( | ||
− | |||
− | |||
− | + | if (o==3) | |
− | + | if(slon(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if (o==4) | |
− | + | if(kon(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;} | |
− | |||
− | |||
− | if( | + | if (o==5) |
− | + | if(king(i/n,i%n) && y>0) {matrix[i/n][i%n]=1; y--;} | |
− | |||
− | |||
− | |||
− | + | vsevarintyrasstavitnfigur(i+1, y); | |
− | + | matrix[i/n][i%n]=0;//удаление фигуры из прошлой клетки для проверки других вариантов | |
+ | y++; | ||
− | |||
− | |||
} | } | ||
+ | |||
} | } | ||
− | + | void maxfig(){ //поиск максимального количества фигур | |
− | + | int i=0; | |
− | + | while(mozno==1){ //проверяет для данной доски возможность расставить 1,2... фигуры, пока не доходит до количества, которое расставить невозхможно. Тогда это количество фигур -1 - искомая величина | |
− | + | i++; | |
+ | mozno=0; | ||
+ | vsevarintyrasstavitnfigur(0,i); | ||
+ | } | ||
+ | setlocale(LC_ALL, "Russian"); | ||
+ | cout<<"Максимальное количество фигур = "<<i-1<<endl; | ||
+ | } | ||
− | |||
− | |||
− | + | int main() { | |
− | + | setlocale(LC_ALL, "Russian"); | |
+ | g=0; | ||
+ | cout<<"Введите размер доски:"<<endl; | ||
+ | cin >>n; | ||
+ | for(int i=0; i<n; i++) { | ||
+ | vector<int> z; | ||
+ | for(int j=0; j<n; j++){ | ||
+ | z.push_back(0); //создание вектора z из n нулей и добавление его к двухмерному вектору | ||
+ | } | ||
+ | matrix.push_back(z); | ||
+ | } | ||
+ | |||
+ | cout<<"1 - расстановки фигур на доске n*n"<<endl<<"2 - максимум фигур на доске n*n"<<endl; | ||
+ | cin>>a; | ||
− | + | while(2>1){ | |
− | + | cout<<" 1 - ферзь"<<endl; | |
+ | cout<<" 2 - ладья"<<endl; | ||
+ | cout<<" 3 - слон"<<endl; | ||
+ | cout<<" 4 - конь"<<endl; | ||
+ | cout<<" 5 - король"<<endl; | ||
+ | cout<<" 6 - выход"<<endl; | ||
+ | |||
+ | cout<<"Введите число от 1 до 6:"<<endl; | ||
+ | cin>>o; | ||
+ | mozno=1; | ||
+ | if(o==6) break; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if (o==1) { | |
− | + | cout<<"Ферзь"<<endl; | |
− | if( | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | if ( | + | if(a==1) |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | cin>>y; | |
− | + | vsevarintyrasstavitnfigur(0,y); | |
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | if | + | if (a==2) |
− | + | maxfig(); | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | if (o==2) { | |
− | + | cout<<endl<<"Ладья"<<endl; | |
− | + | ||
− | + | if(a==1) | |
+ | { | ||
+ | |||
+ | cin>>y; | ||
+ | vsevarintyrasstavitnfigur(0,y); | ||
+ | } | ||
− | + | if (a==2) | |
− | + | maxfig(); | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | if( | + | if (o==3) { |
− | + | cout<<endl<<"Слон"<<endl; | |
− | |||
− | |||
− | |||
− | |||
− | + | if(a==1) | |
− | + | { | |
− | + | cin>>y; | |
− | + | vsevarintyrasstavitnfigur(0,y); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | cin >> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | if (a==2) | |
− | + | maxfig(); | |
− | + | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | |||
+ | if (o==4) { | ||
+ | cout<<endl<<"Конь"<<endl; | ||
+ | |||
+ | if(a==1) | ||
+ | { | ||
+ | cin>>y; | ||
+ | vsevarintyrasstavitnfigur(0,y); | ||
+ | } | ||
+ | if (a==2) | ||
+ | maxfig(); | ||
+ | |||
+ | } | ||
− | < | + | if (o==5) { |
− | + | cout<<"Король"<<endl; | |
+ | |||
+ | if(a==1) | ||
+ | { | ||
+ | cin>>y; | ||
+ | vsevarintyrasstavitnfigur(0,y); | ||
− | + | } | |
+ | if (a==2) | ||
+ | maxfig(); | ||
− | + | } | |
− | + | } | |
− | |||
− | |||
− | |||
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | </syntaxhighlight> | |
− | + | </div> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''[[Лосева Татьяна]]''' | |
− | + | ||
− | + | '''Краткое описание алгоритма :''' | |
− | + | Доска представлена в виде динамического массива;Для каждой фигуры написана отдельная функция проверки на возможность установки фигуры,проверяющая, находится ли эта фигура под ударом других. | |
− | + | После выбора типа фигуры,используется рекурсивная функция,которая проверяет возможные расстановки через данную функцию проверки ,для данного типа фигуры. | |
− | + | Для поиска максимального значения мы проверяем расстановку начиная с 0 количество фигур ,каждый раз увеличивая на 1,если количество расстановок станет равно нулю,то предыдущее количество фигур было максимальным. | |
− | + | ||
− | + | '''Инструкция''' : Пользователя попросят ввести размер доски,затем выбрать один из вариантов работы программы:1.поиск возможных расстановок для M фигур или 2.поиск максимального количества расстановок для данного поля,затем попросят выбрать тип фигуры и в первом случае количество фигур.При выводе на экран выводится номер расстановки и доска,на доске F- обозначены занятые клетки,0-пуская клетка. | |
− | + | Для 2 пункта выводится лишь число: максимальное количество фигур,которое можно расставить. | |
− | + | ||
− | + | Скачать можно : [http://tm.spbstu.ru/Файл:Шахматы_Лосева.rar тут] | |
− | + | ||
− | + | ||
− | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
− | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
− | + | #include<iostream> | |
− | + | using namespace std; | |
− | + | int N;//размер доски NxN | |
− | + | int **a; | |
− | + | int *ax; | |
− | + | int *by; | |
− | + | int l = 0;//L-номер пункта в меню | |
− | + | int M;//количество фигур | |
− | + | bool isPrint = false;//переменная для вывода на экран,когда требуется,для удобства обозначим в начале false | |
− | + | ||
− | + | ||
− | + | void print()//функция вывода на экран | |
− | + | { | |
− | + | for (int i = N - 1; i >= 0; --i) | |
− | + | { | |
− | + | for (int j = 0; j < N; ++j) | |
− | + | { | |
− | + | cout << ((a[j][i]) ? "F " : "0 ");//если (a[j][i]) истина,то есть клетка занята,ставим F,в другом случае,т.е.свободна,ставим 0 | |
− | + | } | |
− | + | cout << '\n'; | |
− | + | } | |
− | + | cout << '\n'; | |
− | + | ||
− | + | } | |
− | + | bool Lad(int x, int y)//Ладья | |
− | + | { | |
− | + | for (int i = 0; i < N; ++i) | |
− | + | { | |
− | + | if (a[i][y] == 1 )//проверяем горизонталь:если клетка занята | |
− | + | { | |
− | + | return false;//возвращаем false | |
− | + | } | |
− | + | if (a[x][i] == 1)//проверяем вертикаль : если хотя бы одна клетка занята,то | |
− | + | { | |
− | + | return false;//возврашаем false | |
− | + | } | |
− | + | } | |
− | + | return true;//ничего выше не выполняется,значит возвращаем правду:вертикаль и горизонталь свободна | |
− | + | ||
− | + | } | |
− | + | ||
− | + | bool Kon(int x, int y)//Коняша | |
− | + | { | |
− | + | int i[8] = {-2, -2, -1, -1, 1, 1, 2, 2};//координаты клеток,на которые может ходить конь,относительно текущей (8 вариантов) | |
− | + | int j[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; | |
− | + | ||
− | + | for (int k = 0; k < 8; k++)//8 вариантов хода | |
− | + | ||
− | + | { | |
− | + | if (x + i[k] >= 0 && x + i[k] < N && y + j[k] >= 0 && y + j[k] < N)//проверка выхода за границы массива | |
− | + | { | |
− | + | if (a[x + i[k]][y + j[k]] != 0)//клетка занята | |
− | + | { | |
− | + | return false;//возвращем false | |
− | + | } | |
− | + | } | |
− | + | } | |
− | + | return true;////ничего выше не выполняется,значит возвращаем правду:все варианты ходов свободны и конь никого не перебивает,тогда можно занять клетку | |
− | + | ||
− | + | } | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | bool Korol(int x, int y)//Король | |
− | + | { | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | int | + | int i[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };//координаты клеток,на которые может ходить король,относительно текущей |
+ | int j[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; | ||
− | + | for(int k = 0; k < 8; k++)//8 вариантов хода | |
− | { | + | { |
− | + | if (x + i[k] >= 0 && x + i[k] < N && y + j[k] >= 0 && y + j[k] < N)//прроверяем не выходит ли фигура за границы массива | |
− | + | { | |
− | + | if (a[x + i[k]][y + j[k]] != 0)//если какой нибудь из вариантов хода занят | |
− | + | { | |
− | + | return false;//то false | |
− | + | } | |
− | + | } | |
− | + | } | |
− | + | return true;//свободно,можно занимать | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | bool Slon(int x, int y) | |
{ | { | ||
− | + | int p1 = y - x;//номер диагонали слева направо | |
− | + | int p2 = y + x;//номер диагонали с права налево | |
− | + | for (int i = 0; i < N; i++)//проверяем левую диагональ | |
− | + | { | |
− | + | if (i + p1 >= 0 && i + p1 < N)//проверка на выход за границы массива | |
− | + | { | |
− | + | if (a[i][i + p1] == 1) //проверяем диагональ | |
− | + | { | |
− | + | return false;//диагональ занята | |
− | + | } | |
− | + | } | |
− | + | if (-i + p2 >= 0 && -i + p2 < N)//вторая диагональ | |
− | + | { | |
− | + | if (a[i][-i + p2] == 1) | |
− | + | { | |
− | + | return false;//вторая диагональ занята | |
− | + | } | |
− | + | } | |
− | + | } | |
− | + | return true;//обе диагонали свободны,ура! | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
− | + | bool Check(int x, int y)//Ферзь=Ладья+Слон | |
{ | { | ||
− | + | int p1 = y - x;//диагональ 1 | |
− | + | int p2 = y + x;//диагональ 2 | |
− | + | for (int i = 0; i < N; ++i) | |
− | + | { | |
− | + | if (a[i][y] == 1 )//проверяем горизонталь | |
− | + | { | |
− | + | return false;//занято | |
− | + | } | |
− | + | if (a[x][i] == 1)//проверяем вертикаль | |
− | + | { | |
− | + | return false;//занято | |
− | + | } | |
− | + | ||
− | + | if (i + p1 >= 0 && i + p1 < N)//выход за границы массива | |
− | + | { | |
− | + | if (a[i][i + p1] == 1) //проверяем 1 диагональ | |
− | + | { | |
− | + | return false;//занято | |
− | + | } | |
− | + | } | |
− | + | if (-i + p2 >= 0 && -i + p2 < N)//выход за границы массива | |
− | + | { | |
− | + | if (a[i][-i + p2] == 1)//проверяем 2ую диагональ | |
− | + | { | |
− | + | return false;//занято | |
− | + | } | |
− | + | } | |
+ | } | ||
+ | return true;//свободно! | ||
} | } | ||
− | + | int menu1() | |
{ | { | ||
− | + | cout << "Type of figure:" << endl << "1 - Ferz" << endl << "2 - Ladya" << endl << "3 - Slon" << endl << "4 - Kon" << endl << "5 - Korol" << endl; | |
− | + | cin >> l; | |
− | + | return l; | |
− | |||
} | } | ||
− | + | int num = 0;//номер расстановки | |
− | + | //пробует найти результаты решений. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | void | + | void Func(int d,int K) //d-глубина рекурсии;K-сколько фигур нужно расставить |
{ | { | ||
− | + | if (d == K)//когда расставили нужное количество | |
− | + | { | |
− | + | if (isPrint)//если true,то печатаем(в случае с MAX количеством доску печатать не нужно) | |
− | + | { | |
− | } | + | cout << "Result: " << num + 1 << '\n';//выводим нормер расстановки |
+ | print();//печатаем доску | ||
+ | } | ||
+ | num++;//номер расстановки увеличивается | ||
+ | return; | ||
+ | } | ||
− | int | + | int minX = d != 0 ? ax[d - 1] : 0;//исходя из того куда быда поставлена предыдущая фигура |
− | + | //,накладываются ограничения для выбора места новой,чтобы избежать поторений | |
− | + | int minY = d != 0 ? by[d - 1] + 1 : 0; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | bool isPossible = false;//Проверяет,возможно ли занять клетку | ||
+ | for (int i = minX; i < N; ++i) | ||
+ | { | ||
− | </ | + | for (int j = (i != minX) ? 0 : minY; j < N; ++j) |
− | + | { | |
+ | switch (l)//l- номер пункта в меню с фигурами | ||
+ | { | ||
+ | case 1://ферзь | ||
+ | isPossible = Check(i, j); | ||
+ | break; | ||
+ | case 2://Ладья | ||
+ | isPossible = Lad(i, j); | ||
+ | break; | ||
+ | case 3://Слон | ||
+ | |||
+ | isPossible = Slon(i, j); | ||
+ | break; | ||
+ | case 4://Конь | ||
+ | isPossible = Kon(i, j); | ||
+ | break; | ||
+ | case 5://Король | ||
+ | isPossible = Korol(i, j); | ||
+ | break; | ||
+ | } | ||
+ | if (isPossible)//если клетку занять возмоно(функция вернула true) | ||
+ | { | ||
+ | a[i][j] = 1;//занимаем клетку | ||
+ | ax[d] = i;//запоминаем куда была поставлена фигура | ||
+ | by[d] = j;//запоминаем куда была поставлена фигура | ||
+ | Func(d + 1, K);//вызываем рекурсивно | ||
+ | a[i][j] = 0; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | return; | ||
+ | } | ||
− | + | int main() | |
+ | { | ||
− | + | cout << "Enter size: ";//нужно ввести размер доски | |
+ | cin >> N;//считываем размер доски | ||
− | + | a = new int*[N];//создаём двумерный массив,т.е.нашу доску | |
− | + | for (int i = 0; i < N; i++) | |
− | + | { | |
+ | a[i] = new int[N]; | ||
+ | for (int j = 0; j < N; j++) | ||
+ | a[i][j] = 0;//заполняем нулями | ||
+ | } | ||
+ | |||
+ | ax = new int[N];//массивы для сохранения координаты каждой фигуры,чтобы избежать повторений | ||
+ | by = new int[N]; | ||
− | + | int d;//пункт в меню | |
+ | cout<<"1 - Rasstanovka figur"<<endl<<"2 - MAX znachenie"<<endl;//два варианта работы программы | ||
+ | cin>>d;//считываем выбор пользователя | ||
+ | if(d==1)//если выбирает расстановку | ||
+ | { | ||
+ | menu1();//то спрашиваем для какой фигуры | ||
+ | cout<<"How many figures?"<<endl;//и как много будет фигур | ||
+ | cin>>M;//считываем количество фигур | ||
+ | isPrint = true;//в этом случае будем выводить на экран | ||
+ | Func(0,M);//запуск рекурсивной функции | ||
+ | } | ||
− | + | if (d == 2)//случай подсчёта максимального значения | |
+ | { | ||
+ | int n = 0;//изачально max=0 | ||
+ | menu1();//выбираем фигуру | ||
+ | |||
+ | do//начало цикла | ||
+ | { | ||
+ | num = 0; | ||
+ | Func(0, ++n);//запускаем каждый раз увеличивая значение фигур и считаем количество расстановок | ||
+ | } while (num != 0);//количество вариантов не должно быть равно нулю | ||
+ | cout <<"MAX ="<< n - 1 << endl;//если количество вариантов = 0,то выходим из цикла и предыдущее значение максимальное | ||
+ | } | ||
+ | |||
− | + | int z; | |
+ | cin >> z; | ||
− | '''Идея алгоритма''': Функция вызывает саму себя(рекурсия) в рекурсии фигура ставится на небьющуюся клетку и помечаются клетки, которые бьются этой фигурой.Если дальше ставить нельзя, то начинается обратный ход:фигура убирается, и запоминается место, где она стояла, и вновь вызывается функция. | + | return 0; |
+ | } | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | '''[[Степанянц Степан]]''' | ||
+ | |||
+ | '''Программа''': 1)Программа получает все возможные варианты расстановок одинаковых фигур на поле боя(шахматной доске) так, чтобы они не смогли бить друг друга.2)Программа выводит максимальное число фигур, которые можно поставить на шахматную доску nxn так, чтобы они не смогли бить друг друга. | ||
+ | |||
+ | '''Идея алгоритма''': Функция вызывает саму себя(рекурсия) в рекурсии фигура ставится на небьющуюся клетку и помечаются клетки, которые бьются этой фигурой.Если дальше ставить нельзя, то начинается обратный ход:фигура убирается, и запоминается место, где она стояла, и вновь вызывается функция. | ||
Скачать можно [http://tm.spbstu.ru/Файл:Шахматы.rar тут]. | Скачать можно [http://tm.spbstu.ru/Файл:Шахматы.rar тут]. | ||
Строка 4279: | Строка 3369: | ||
cout << func(n, k, 0, v, 0, 0, fig, task); | cout << func(n, k, 0, v, 0, 0, fig, task); | ||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''[[Лобанов Илья]]''' | |
− | |||
− | + | '''Описание алгоритма''': | |
− | |||
− | |||
− | |||
− | |||
− | |||
+ | Программа проверяет возможность расстановки фигур на доске M*M . При выводе на экран на экран клетки,занятые фигурами ,помечаются буквами,соответствующими первой букве типа фигуры. Также программа считает максимальное число фигур определенного типа,которые можно расставить на доске. | ||
− | + | '''Инструкция''' | |
+ | В окне консоли пользователю предлагается выбрать 2 типа работы программы, затем пользователь вводит размер доски(четный),тип и количество фигур,которые необходимо разместить на доске.В зависимости от режима работы программы ,будет выведено либо максимально возможное число расстановок фигур,либо максимальное число фигур. | ||
+ | Скачать можно тут [[http://tm.spbstu.ru/File:ConsoleApplication54.rar]] | ||
− | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
− | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | <div class="mw-collapsible mw-collapsed" style="width:100%" > | ||
− | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |