Редактирование: Информатика: Расстановка шахматных фигур
Внимание! Вы не авторизовались на сайте. Ваш 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++; | ||
| + | } | ||
} | } | ||
| − | + | } | |
| + | |||
| + | void bishop(int x, int &top) //отметить битые клетки слоном | ||
| + | { | ||
| + | //вверх влево | ||
| + | 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)) |
| − | |||
| − | for (int x=0; | ||
{ | { | ||
| − | + | 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) | |
| − | if (((x | ||
| − | |||
{ | { | ||
| − | + | 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 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; | |
| − | |||
| − | { | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | } | |
| − | + | ||
| − | + | //отмечаем,что в данной клетке стоит фигура | |
| − | + | a[x] = -1; | |
| − | + | stak[top] = x; | |
| − | + | top++; | |
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | int | + | void step(int top,int x,int st) |
{ | { | ||
| − | + | 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 ( | + | 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 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 | ||
{ | { | ||
| − | + | for (int j = 0; j < (n*n); j++) | |
| − | for ( | + | a[j] = 0; |
| − | + | if (variant == 1) | |
| − | + | cout << "__________________________________" << endl; | |
| − | + | step(0,i,0); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| + | 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 (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) | |
| − | |||
| − | |||
{ | { | ||
| − | + | board_[i][j] = 0; | |
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | } | |
| − | + | } | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | // функция, принимающая размер доски | |
| + | int get_size() | ||
| + | { | ||
| + | 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 ( | + | 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 | + | 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) | |
| − | |||
| − | |||
| − | if ( | ||
{ | { | ||
| − | + | 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); | ||
| + | } | ||
| − | return | + | //функция поиска расстановок, в случае, когда на доске что-то стоит, вернуть ложь |
| + | //иначе поставить вернуть истину | ||
| + | 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 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; | |
| − | for (int | + | const int size = board.get_size(); |
| + | for (int i = 0; i < size; ++i) | ||
{ | { | ||
| − | + | for (int j = 0; j < size; ++j) | |
| − | for(int | ||
{ | { | ||
| − | + | //если мы можем поставить фигуру, то добавляем к максимуму единицу и запускаем цикл снова | |
| + | 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")) | ||
| + | { | ||
| + | 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; | |
| − | if( | + | |
| + | 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 CheckHorse(int x, int y)//проверка для коня в клетке с номером x, y | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{ | { | ||
| − | + | 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)) | |
| − | else | ||
{ | { | ||
| − | + | return false; | |
| − | |||
} | } | ||
| − | + | else if (((x+2)<M ) && ((y-1)>=0) && (ChessBoard[x+2][y-1]==1)) | |
| − | |||
| − | |||
{ | { | ||
| − | + | return false; | |
| − | + | } | |
| − | + | else if (((x-2)>=0 ) && ((y+1)<M) && (ChessBoard[x-2][y+1]==1)) | |
| − | + | { | |
| − | + | 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; //возвращаем количество фигур | |
| − | return | ||
| − | |||
} | } | ||
| − | + | bool CheckKing(int x, int y) //все то же самое для проверки короля, стоящего в клетке х,у | |
| − | |||
| − | |||
| − | |||
{ | { | ||
| − | if( | + | 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; | ||
| − | if (x == | + | } |
| − | return; | + | 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)) | |
| − | + | { | |
| − | + | sum=sum+1; | |
| − | + | } | |
| − | + | else | |
| − | |||
{ | { | ||
| − | + | sum=0; | |
| − | + | break; | |
} | } | ||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | |||
} | } | ||
| − | + | if (y<M) | |
| + | { | ||
| + | break; | ||
| + | } | ||
} | } | ||
| − | + | return sum; | |
} | } | ||
| − | int | + | 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 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; | |
| + | 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:///королева | |
| − | + | { | |
| − | + | 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 | 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 | ||
{ | { | ||
| − | for (int | + | 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 | |
| − | for (int | + | 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(); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | int | + | ///проверяем наличие фигуры в строке а |
| + | bool isEmptyHorisontal(int a) | ||
{ | { | ||
| − | |||
| − | |||
| − | int | + | for(int i=0; i<n; ++i)///создаем цикл от 0 до n |
| − | + | { | |
| − | + | 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;///неверно | ||
| + | } | ||
} | } | ||
| − | return | + | 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], | |
| + | ///будет ли он единственным в этих строке, столбце и диагоналях | ||
| + | { | ||
| + | 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) | |
| − | void | ||
{ | { | ||
| − | |||
| − | |||
| − | |||
| − | + | for(int column=0; column<n; ++column)///двигаемся по столбцу сверху вниз | |
| − | |||
{ | { | ||
| − | + | ||
| − | if ( | + | 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 (( | + | { |
| − | + | ||
| − | + | 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++)///для ячеек находящихся слева и справа от поставленного короля | |
| − | for (int i = | ||
{ | { | ||
| − | + | for(int j = b-1; j <= b+1; j++)///для ячеек находящихся снизу и сверху от поставленного короля | |
{ | { | ||
| − | + | if (isFigure(i,j))///если выполняется это условие | |
| − | + | return false;///неверно | |
| − | |||
} | } | ||
} | } | ||
| − | // | + | return true;///в остальных случаях верно |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | void | + | ///функция поиска результатов решений |
| + | /// count - количество фигур, поставленое к данному моменту | ||
| + | ///x,y - позиция, начиная с которой разрешено ставить фигуры (все предшествующие позиции уже точно определены) | ||
| + | void setKing(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(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; | ||
| + | |||
| + | } | ||
| + | |||
} | } | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | } | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | if ((( | + | 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;///в остальных случаях верно | ||
| + | |||
| + | } | ||
| + | |||
| + | ///функция поиска результатов решений | ||
| + | /// count - количество фигур, поставленое к данному моменту. | ||
| + | void setHorse(int count, int x, int y) | ||
| + | { | ||
| + | |||
| + | 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) | |
{ | { | ||
| − | + | ||
| + | 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 = | + | 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; | 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- очередной столбец | |
| − | int | ||
{ | { | ||
| − | + | 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; | ||
| + | } | ||
| + | |||
| + | 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 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 - счетчик количества фигур, которое необходимо расставить | |
| − | void | ||
{ | { | ||
| − | + | 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 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 | + | 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> | </syntaxhighlight> | ||
</div> | </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"> | ||
| + | #include <vector> | ||
| + | #include <iostream> | ||
| + | #include <algorithm> | ||
| − | |||
| − | |||
| − | + | 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 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 vsevarintyrasstavitnfigur(int x,int y){ // рекурсивный поиск всех вараинтов расстановок заданнного количества фигур (x - номер фигуры в доске, если ее растянуть в линию, y - кол-во фигур) | ||
| + | if(y==0) { | ||
| + | if (a==1){ | ||
| + | mass(); | ||
| + | cout<<'\n'; | ||
| + | } | ||
| + | if(a==2) { | ||
| + | mozno = 1; //mozno=1 если можно поставить n фигур | ||
| + | |||
| + | } | ||
| + | |||
| + | return; | ||
| + | } | ||
| + | |||
| + | 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 (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 (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(a==1) | |
| − | + | { | |
| − | + | cin>>y; | |
| − | + | vsevarintyrasstavitnfigur(0,y); | |
| + | } | ||
| + | |||
| + | |||
| + | if (a==2) | ||
| + | maxfig(); | ||
| + | |||
| + | } | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | if (o==2) { | |
| − | + | cout<<endl<<"Ладья"<<endl; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | if(a==1) | |
| − | + | { | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | cin>>y; | |
| + | vsevarintyrasstavitnfigur(0,y); | ||
| + | } | ||
| − | + | if (a==2) | |
| − | + | maxfig(); | |
| − | |||
| − | |||
| − | |||
| + | } | ||
| − | |||
| − | + | if (o==3) { | |
| + | cout<<endl<<"Слон"<<endl; | ||
| − | + | if(a==1) | |
| + | { | ||
| + | cin>>y; | ||
| + | vsevarintyrasstavitnfigur(0,y); | ||
| + | } | ||
| − | + | 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 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 | + | 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 | + | int num = 0;//номер расстановки |
| + | //пробует найти результаты решений. | ||
| + | |||
| + | void Func(int d,int K) //d-глубина рекурсии;K-сколько фигур нужно расставить | ||
{ | { | ||
| − | + | if (d == K)//когда расставили нужное количество | |
| − | + | { | |
| − | + | if (isPrint)//если true,то печатаем(в случае с MAX количеством доску печатать не нужно) | |
| − | + | { | |
| − | + | cout << "Result: " << num + 1 << '\n';//выводим нормер расстановки | |
| − | + | print();//печатаем доску | |
| − | + | } | |
| − | + | num++;//номер расстановки увеличивается | |
| − | + | return; | |
| − | + | } | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | 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; |
| − | #include < | + | } |
| − | + | </syntaxhighlight> | |
| + | </div> | ||
| + | |||
| + | '''[[Степанянц Степан]]''' | ||
| + | |||
| + | '''Программа''': 1)Программа получает все возможные варианты расстановок одинаковых фигур на поле боя(шахматной доске) так, чтобы они не смогли бить друг друга.2)Программа выводит максимальное число фигур, которые можно поставить на шахматную доску nxn так, чтобы они не смогли бить друг друга. | ||
| + | |||
| + | '''Идея алгоритма''': Функция вызывает саму себя(рекурсия) в рекурсии фигура ставится на небьющуюся клетку и помечаются клетки, которые бьются этой фигурой.Если дальше ставить нельзя, то начинается обратный ход:фигура убирается, и запоминается место, где она стояла, и вновь вызывается функция. | ||
| + | |||
| + | Скачать можно [http://tm.spbstu.ru/Файл:Шахматы.rar тут]. | ||
| + | |||
| + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | ||
| + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | ||
| + | #include <iostream> | ||
| + | #include <vector> | ||
| + | |||
| + | using namespace std; | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | //задаю массивы в которых изображены все ходы определенных фигур | |
| − | { | + | int d = 0; |
| − | + | int d_knight[2][8] = {{1, 1, -1, -1, 2, 2, -2, -2}, | |
| − | + | {2, -2, 2, -2, 1, -1, 1, -1}}; | |
| − | + | int d_bish[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; | |
| − | return | + | int d_king[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; |
| + | //Проверяем, не выходим ли мы за поле | ||
| + | bool ok(int x, int y, int n) { | ||
| + | if (x < 0 || y < 0 || x >= n || y >= n) | ||
| + | return false; | ||
| + | return true; | ||
} | } | ||
| − | + | void print(int n, vector<vector<pair<bool, int> > > board) { | |
| − | + | for (int i = 0; i < n; i++) { | |
| − | + | for (int j = 0; j < n; j++) { | |
| − | + | cout << ((board[i][j].first) ? " X " : " 0 "); | |
| − | + | } | |
| − | + | cout << '\n'; | |
| − | + | } | |
| − | + | cout << "-------------------------------------\n"; | |
| − | + | } | |
| − | + | //Рекурсивная функция | |
| − | + | int func(int n, int k, int count, vector<vector<pair<bool, int> > > board, int ii, int jj, int fig, int task) { | |
| − | + | int ans = 0; | |
| − | for(int | + | if (count == k && !task) { |
| − | + | print(n, board); | |
| − | + | return 1; | |
| − | |||
| − | |||
} | } | ||
| − | + | else if(task) { | |
| − | + | ans = max(ans, count); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | for (int i = ii + jj / n; i < n; i++) { | |
| − | + | for (int j = jj % n; j < n; j++) { | |
| − | + | if (!board[i][j].first && !board[i][j].second) { | |
| − | + | switch (fig) { | |
| − | + | case 1://конь | |
| − | + | for (int k = 0; k < 8; k++) { | |
| − | + | if (ok(i + d_knight[0][k], j + d_knight[1][k], n)) | |
| − | + | board[i + d_knight[0][k]][j + d_knight[1][k]].second++; | |
| − | + | } | |
| − | + | break; | |
| − | + | case 2://слон | |
| − | + | for (int k = 0; k < n; k++) { | |
| − | + | for (int l = 0; l < 4; l++) { | |
| − | + | if (ok(i + k * d_bish[l][0], j + k * d_bish[l][1], n)) | |
| − | + | board[i + k * d_bish[l][0]][j + k * d_bish[l][1]].second++; | |
| − | + | } | |
| − | + | } | |
| − | + | break; | |
| − | + | case 3: // ладья | |
| − | + | for (int k = 0; k < n; k++) | |
| − | + | board[i][k].second++, board[k][j].second++; | |
| − | + | break; | |
| − | + | case 4: // король | |
| − | + | for (int k = 0; k < 8; k++) | |
| − | + | if (ok(i + d_king[k][0], j + d_king[k][1], n)) | |
| − | + | board[i + d_king[k][0]][j + d_king[k][1]].second++; | |
| − | + | break; | |
| − | + | case 5: // ферзь | |
| − | + | for (int k = 0; k < 8; k++) | |
| − | } | + | for (int l = 0; l < n; l++) |
| + | if (ok(i + l * d_king[k][0], j + l * d_king[k][1], n)) | ||
| + | board[i + l * d_king[k][0]][j + l * d_king[k][1]].second++; | ||
| + | break; | ||
| + | |||
| + | } | ||
| + | //Рекурсия | ||
| + | board[i][j].first = true; | ||
| + | if (!task) | ||
| + | ans += func(n, k, count + 1, board, i, j + 1, fig, task); | ||
| + | //обратный ход | ||
| + | else | ||
| + | ans = max(ans, func(n, k, count + 1, board, i, j + 1, fig, task)); | ||
| + | board[i][j].first = false; | ||
| + | switch (fig) { | ||
| + | case 1: | ||
| + | for (int k = 0; k < 8; k++) { | ||
| + | if (ok(i + d_knight[0][k], j + d_knight[1][k], n)) | ||
| + | board[i + d_knight[0][k]][j + d_knight[1][k]].second--; | ||
| + | } | ||
| + | break; | ||
| + | case 2: | ||
| + | for (int k = 0; k < n; k++) { | ||
| + | for (int l = 0; l < 4; l++) { | ||
| + | if (ok(i + k * d_bish[l][0], j + k * d_bish[l][1], n)) | ||
| + | board[i + k * d_bish[l][0]][j + k * d_bish[l][1]].second--; | ||
| + | } | ||
| + | } | ||
| + | break; | ||
| + | case 3: | ||
| + | for (int k = 0; k < n; k++) | ||
| + | board[i][k].second--, board[k][j].second--; | ||
| + | break; | ||
| + | case 4: | ||
| + | for (int k = 0; k < 8; k++) | ||
| + | if (ok(i + d_king[k][0], j + d_king[k][1], n)) | ||
| + | board[i + d_king[k][0]][j + d_king[k][1]].second--; | ||
| + | break; | ||
| + | case 5: | ||
| + | for (int k = 0; k < 8; k++) | ||
| + | for (int l = 0; l < n; l++) | ||
| + | if (ok(i + l * d_king[k][0], j + l * d_king[k][1], n)) | ||
| + | board[i + l * d_king[k][0]][j + l * d_king[k][1]].second--; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | jj = 0; | ||
} | } | ||
| − | + | return ans; | |
| − | + | } | |
| − | + | //меню | |
| − | + | int main() { | |
| − | + | int fig, task; | |
| − | + | int n, k; | |
| − | + | cout << "Please, input the task number: 1 - amount of solutions, 2 - maximum of figures\n"; | |
| − | + | cin >> task; | |
| − | + | task--; | |
| − | + | cout << "Please, input figure type: 1 - knight, 2 - bishop, 3 - castle, 4 - king, 5 - queen\n"; | |
| + | cin >> fig; | ||
| + | cout << "Please, input the size of the board\n"; | ||
| + | cin >> n; | ||
| + | if (!task) { | ||
| + | cout << "Please, input number of figures\n"; | ||
| + | cin >> k; | ||
} | } | ||
| − | + | vector<vector<pair<bool, int> > > v = vector<vector<pair<bool, int> > >(n, vector <pair<bool, int> >(n, {false, 0})); | |
| − | + | cout << func(n, k, 0, v, 0, 0, fig, task); | |
| − | + | } | |
| − | + | </syntaxhighlight> | |
| − | + | </div> | |
| − | + | ||
| − | + | '''[[Лобанов Илья]]''' | |
| − | + | ||
| − | + | '''Описание алгоритма''': | |
| − | + | ||
| − | + | Программа проверяет возможность расстановки фигур на доске 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"> | |
| − | + | #include <iostream> | |
| − | + | #include <windows.h> | |
| − | + | using namespace std; | |
| − | + | ||
| − | + | enum type{peshka, king, kon, ladya, slon, queen}; // все возможные типы фигур | |
| − | + | const char symbols[] = "pKklsQ"; // буквенное обозначение каждой фигуры:p - пешка, K - король, k - конь, l- ладья, s - слон, Q - ферзь | |
| − | + | const int NONE = INT_MAX;//константа для обозначения пустой клетки | |
| − | + | int M, **desk, *colons, *rows, *diag_1, *diag_2; | |
| − | + | ||
| − | + | // структура для описания клектки доски | |
| − | + | struct point | |
| − | + | { | |
| − | + | int x, y; | |
| − | + | point(int x = 0, int y = 0): x(x), y(y) {} | |
| − | + | point &operator++() | |
| − | + | { | |
| − | + | if (y == M - 1) | |
| − | + | { | |
| − | + | ++x; | |
| − | + | y = 0; | |
| − | + | } | |
| − | + | else | |
| − | + | ++y; | |
| − | + | return *this; | |
| − | + | } | |
| − | + | point operator+(const point &p) const | |
| − | + | { | |
| − | + | return point(x + p.x, y + p.y); | |
| − | + | } | |
| − | + | point next() const | |
| − | + | { | |
| − | + | point r = *this; | |
| − | + | return ++r; | |
| − | + | } | |
| − | + | }; | |
| − | + | ||
| − | + | ||
| − | + | int *new_array(int n) | |
| − | + | { | |
| − | + | int *a = new int[n]; | |
| − | + | fill(a, a + n, NONE); | |
| − | + | return a; | |
| − | + | } | |
| − | + | ||
| − | + | // Количество свободных клеток от клетки p до конца доски | |
| − | + | int rest(const point &p, type t) | |
| − | + | { | |
| − | + | int r0 = (M - p.x) * M - p.y, r, | |
| − | + | m = M - p.x, | |
| − | + | s_2 = (m + 1) / 2 * M; | |
| − | + | switch (t) | |
| − | + | { | |
| − | + | case peshka: | |
| − | + | case kon: | |
| − | + | r = s_2; break; | |
| − | + | case king: | |
| − | + | r = s_2 / 2; break; | |
| − | + | case ladya: | |
| − | + | case queen: | |
| − | + | return m; | |
| − | + | case slon: | |
| − | + | r = m + M - 1; | |
| − | + | } | |
| − | + | return min(r0, r); | |
| − | + | } | |
| − | + | ||
| − | + | // Помечает клетку доски номером i | |
| − | + | void set(const point &p, type t, int i) | |
| − | + | { | |
| − | + | if (t == peshka || t == king || t == kon) | |
| − | + | desk[p.x][p.y] = i; | |
| − | + | else | |
| − | + | { | |
| − | + | if (t == ladya || t == queen) | |
| − | + | colons[p.y] = rows[p.x] = i; | |
| − | + | if (t == slon || t == queen) | |
| − | + | diag_1[p.x+p.y] = diag_2[p.x-p.y+M-1] = i; | |
| − | + | } | |
| − | + | } | |
| − | + | ||
| − | + | // Можно ли поставить фигуру номер i на клетку p | |
| − | + | bool empty(const point &p, type t, int i) | |
| − | + | { | |
| − | + | const int n_attack[3] = {4, 8, 8}; | |
| − | + | const point attack[3][8] = {{point(1, 1), point(1, -1), point(-1, 1), point(-1, -1)}, //кол-во вариантов атаки для пешки | |
| − | + | {point(1, 1), point(1, -1), point(-1, 1), point(-1, -1), point(1, 0), point(-1, 0), point(0, 1), point(0, -1)}, // кол-во вариантов атаки для короля | |
| − | + | {point(1, 2),point(-1, 2),point(1, -2), point (-1,-2), point (2, 1), point (2,-1), point (-2, 1),point (-2,-1)}}; //количество вариантов атаки для коня | |
| − | + | switch(t) | |
| − | + | { | |
| − | + | case peshka: | |
| − | + | case king: | |
| − | + | case kon: | |
| − | + | for (int k = 0; k < n_attack[t]; k++) | |
| − | + | { | |
| − | + | point q = p + attack[t][k]; | |
| − | + | if (q.x >= 0 && q.x < M && q.y >= 0 && q.y < M && desk[q.x][q.y] < i) | |
| − | + | return false; | |
| − | + | } | |
| − | + | return true; | |
| − | + | case ladya: | |
| − | + | return colons[p.y] > i && rows[p.x] > i; | |
| − | + | case slon: | |
| − | + | return diag_1[p.x+p.y] > i && diag_2[p.x-p.y+M-1] > i; | |
| − | + | case queen: | |
| − | + | return colons[p.y] > i && rows[p.x] > i && diag_1[p.x+p.y] > i && diag_2[p.x-p.y+M-1] > i; | |
| − | + | } | |
| − | + | } | |
| − | + | ||
| − | + | //печатает заданное количество досок на экране | |
| − | + | void print(point **figures, int n_desks, int N, type t, ostream &out = cout) | |
| − | + | { | |
| − | + | HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); | |
| − | + | for (int n = 0; n < n_desks; n++) | |
| − | + | { | |
| − | + | out << " \xdb"; | |
| − | + | for (int i = 0; i < M * 2 + 2; i++) | |
| − | + | out << "\xdf"; | |
| − | + | out << "\xdb"; | |
| − | + | } | |
| − | + | out << endl; | |
| − | + | ||
| − | + | int *K = new int[n_desks]; | |
| − | + | fill(K, K + n_desks, 0); | |
| − | + | for (int i = 0; i < M; i++) | |
| − | + | { | |
| − | + | for (int n = 0; n < n_desks; n++) | |
| − | + | { | |
| − | + | int &k = K[n]; | |
| − | + | out << " \xdb "; | |
| − | + | for (int j = 0; j < M; j++) | |
| − | + | { | |
| − | + | SetConsoleTextAttribute(hConsole, (i + j) % 2 == 0 ? 0xf0 : 0xf); | |
| − | + | if (k < N && i == figures[n][k].x && j == figures[n][k].y) | |
| − | + | { | |
| − | + | out << ' ' << symbols[t]; | |
| − | + | k++; | |
| − | + | } | |
| − | + | else | |
| − | + | out << " "; | |
| − | + | } | |
| − | + | SetConsoleTextAttribute(hConsole, 0x70); | |
| − | + | out << " \xdb"; | |
| − | + | } | |
| − | + | out << endl; | |
| − | + | } | |
| − | + | delete[] K; | |
| − | + | ||
| − | + | for (int n = 0; n < n_desks; n++) | |
| − | + | { | |
| − | + | out << " \xdb"; | |
| − | + | for (int i = 0; i < M * 2 + 2; i++) | |
| − | + | out << "\xdc"; | |
| − | + | out << "\xdb"; | |
| − | + | } | |
| − | + | out << endl << endl; | |
| − | + | } | |
| − | + | ||
| − | + | // Вывести все возможные расположения на доске N фигур | |
| − | + | void all_placements(int N, type t) | |
| − | + | { | |
| − | + | desk = NULL; | |
| − | + | colons = rows = diag_1 = diag_2 = NULL; | |
| − | + | // создание необходимых массивов, отмечающих занятость клеток, в зависимости от вида фигуры | |
| − | + | if (t == peshka || t == king || t == kon) | |
| − | + | { | |
| − | + | desk = new int*[M]; | |
| − | + | for (int j = 0; j < M; j++) | |
| − | + | desk[j] = new_array(M); | |
| − | + | } | |
| − | + | else | |
| − | + | { | |
| − | + | if (t == ladya || t == queen) | |
| − | + | { | |
| − | + | colons = new_array(M); | |
| − | + | rows = new_array(M); | |
| − | + | } | |
| − | + | if (t == slon || t == queen) | |
| − | + | { | |
| − | + | diag_1 = new_array(2*M-1); | |
| − | + | diag_2 = new_array(2*M-1); | |
| − | + | } | |
| − | + | } | |
| − | + | ||
| − | + | const int W = 80 / (2 * M + 5);//количество досок,помещающихся на экране | |
| − | + | point **figures = new point*[W];//массив фигур | |
| − | + | for (int j = 0; j < W; j++) | |
| − | + | figures[j] = new point[N]; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | int | + | int i = 0, // номер фигуры |
| − | + | k = 0; //номер комбинации | |
| − | + | while (true) | |
| − | + | { | |
| − | + | if (rest(figures[k%W][i], t) < N - i) // если оставшиеся фигуры не помещаются на доске | |
| − | + | { | |
| − | + | if (i == 0) // если все комбинации закончились | |
| − | + | { | |
| − | + | // вывод оставшихся досок | |
| − | + | if (k % W) | |
| − | + | print(figures, k % W, N, t); | |
| − | + | cout << "Amount of combinations: " << k << endl; | |
| − | + | break; | |
| − | + | } | |
| − | + | // переходим к предыдущей фигуре и помечаем клетку пустой | |
| − | + | set(figures[k%W][--i], t, NONE); | |
| − | + | // сдвигаем фигуру на шаг вперёд | |
| − | + | ++figures[k%W][i]; | |
| − | + | } | |
| − | } | + | else if (!empty(figures[k%W][i], t, i)) // если фигуры помещаются, но текущая клетка под ударом |
| − | + | // сдвигаем текущую фигуру на шаг вперёд | |
| − | + | ++figures[k%W][i]; | |
| − | + | else if (i == N - 1) // если ставим последнюю фигуру | |
| − | + | { | |
| − | + | // если текущая доска - последняя на строке экрана, выводим W досок | |
| − | + | if ((k + 1) % W == 0) | |
| − | + | print(figures, W, N, t); | |
| − | + | // копирование комбинаций фигур на следующую доску | |
| − | + | for (int j = 0; j < N; j++) | |
| − | + | figures[(k+1)%W][j] = figures[k%W][j]; | |
| − | + | // переход к следующей доске | |
| − | + | k++; | |
| − | + | //сдвигаем текущую фигуру на шаг вперёд | |
| − | + | ++figures[k%W][i]; | |
| − | + | } | |
| − | + | else // если ставим не последнюю фигуру | |
| − | + | { | |
| − | + | // помечаем текущую клетку номером i | |
| − | + | set(figures[k%W][i], t, i); | |
| − | + | //ставим следующую фигуру на клетку после текущей | |
| − | + | figures[k%W][i+1] = figures[k%W][i].next(); | |
| − | + | // переходим к следующей фигуре | |
| − | + | i++; | |
| − | + | } | |
| − | + | } | |
| − | + | ||
| − | + | //освобождение памяти | |
| − | + | for (int j = 0; j < W; j++) | |
| − | + | delete[] figures[j]; | |
| − | + | delete[] figures; | |
| − | + | if (desk) | |
| − | + | { | |
| − | + | for (int j = 0; j < M; j++) | |
| − | + | delete[] desk[j]; | |
| − | + | delete[] desk; | |
| − | + | } | |
| − | + | if (colons) | |
| − | + | { | |
| − | + | delete[] colons; | |
| − | + | delete[] rows; | |
| − | + | } | |
| − | + | if (diag_1) | |
| − | + | { | |
| + | delete[] diag_1; | ||
| + | delete[] diag_2; | ||
| + | } | ||
} | } | ||
| − | + | ||
| + | int main() | ||
{ | { | ||
| − | + | system("color 70"); // Установка серого фона и чёрного текста | |
| − | + | while (true) | |
| − | + | { | |
| − | + | cout << "Choose the mode:\n1 - all possible variants of figures' placement\n2 - maximum number of figures which can be placed on the desk\nq - quit\n\n"; | |
| − | + | char c; | |
| − | + | cin >> c; | |
| − | + | cin.ignore(100, '\n'); | |
| − | + | switch (c) | |
| − | + | { | |
| − | + | case '1': | |
| − | + | case '2': | |
| − | + | cout << "Enter the desk size please. (The number must be even and not more than 37.)\n"; | |
| − | + | cin >> M; | |
| − | + | while (!cin || M % 2 != 0 || M > 37 || M <= 0) | |
| − | + | { | |
| − | + | cout << "Error: wrong desk size. Try again please.\n"; | |
| − | + | cin.clear(); | |
| − | + | cin.ignore(100, '\n'); | |
| − | + | cin >> M; | |
| − | + | } | |
| − | + | cin.ignore(100, '\n'); | |
| − | + | cout << "Choose a figure, please.\n p - peshka, k - kon, l - ladya, s - slon, Q - Queen, K - King\n"; | |
| − | + | char f; | |
| − | + | cin >> f; | |
| − | + | cin.ignore(100, '\n'); | |
| − | + | type t; | |
| − | + | int i; | |
| − | + | do | |
| − | + | { | |
| − | + | for (i = 0; i < 6; i++) | |
| − | { | + | { |
| − | + | if (symbols[i] == f) | |
| − | + | { | |
| − | + | t = type(i); | |
| − | + | break; | |
| − | } | + | } |
| − | + | } | |
| − | + | if (i == 6) | |
| − | + | { | |
| − | + | cout << "Enter the right letter, you've chosen the wrong one.\n"; | |
| − | + | cin >> f; | |
| − | + | cin.ignore(100, '\n'); | |
| − | + | } | |
| − | + | } while (i == 6); | |
| − | + | if (c == '1') | |
| − | + | { | |
| − | { | + | cout << "Enter the number of figures please.\n"; |
| − | + | int N; | |
| − | + | cin >> N; | |
| − | + | while (!cin || N <= 0) | |
| − | + | { | |
| − | } | + | cout << "Error: wrong argument. Try again please.\n"; |
| − | + | cin.clear(); | |
| − | + | cin.ignore(100, '\n'); | |
| − | { | + | cin >> N; |
| − | + | } | |
| − | + | cin.ignore(100, '\n'); | |
| − | + | all_placements(N, t); | |
| − | + | } | |
| − | + | else | |
| − | + | { | |
| − | + | cout << "The maximal number of figures is "; | |
| − | + | switch (t) | |
| − | + | { | |
| − | + | case peshka: | |
| − | + | cout << M*M/2; break; | |
| − | + | case king: | |
| − | + | cout << M*M/4; break; | |
| − | + | case kon: | |
| − | + | cout << (M == 2 ? 4 : M*M/2); break; | |
| − | + | case ladya: | |
| − | + | cout << M; break; | |
| − | + | case slon: | |
| − | + | cout << 2*M - 2; break; | |
| − | + | case queen: | |
| − | + | cout << (M == 2 ? 1 : M); | |
| − | + | } | |
| − | + | cout << ".\n"; | |
| − | + | } | |
| − | + | break; | |
| − | + | case 'q': | |
| − | + | cout << endl; | |
| − | + | return 0; | |
| − | + | default: | |
| − | + | cout << "You've chosen the wrong command, try again please.\n"; | |
| − | + | } | |
| − | + | cout << endl << endl; | |
| − | + | } | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | |||
| − | |||
| − | |||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
| + | '''[[Савельева Ольга]]''' | ||
| − | |||
| − | ''' | + | '''Инструкция''': В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей: либо максимальное число вариантов, либо посмотреть наглядно на варианты. Человек вводит размер доски и тип фигуры. |
| − | + | Скачать программу можно [http://tm.spbstu.ru/:File:Шахматы0001.zip ] | |
| − | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
| + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | ||
| − | + | #define windows | |
| − | + | #include <stdio.h> | |
| + | #include <vector> | ||
| − | + | #ifdef windows | |
| − | + | #include <windows.h> | |
| − | + | #endif // windows | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | #include < | ||
| − | # | ||
using namespace std; | using namespace std; | ||
| + | #ifdef windows | ||
| + | HANDLE hCon; | ||
| + | #endif // windows | ||
| − | + | unsigned fact(int n) //factorial of a number | |
| − | // | + | { |
| − | + | unsigned long long ret = 1; | |
| − | + | for(int i = 2; i <= n; i++) | |
| − | + | ret *= i; | |
| − | int | + | return ret; |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | return | ||
} | } | ||
| − | + | struct desk | |
| − | + | { | |
| − | for (int | + | char **deskFigures, **deskOccupy; //desk with figures, desk with occupation counter for each cell |
| − | + | int x, y, size, a, f; //pointer position(x, y), size of the desk, amount of prints, amount of figures | |
| − | + | vector<pair<int, int> > *s; //stack of placed figures | |
| − | + | bool stackIsUsed; //if stack is needed | |
| + | desk(int size, bool stackIsUsed = true):x(0), y(0), size(size), a(0), f(0), stackIsUsed(stackIsUsed) | ||
| + | { | ||
| + | deskFigures = new char*[size]; | ||
| + | for(int i = 0; i < size; i++) | ||
| + | deskFigures[i] = new char[size]; | ||
| + | deskOccupy = new char*[size]; | ||
| + | for(int i = 0; i < size; i++) | ||
| + | deskOccupy[i] = new char[size]; | ||
| + | if(stackIsUsed) | ||
| + | s = new vector<pair<int, int> >; | ||
| + | clear(); | ||
} | } | ||
| − | + | ~desk() | |
| − | + | { | |
| − | + | for(int i = 0; i < size; i++) | |
| − | + | delete deskFigures[i]; | |
| − | + | delete deskFigures; | |
| − | + | for(int i = 0; i < size; i++) | |
| − | + | delete deskOccupy[i]; | |
| − | + | delete deskOccupy; | |
| + | if(stackIsUsed) | ||
| + | delete s; | ||
} | } | ||
| − | + | void setKnight(int x, int y, int z) //increase all cells occupied by knight at (x, y) on z | |
| − | + | { | |
| − | + | if(x + 2 < size) | |
| − | + | { | |
| − | + | if(y - 1 >= 0) | |
| − | if ( | + | deskOccupy[x + 2][y - 1] += z; |
| − | + | if(y + 1 < size) | |
| − | + | deskOccupy[x + 2][y + 1] += z; | |
| − | + | } | |
| − | + | if(y + 2 < size) | |
| − | + | { | |
| − | + | if(x - 1 >= 0) | |
| − | + | deskOccupy[x - 1][y + 2] += z; | |
| − | + | if(x + 1 < size) | |
| − | + | deskOccupy[x + 1][y + 2] += z; | |
| − | + | } | |
| − | + | if(x - 2 >= 0) | |
| − | + | { | |
| − | + | if(y - 1 >= 0) | |
| − | + | deskOccupy[x - 2][y - 1] += z; | |
| − | + | if(y + 1 < size) | |
| − | + | deskOccupy[x - 2][y + 1] += z; | |
| − | + | } | |
| − | + | if(y - 2 >= 0) | |
| − | + | { | |
| − | + | if(x - 1 >= 0) | |
| − | + | deskOccupy[x - 1][y - 2] += z; | |
| − | + | if(x + 1 < size) | |
| − | + | deskOccupy[x + 1][y - 2] += z; | |
| − | + | } | |
| − | + | } | |
| − | + | void setBishop(int x, int y, int z) //increase all cells occupied by bishop at (x, y) on z | |
| − | + | { | |
| − | + | for(int ix = 0, iy1 = y - x, iy2 = y + x; ix < size; ix++, iy1++, iy2--) | |
| − | + | if(ix != x) | |
| − | + | { | |
| − | + | if((iy1 >= 0)and(iy1 < size)) | |
| − | + | deskOccupy[ix][iy1] += z; | |
| − | + | if((iy2 >= 0)and(iy2 < size)) | |
| − | + | deskOccupy[ix][iy2] += z; | |
| − | + | } | |
| − | + | } | |
| − | + | void setRook(int x, int y, int z) //increase all cells occupied by rook at (x, y) on z | |
| − | + | { | |
| − | + | for(int i = 0; i < size; i++) | |
| − | + | { | |
| − | + | if(i != x) | |
| − | + | deskOccupy[i][y] += z; | |
| − | + | if(i != y) | |
| − | + | deskOccupy[x][i] += z; | |
| − | + | } | |
| − | + | } | |
| − | + | void setKing(int x, int y, int z) //increase all cells occupied by king at (x, y) on z | |
| − | + | { | |
| − | + | for(int ix = x - 1; ix <= x + 1; ix++) | |
| − | + | for(int iy = y - 1; iy <= y + 1; iy++) | |
| − | + | if((ix >= 0)and(ix < size)and(iy >= 0)and(iy < size)and((ix != 0)or(iy != 0))) | |
| − | + | deskOccupy[ix][iy] += z; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | void setFigure(int x, int y, int z, char figure) //increase all cells occupied by figure | |
| − | + | //and (x, y) on z | |
| − | // | + | { |
| − | + | deskOccupy[x][y] += z; | |
| − | + | switch(figure) | |
| − | + | { | |
| − | + | case 'N': | |
| − | + | setKnight(x, y, z); | |
| − | + | break; | |
| − | + | case 'B': | |
| − | + | setBishop(x, y, z); | |
| − | + | break; | |
| − | + | case 'R': | |
| − | + | setRook(x, y, z); | |
| − | + | break; | |
| − | + | case 'Q': | |
| + | setBishop(x, y, z); | ||
| + | setRook(x, y, z); | ||
| + | break; | ||
| + | case 'K': | ||
| + | setKing(x, y, z); | ||
| + | break; | ||
| + | } | ||
} | } | ||
| − | + | bool putFigure(int x, int y, char figure) //place figure on desk and update occupied cells | |
| − | + | { | |
| − | + | if(deskFigures[x][y] > 0) | |
| − | + | return false; | |
| − | + | deskFigures[x][y] = figure; | |
| − | + | if(stackIsUsed) | |
| − | + | s -> push_back(make_pair(x, y)); | |
| − | + | setFigure(x, y, 1, figure); | |
| − | + | f++; | |
| − | + | return true; | |
| − | + | } | |
| − | + | int cellsLeft() //amount of cells after pointer | |
| − | + | { | |
| − | + | return (size - y) * size - x; | |
| − | + | } | |
| − | + | bool putNextFree(char figure) //attempt to put figure on the next free(and not occupied) place | |
| − | + | { | |
| − | + | if(y >= size) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | int | ||
| − | |||
| − | |||
| − | bool | ||
| − | |||
| − | if( | ||
return false; | return false; | ||
| − | + | while(deskOccupy[x][y] > 0) | |
| − | + | { | |
| − | + | if(++x == size) | |
| − | + | { | |
| − | } | + | if(++y == size) |
| − | + | return false; | |
| − | + | x = 0; | |
| − | + | } | |
| − | + | } | |
| − | + | return putFigure(x, y, figure); | |
| − | + | } | |
| − | + | void removeFigure(int x, int y) //remove figure from (x, y) | |
| − | + | { | |
| − | + | if(deskFigures[x][y]!=0) | |
| − | + | setFigure(x, y, -1, deskFigures[x][y]); | |
| − | + | deskFigures[x][y] = 0; | |
| − | + | f--; | |
| − | + | } | |
| − | + | void removeBishop(int diag, bool color, bool left) //remove bishop | |
| − | + | { | |
| − | + | if(color) //true - white, false - black | |
| − | + | { | |
| − | + | if(diag > 0) //diag - number of diagonal | |
| − | + | { | |
| − | + | int diff = left ? 0 : diag * 2; | |
| − | + | removeFigure(diff, diag * 2 - diff); | |
| − | + | removeFigure(size - diff - 1, size - diag * 2 + diff - 1); | |
| − | + | } | |
| − | + | else | |
| − | + | if(left) //determine position of the bishop on the diagonal | |
| − | + | removeFigure(0, 0); | |
| − | + | else | |
| − | } | + | removeFigure(size - 1, size - 1); |
| − | + | } | |
| − | + | else | |
| − | + | { | |
| − | + | if(diag > 0) | |
| − | + | { | |
| − | + | int diff = left ? 0 : diag * 2; | |
| − | + | removeFigure(size - diff - 1, diag * 2 - diff); | |
| − | + | removeFigure(diff, size - diag * 2 + diff - 1); | |
| − | + | } | |
| − | + | else | |
| − | + | if(left) | |
| − | + | removeFigure(0, size - 1); | |
| − | + | else | |
| − | + | removeFigure(size - 1, 0); | |
| − | + | } | |
| − | + | } | |
| − | + | void putBishop(int diag, bool color, bool left) //place bishop | |
| − | + | { | |
| − | + | if(color) | |
| − | + | { | |
| − | } | + | if(diag > 0) |
| − | + | { | |
| − | + | int diff = left ? 0 : diag * 2; | |
| − | + | putFigure(diff, diag * 2 - diff, 'B'); | |
| − | + | putFigure(size - diff - 1, size - diag * 2 + diff - 1, 'B'); | |
| − | + | } | |
| − | + | else | |
| − | + | if(left) | |
| − | + | putFigure(0, 0, 'B'); | |
| − | + | else | |
| − | + | putFigure(size - 1, size - 1, 'B'); | |
| − | + | } | |
| − | + | else | |
| − | + | { | |
| − | + | if(diag > 0) | |
| − | + | { | |
| − | + | int diff = left ? 0 : diag * 2; | |
| − | + | putFigure(size - diff - 1, diag * 2 - diff, 'B'); | |
| − | + | putFigure(diff, size - diag * 2 + diff - 1, 'B'); | |
| − | + | } | |
| − | + | else | |
| − | + | if(left) | |
| − | } | + | putFigure(0, size - 1, 'B'); |
| − | + | else | |
| − | + | putFigure(size - 1, 0, 'B'); | |
| − | + | } | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | void swapBishops(int diag, bool color, bool left) //move pair bishops to another borders | |
| − | + | { | |
| − | + | removeBishop(diag, color, left); | |
| − | + | putBishop(diag, color, not(left)); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | void | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | void figureBefore() //remove one figure from stack and change pointer to the next position after figure was placed | |
| − | + | { | |
| − | + | pair<int, int> c = s -> back(); | |
| − | + | s -> pop_back(); | |
| − | + | x = c.first; | |
| − | + | y = c.second; | |
| − | + | removeFigure(x, y); | |
| − | + | if(++x == size) | |
| − | + | { | |
| − | + | x = 0; | |
| − | + | y++; | |
| − | + | } | |
| − | |||
| − | |||
| − | |||
| − | if ( | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | void clear() //clear the desk | |
| − | + | { | |
| − | + | for(int ix = 0; ix < size; ix++) | |
| − | void | + | for(int iy = 0; iy < size; iy++) |
| − | int | + | { |
| − | + | deskFigures[ix][iy] = 0; | |
| − | + | deskOccupy[ix][iy] = 0; | |
| − | + | } | |
| − | + | x = 0; | |
| + | y = 0; | ||
| + | if(stackIsUsed) | ||
| + | s -> empty(); | ||
| + | f = 0; | ||
} | } | ||
| − | + | void show() //show the desk | |
| − | + | { | |
| − | + | a++; | |
| − | + | printf("%i:\n", a); | |
| − | + | #ifdef windows | |
| − | + | unsigned background = 4; | |
| − | + | #else | |
| − | + | printf("\x1b[31m"); | |
| − | + | char background = 47; | |
| − | + | #endif //windows | |
| − | for(int | + | for(int y = 0; y < size; y++) |
| − | + | for(int x = 0; x < size; x++) | |
| − | for(int | + | { |
| − | + | #ifdef windows | |
| − | + | SetConsoleTextAttribute(hCon, background); | |
| − | + | #else | |
| − | + | printf("\x1b[%dm", background); | |
| − | + | #endif //windows | |
| − | + | if(deskFigures[x][y] == 0) | |
| − | + | putchar(' '); | |
| − | + | else | |
| − | + | putchar(deskFigures[x][y]); | |
| − | + | #ifdef windows | |
| − | + | if(x < size - 1) | |
| − | + | background = background == 4 ? 116 : 4; | |
| − | + | else | |
| − | + | { | |
| − | + | SetConsoleTextAttribute(hCon, 7); | |
| − | + | putchar('\n'); | |
| − | + | } | |
| − | + | #else | |
| − | + | if(x < size - 1) | |
| − | + | background = background == 47 ? 40 : 47; | |
| − | + | else | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{ | { | ||
| − | + | printf("\x1b[0m\n"); | |
| − | + | if(y < size - 1) | |
| + | printf("\x1b[31m"); | ||
} | } | ||
| + | #endif // windows | ||
| + | } | ||
| + | } | ||
| + | }; | ||
| + | int m = -1; //0 for number of arrangements, 1 for all variants | ||
| − | if ( | + | unsigned lookForFigure(int size, int amount, char figure, bool show = true) //brute-force |
| − | + | { | |
| + | desk *d = new desk(size); | ||
| + | unsigned ret = 0; | ||
| + | while((d -> f > 0)or(d -> cellsLeft() >= amount)) | ||
| + | if(not(d -> putNextFree(figure))) | ||
| + | { | ||
| + | if(d -> f == amount) | ||
| + | { | ||
| + | if(show) | ||
| + | d -> show(); | ||
| + | ret++; | ||
| + | } | ||
| + | d -> figureBefore(); | ||
| + | } | ||
| + | delete d; | ||
| + | return ret; | ||
| + | } | ||
| − | + | void lookForKnight(int size, int amount) //arrangements of knights | |
| − | + | { | |
| − | + | if(m == 0) | |
| − | + | { | |
| − | + | printf("Amount of arrangements: "); | |
| − | + | if(size == 2) | |
| − | + | printf("1\n"); | |
| − | if ( | + | else |
| − | + | if(size == 4) | |
| − | + | printf("6\n"); | |
| − | if( | + | else |
| − | + | printf("2\n"); | |
| + | } | ||
| + | else | ||
| + | { | ||
| + | desk *d = new desk(size); | ||
| + | if(size == 2) | ||
| + | { | ||
| + | d -> putFigure(0, 0, 'N'); | ||
| + | d -> putFigure(0, 1, 'N'); | ||
| + | d -> putFigure(1, 0, 'N'); | ||
| + | d -> putFigure(1, 1, 'N'); | ||
| + | d -> show(); | ||
| + | } | ||
| + | else | ||
| + | if(size==4) | ||
| + | lookForFigure(size, amount, 'N'); | ||
| + | else | ||
| + | { | ||
| + | for(int x = 0; x < size; x++) | ||
| + | for(int y = 0;y < size; y++) | ||
| + | if(x + y % 2 == 0) | ||
| + | d -> putFigure(x, y, 'N'); | ||
| + | d -> show(); | ||
| + | d -> clear(); | ||
| + | for(int x = 0; x < size; x++) | ||
| + | for(int y = 0;y < size; y++) | ||
| + | if(x + y % 2 == 1) | ||
| + | d -> putFigure(x, y, 'N'); | ||
| + | d -> show(); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| − | + | void lookForBishop(int size, int amount) //arrangements of bishops | |
| − | + | { | |
| − | + | if(m == 0) | |
| − | + | printf("Amount of arrangements: %u", (unsigned) 1 << size); | |
| − | + | else | |
| − | + | { | |
| − | + | desk *d = new desk(size, false); | |
| − | } | + | bool *b = new bool[size]; |
| + | for(int dw = 0; dw < size/2; dw++) | ||
| + | { | ||
| + | d -> putBishop(dw, true, false); | ||
| + | d -> putBishop(dw, false, false); | ||
| + | } | ||
| + | int p = size - 1; | ||
| + | for(;;) | ||
| + | { | ||
| + | d -> show(); | ||
| + | while(b[p]) | ||
| + | { | ||
| + | d -> swapBishops(p % (size / 2), p < size / 2, true); | ||
| + | b[p--] = false; | ||
| + | if(p < 0) | ||
| + | return; | ||
| + | } | ||
| + | b[p] = true; | ||
| + | d -> swapBishops(p % (size / 2), p < size / 2, false); | ||
| + | p = size - 1; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void lookForRook(int size, int amount) //arrangements of rooks | ||
| + | { | ||
| + | if(m == 0) | ||
| + | printf("Amount of arrangements: %u", fact(size)); | ||
| + | else | ||
| + | lookForFigure(size, amount, 'R'); | ||
| + | } | ||
| − | if ( | + | void lookForQueen(int size, int amount) //arrangements of queens |
| − | + | { | |
| + | if(m == 0) | ||
| + | printf("Amount of arrangements: %u", lookForFigure(size, amount, 'Q', false)); | ||
| + | else | ||
| + | lookForFigure(size, amount, 'Q'); | ||
| + | } | ||
| − | + | void lookForKing(int size, int amount) //arrangements of kings | |
| − | + | { | |
| − | + | if(m == 0) | |
| − | + | printf("Amount of arrangements: %u", lookForFigure(size, amount, 'K', false)); | |
| − | + | else | |
| − | + | lookForFigure(size, amount, 'K'); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
} | } | ||
| − | + | int main() | |
| − | + | { | |
| − | + | int s = -1, f = -1; //s - size, f - figure | |
| − | + | #ifdef windows | |
| − | + | hCon = GetStdHandle(STD_OUTPUT_HANDLE); | |
| − | + | #endif // windows | |
| − | + | sizeInput: | |
| − | + | printf("Enter size of the desk:\n"); | |
| − | + | scanf("%i", &s); | |
| − | + | if((s<=0)or(s%2!=0)) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{ | { | ||
| − | + | printf("Size must be above 0 and even\n"); | |
| − | + | goto sizeInput; | |
| − | |||
} | } | ||
| − | + | modeInput: | |
| − | + | printf("Enter mode:\n\t0: Print amount of results\n\t1: Print all results\n"); | |
| − | + | scanf("%i", &m); | |
| − | + | if((m<0)or(m>1)) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{ | { | ||
| − | + | printf("Mode can be 0 or 1\n"); | |
| − | + | goto modeInput; | |
} | } | ||
| − | + | figureInput: | |
| − | + | printf("Enter figures to be placed\n\t0: Knight (N)\n\t1: Bishop (B)\n\t2: Rook (R)\n\t3: Queen (Q)\n\t4: King (K)\n"); | |
| + | scanf("%i", &f); | ||
| + | if((f<0)or(f>4)) | ||
{ | { | ||
| − | + | printf("Figure number ranges from 0 to 4\n"); | |
| − | + | goto figureInput; | |
} | } | ||
| − | + | switch(f) | |
| − | |||
{ | { | ||
| − | if( | + | case 0: |
| − | + | if(s==2) | |
| + | lookForKnight(s, 4); | ||
| + | else | ||
| + | lookForKnight(s, s *s / 2); | ||
| + | break; | ||
| + | case 1: | ||
| + | lookForBishop(s, 2 * s - 2); | ||
| + | break; | ||
| + | case 2: | ||
| + | lookForRook(s, s); | ||
| + | break; | ||
| + | case 3: | ||
| + | if(s==2) | ||
| + | lookForQueen(s, 1); | ||
| + | else | ||
| + | lookForQueen(s, s); | ||
| + | break; | ||
| + | case 4: | ||
| + | lookForKing(s, (s / 2) * (s / 2)); | ||
| + | break; | ||
} | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | </syntaxhighlight> | |
| − | + | </div> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | '''[[Козловская Анна]]''' | |
| − | |||
| − | + | '''Краткое описание алгоритма:''' Доска представлена в виде динамического массива[m;m], при выводе на экран пустые клетки обозначаются звездочками,а клетки, заполненные фигурами-буквами(каждая буква соответствует первой букве названия фигуры на английском языке). Для всех фигур написаны алгоритмы проверки на возможность расстановки фигуры. После выбора типа фигуры,используется рекурсивная функция,которая проверяет возможные расстановки через данную функцию проверки ,для данного типа фигуры. Во втором варианте работы программы,она аналитически высчитывает максимально возможное количество заданных фигур на доске.В программу встроена функция,проверяющая доску на повторные и симметричные относительно всех осей симметрии способы расстановки фигур. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | '''Инструкция:''' В меню указывается два варианта развития событий. Пользователь должен выбрать один из путей. Он вводит размер доски и тип фигуры и кол-во фигур(для первого типа работы программы).Если он выбирает первый вариант работы программы - вывод всех различных расстановок N фигур.Другой вариант работы программы максимальное число расстановок- программа выводит их количество. | |
| − | |||
| − | + | Скачать можно [http://tm.spbstu.ru/File:Chess3.rar тут]. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | '''[[Абрамов Игорь]]''' | |
| − | + | '''Алгоритм''': в зависимости от выбранного режима работы, после ввода пользователем необходимой информации о размере поля а также типе расставляемых фигур, запускается основная рекурсивная функция, которая либо подсчитывает все возможные расстановки для заданного числа фигур и выводит их в файл, либо рассчитывает максимально возможное расставляемое число фигур. В первом режиме это происходит путём установки фигуры в свободную клетку и отметки клеток, которые бьются данной фигурой, затем запускается эта же функция для оставшихся клеток и т.д., пока число поставленных фигур не дойдёт до числа, заданного пользователем. Тогда эта расстановка выводится в файл и счётчик числа расстановок увеличивается на единицу. Во втором режиме как только находится расстановка для данного количества фигур, функция завершает свою работу, увеличивается счётчик количества фигур и функция вызывается уже для большего количества фигур, пока не будет найдено максимально возможное расставляемое на данной доске число фигур. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | '''Инструкция''': В меню пользователю предлагается указать размеры доски, тип расставляемых фигур и режим работы программы. После этого, если был выбран режим вывода всех расстановок, необходимо ввести количество расставляемых фигур, после чего программа выведет на экран количество расстановок, а в файле "output.txt" появятся изображения всех расстановок. При выборе второго режима, на экран будет выведено максимальное число фигур заданного типа, которые можно расставить на данной доске. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | Ссылка для скачивания:[http://tm.spbstu.ru/File:Chess_Abramov.rar] | |
| − | |||
| − | + | <br>'''[[Нарядчиков Александр]]'''<br> | |
| − | + | '''Инструкция:''' Запустить программу, следовать указаниям, полученным в меню программы.<br> | |
| − | + | '''Описание программы:''' Шахматное поле представлено в виде двумерного массив N на M, значения N и M пользователь вводит самостоятельно, память выделяется динамически. Также пользователь выбирает тип и количество фигур на поле. В меню можно выбрать между поиском максимально возможного числа фигур на столе и поиском всех расстановок с дальнейшей записью полей в файл.<br> | |
| − | + | '''Описание алгоритма:''' При поиске всех расстановок происходит установка выбранной фигуры в свободную клетку, далее происходит маркирование тех клеток, в которые уже невозможно поставить фигуру данного типа, затем процесс происходит снова(рекурсия) пока на поле не окажется выбранное пользователем число фигур. Под конец данное поле записывается в файл и происходит поиск других возможных расстановок данного типа. В конце получаем файл со всеми вариантами расстановок и их количеством. При поиске наибольшего числа фигур на доске программа ищет расстановку для одной фигуры, затем для двух, если это возможно и т.д. С каждым разом происходит увеличение счетчика количества фигур на поле, тем самым в конце данного алгоритма мы получаем максимально возможное число данного типа фигур на доске данного размера.<br> | |
| − | + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | |
| − | + | "'''T04CHESS.CPP'''" | |
| − | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
| + | /* FILENAME: T04CHESS.CPP | ||
| + | * LAST UPDATE: 17.01.2016 | ||
| + | */ | ||
| − | + | #include "CHESS.h" | |
| − | |||
| − | + | /* Main function */ | |
| − | + | int main( void ) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{ | { | ||
| − | + | // Переменная, отвечающая за выход из меню | |
| − | + | int IsReady = 1; | |
| − | + | // Количество строк поля; количество столбцов поля | |
| − | + | int N, M; | |
| − | + | // Если идет поиск всех расстановок - 0; если идет поиск максимального числа фигур на доске - 1 | |
| + | int IsCount; | ||
| + | // Количество фигур на поле | ||
| + | int Number; | ||
| + | // Тип фигуры; количество разных расстановок; максимальное число фигур на доске | ||
| + | int tmp, count, max_value = 1; | ||
| + | // Создание указателя на тип FILE | ||
| + | FILE *F; | ||
| + | |||
| + | // Консольное меню | ||
| + | while (IsReady == 1) | ||
| + | { | ||
| + | cout << "Input figure type:\n1 - castle\n2 - bishop\n3 - knight\n4 - queen\n5 - king\n"; | ||
| + | cin >> tmp; | ||
| − | + | cout << "Input number of rows on the field:\n"; | |
| − | + | cin >> N; | |
| − | |||
| − | |||
| − | |||
| − | + | cout << "Input number of columns on the field:\n"; | |
| − | + | cin >> M; | |
| − | |||
| − | |||
| − | |||
| − | + | // Поле шахмат | |
| − | + | chess desk(N, M); | |
| − | |||
| − | |||
| − | |||
| − | + | // Обнуление поля | |
| − | + | desk.Clear(); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | cout << "Input in what mode do you want to work:\n0 - Searching for all fields variants\n1 - Searching for the maximum number of chessmen\n"; | |
| − | + | cin >> IsCount; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | // Если идет поиск всех расстановок | |
| − | + | if (IsCount == 0) | |
| − | + | { | |
| − | + | cout << "Input number of chessmen on the field:\n"; | |
| + | cin >> Number; | ||
| − | + | // Создание файла и его открытие | |
| − | + | fopen_s(&F, "chess.txt", "wt"); | |
| − | + | if ((type)(tmp + 1) == 2) | |
| − | + | fputs("Castles' fields:\n", F); | |
| − | + | else if ((type)(tmp + 1) == 3) | |
| − | + | fputs("Bishops' fields:\n", F); | |
| − | + | else if ((type)(tmp + 1) == 4) | |
| − | + | fputs("Knights' fields:\n", F); | |
| − | + | else if ((type)(tmp + 1) == 5) | |
| + | fputs("Quenns' fields:\n", F); | ||
| + | else if ((type)(tmp + 1) == 6) | ||
| + | fputs("Kings' fields:\n", F); | ||
| + | else | ||
| + | { | ||
| + | fputs("Error\n", F); | ||
| + | return 0; | ||
| + | } | ||
| + | // Закрытие файла | ||
| + | fclose(F); | ||
| − | + | // Количество разных расстановок | |
| − | + | count = desk.FillField(IsCount, (type)(tmp + 1), 0, 0, Number, 0); | |
| − | |||
| − | |||
| − | /// | + | // Открытие файла в режиме повторной записи |
| + | fopen_s(&F, "chess.txt", "at"); | ||
| + | fprintf(F, "\nNumber of fields: %i", count); | ||
| + | // Закрытие файла | ||
| + | fclose(F); | ||
| − | + | cout << "Done!\nCheck 'chess.txt' to see results\n"; | |
| − | + | } | |
| − | |||
| − | + | // Если идет поиск максимального числа фигур на доске | |
| − | + | else if (IsCount == 1) | |
| + | { | ||
| + | while (desk.FillField(IsCount, (type)(tmp + 1), 0, 0, max_value, 0)) | ||
| + | max_value++; | ||
| + | cout << "The maximum number of chessmen on the board is " << (max_value - 1) << endl; | ||
| + | max_value = 1; | ||
| + | } | ||
| − | + | // Если было введено некорректное значение для IsCount | |
| − | + | else | |
| + | cout << "Error\n"; | ||
| − | + | // Продолжение работы с программой | |
| − | + | cout << "Press '1' if you want to continue\nPress another number if you want to exit\n"; | |
| + | cin >> IsReady; | ||
| − | + | if (IsReady == 1) | |
| − | + | continue; | |
| + | else | ||
| + | exit(0); | ||
| + | } | ||
| − | + | return 0; | |
| − | + | } // End of 'main' function | |
| − | + | // END OF 'T04CHESS.CPP' FILE | |
| − | + | </syntaxhighlight> | |
| + | "'''CHESS.CPP'''" | ||
| + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | ||
| + | /* FILENAME: CHESS.CPP | ||
| + | * LAST UPDATE: 17.01.2016 | ||
| + | */ | ||
| − | + | #include "CHESS.H" | |
| − | |||
| − | + | // Количество расстановок | |
| − | + | int Result_count = 0; | |
| − | + | /* Clear field function */ | |
| − | } | + | // Обнуление поля |
| + | void chess::Clear( void ) | ||
| + | { | ||
| + | // Все клетки свободны | ||
| + | for (int i = 0; i < N; i++) | ||
| + | for (int j = 0; j < M; j++) | ||
| + | Field[i][j] = Free; | ||
| + | } // End of 'Clear' function | ||
| − | + | /* Check if the cell is available that function */ | |
| + | // Проверка, свободна и существует ли данная клетка | ||
| + | int chess::IsAvailable( int x, int y ) | ||
{ | { | ||
| − | + | if (x >= 0 && y >= 0 && x < M && y < N) | |
| − | + | if (Field[y][x] == Free) | |
| − | + | return 1; | |
| − | + | ||
| + | return 0; | ||
| + | } // End of 'IsAvailable' function | ||
| − | + | /* Output field in file function */ | |
| − | + | // Запись одного поля в файл | |
| + | void chess::OutputInFile( void ) | ||
| + | { | ||
| + | // Создание указателя на тип FILE | ||
| + | FILE *F; | ||
| − | + | // Открытие файла в режиме повторной записи | |
| − | + | fopen_s(&F, "chess.txt", "at"); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | // Переход на следующую строку файла | |
| − | + | fputc('\n', F); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | // Заполнение файла текущем полем | |
| − | + | for (int i = 0; i < N; ++i) | |
| − | + | { | |
| − | + | // '*' - свободная клетка; '#' - клетка, которая уже занята | |
| − | + | for (int j = 0; j < M; ++j) | |
| − | + | (Field[i][j] == Free || Field[i][j] == busy) ? fputc('*', F) : fputc('#', F); | |
| − | + | // Переход на следующую строку файла | |
| − | + | fputc('\n', F); | |
| + | } | ||
| − | + | // Закрытие файла | |
| − | + | fclose(F); | |
| − | + | } /* End of 'OutputInFile' function */ | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | /// | + | /* Copy desks function */ |
| + | // Копирование поля | ||
| + | void chess::Copy( chess &desk2 ) | ||
| + | { | ||
| + | for (int i = 0; i < N; i++) | ||
| + | for (int j = 0; j < M; j++) | ||
| + | desk2.Field[i][j] = Field[i][j]; | ||
| + | } // End of 'Copy' function | ||
| − | + | /* Fill field function */ | |
| + | // Заполнение полей и поиск максимального числа расстановок | ||
| + | // Chessmen_num - количество фигур, которое нужно поставить; Already_stood - количество, которое уже стоит | ||
| + | int chess::FillField( int IsCount, type set, int x, int y, int Chessmen_num, int Already_stood ) | ||
{ | { | ||
| − | + | int i, j, k, l; | |
| + | chess desk2(N, M); | ||
| − | + | // Обнуление поля | |
| − | + | desk2.Clear(); | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | // Пробег по всем оставшимся клеткам поля, начиная с той, на которой мы закончили предыдущую итерацию | |
| − | + | for (i = y; i < N; i++) | |
| − | + | for (j = ((i == y) ? x : 0); j < M; j++) | |
| − | + | { | |
| − | + | // Если клетка свободна | |
| − | + | if (Field[i][j] == Free) | |
| − | + | { | |
| − | + | // Копируем доску | |
| − | + | Copy(desk2); | |
| − | + | ||
| − | + | // Множественный выбор типа фигуры | |
| − | + | switch (set) | |
| − | + | { | |
| − | + | // Ладья | |
| − | + | case castle: | |
| − | + | for (k = 0; k < N; k++) | |
| − | + | { | |
| − | + | // Движение по столбцу | |
| − | + | if (desk2.Field[k][j] == Free) | |
| − | + | desk2.Field[k][j] = busy; | |
| − | + | // Движение по строке | |
| − | + | if (desk2.Field[i][k] == Free) | |
| − | + | desk2.Field[i][k] = busy; | |
| − | + | } | |
| − | + | break; | |
| − | + | // Слон | |
| − | + | case bishop: | |
| − | + | // Выбор и поиск наибольшей существующей на поле диагонали | |
| − | + | for (k = 1 - (N < M ? N : M); k < (N < M ? N : M); k++) | |
| − | + | { | |
| − | + | // Проход из левого верхнего угла до правого нижнего | |
| − | + | if (IsAvailable(j + k, i + k)) | |
| − | + | desk2.Field[i + k][j + k] = busy; | |
| − | + | // Проход из левого нижнего до правого верхнего | |
| − | + | if (IsAvailable(j + k, i - k)) | |
| − | + | desk2.Field[i - k][j + k] = busy; | |
| − | + | } | |
| − | + | break; | |
| − | + | // Конь | |
| − | + | case knight: | |
| − | + | // Ходы коня, k - приращение по X, l - по Y | |
| − | + | k = -2, l = 1; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | ||
| − | + | k = -2, l = -1; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | ||
| − | + | k = -1, l = 2; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | ||
| − | + | k = -1, l = -2; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | ||
| − | + | k = 1, l = 2; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | ||
| − | + | k = 1, l = -2; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | ||
| − | + | k = 2, l = 1; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | ||
| − | + | k = 2, l = -1; | |
| − | + | // Проверка возможности хода в данную клетку | |
| − | + | if (IsAvailable(j + k, i + l)) | |
| − | + | desk2.Field[i + l][j + k] = busy; | |
| − | + | break; | |
| − | + | // Ферзь | |
| − | + | case queen: | |
| − | + | for (k = 0; k < N; k++) | |
| − | + | { | |
| − | + | // Движение по столбцу | |
| − | + | if (desk2.Field[k][j] == Free) | |
| − | + | desk2.Field[k][j] = busy; | |
| − | + | // Движение по строке | |
| − | + | if (desk2.Field[i][k] == Free) | |
| − | + | desk2.Field[i][k] = busy; | |
| − | + | } | |
| − | + | ||
| − | + | // Выбор и поиск наибольшей существующей на поле диагонали | |
| − | + | for (k = 1 - (N < M ? N : M); k < (N < M ? N : M); k++) | |
| − | + | { | |
| − | + | // Проход из левого верхнего угла до правого нижнего | |
| − | + | if (IsAvailable(j + k, i + k)) | |
| + | desk2.Field[i + k][j + k] = busy; | ||
| + | // Проход из левого нижнего до правого верхнего | ||
| + | if (IsAvailable(j + k, i - k)) | ||
| + | desk2.Field[i - k][j + k] = busy; | ||
| + | } | ||
| + | break; | ||
| + | // Король | ||
| + | case king: | ||
| + | // Проход по квадрату 3 на 3, построенному центром на клетке, в которой стоит король | ||
| + | for (k = -1; k < 2; k++) | ||
| + | for (l = -1; l < 2; l++) | ||
| + | if (IsAvailable(j + k, i + l)) | ||
| + | desk2.Field[i + l][j + k] = busy; | ||
| + | break; | ||
| + | } | ||
| + | // Установка фигуры в данную клетку | ||
| + | desk2.Field[i][j] = set; | ||
| + | |||
| + | // Проверяем, что количество поставленных фигур, которое равно номеру итерации, меньше чем необходимое число фигур | ||
| + | if ((Already_stood + 1) < Chessmen_num) | ||
| + | { | ||
| + | // Если идет поиск всех расстановок, то запускаем следующий шаг | ||
| + | if (IsCount == 0) | ||
| + | desk2.FillField(IsCount, set, j, i, Chessmen_num, Already_stood + 1); | ||
| + | // Если идет поиск максимального числа фигур на доске и была найдена хотя бы одна расстоновка, то возвращаем 1 | ||
| + | else if ((IsCount == 1) && desk2.FillField(IsCount, set, j, i, Chessmen_num, Already_stood + 1)) | ||
| + | return 1; | ||
| + | } | ||
| − | + | // Если количество поставленных фигур равно необходимому числу фигур | |
| − | + | else if ((Already_stood + 1) == Chessmen_num) | |
| − | + | { | |
| − | + | // Если идет поиск всех расстановок, то увеличиваем количество расстоновок на одну и записываем поле в файл | |
| − | + | if (IsCount == 0) | |
| − | + | { | |
| − | + | Result_count++; | |
| − | + | desk2.OutputInFile(); | |
| − | + | } | |
| − | + | // Если идет поиск максимального числа фигур на доске, значит расстановка существует, возвращаем 1 | |
| − | + | else if (IsCount == 1) | |
| − | + | return 1; | |
| − | + | } | |
| − | + | } | |
| − | + | } | |
| − | + | // Если идет поиск всех расстановок, то возвращаем количество расстановок | |
| − | + | if (IsCount == 0) | |
| − | + | return Result_count; | |
| − | + | // Если идет поиск максимального числа фигур на доске, то возвращаем 0 | |
| − | + | else if (IsCount == 1) | |
| − | + | return 0; | |
| − | + | } // End of 'FillField' function | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | // END OF 'CHESS.CPP' FILE | |
| − | + | </syntaxhighlight> | |
| − | + | "'''CHESS.H'''" | |
| − | + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | |
| − | + | /* FILENAME: CHESS.H | |
| − | + | * LAST UPDATE: 17.01.2016 | |
| + | */ | ||
| − | + | #ifndef __CHESS_H_ | |
| + | #define __CHESS_H_ | ||
| − | + | #include <iostream> | |
| − | + | #include <conio.h> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | using namespace std; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | // свободен, занят, ладья, слон, конь, ферзь, король | |
| − | + | enum type { Free, busy, castle, bishop, knight, queen, king }; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | /* Chess class */ | |
| − | + | class chess | |
| − | + | { | |
| − | + | private: | |
| − | + | // Поле данных фигур | |
| − | + | type **Field; | |
| − | + | // Количество строк поля; количество столбцов поля | |
| − | + | int N, M; | |
| − | + | public: | |
| − | + | /* Default constructor */ | |
| − | + | chess( void ) | |
| − | + | { | |
| − | + | N = 8, M = 8; | |
| − | + | ||
| − | + | // Выделение памяти под массив поля | |
| − | + | Field = new type*[N]; | |
| − | + | for (int i = 0; i < N; i++) | |
| − | + | Field[i] = new type[M]; | |
| − | + | } | |
| − | + | ||
| − | + | /* Class constructor */ | |
| − | + | chess( int _N, int _M ) : N(_N), M(_M) | |
| − | + | { | |
| − | + | // Выделение памяти под массив поля | |
| − | + | Field = new type* [N]; | |
| − | + | for (int i = 0; i < N; i++) | |
| − | + | Field[i] = new type [M]; | |
| − | + | } | |
| − | + | ||
| − | + | /* Class destructor */ | |
| − | + | ~chess( void ) | |
| − | + | { | |
| − | + | // Чистка памяти | |
| − | + | for (int i = 0; i < N; i++) | |
| − | + | delete[] Field[i]; | |
| − | + | delete[] Field; | |
| − | + | } | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | /* Clear field function */ | |
| − | + | void Clear( void ); | |
| − | + | ||
| − | + | /* Check if the cell is available that function */ | |
| − | + | int IsAvailable( int x, int y ); | |
| − | + | ||
| − | + | /* Output field in file function */ | |
| − | + | void OutputInFile( void ); | |
| − | + | ||
| − | + | /* Copy desks function */ | |
| − | + | void Copy( chess& desk2 ); | |
| − | + | ||
| − | + | /* Fill field function */ | |
| − | } | + | int FillField ( int IsCount, type set, int x, int y, int Chessmen_num, int Already_stood); |
| + | }; // end of 'chess' class | ||
| + | |||
| + | #endif /*__CHESS_H_ */ | ||
| + | // END OF 'CHESS.H' FILE | ||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
| + | [http://tm.spbstu.ru/File:T04CHESS.7z Скачать архив] | ||
| + | <br> | ||
| + | |||
| + | |||
| + | '''[[Рубинова Раиса]]''' | ||
| + | |||
| + | '''Основная идея программы''': программа позволяет выводить на экран всевозможные расстановки n однотипных фигур на шахматной доске размером n*n так, чтобы ни одна из фигур не била другую. | ||
| + | |||
| + | Скачать можно [http://tm.spbstu.ru/File:Mode.rar тут]. | ||
| + | |||
| + | <div class="mw-collapsible mw-collapsed" style="width:100%" > | ||
| + | <syntaxhighlight lang="cpp" line start="1" enclose="div"> | ||
| + | #include <iostream> | ||
| + | |||
| + | int S; /// Переменная отвечающая за размер доски. | ||
| + | |||
| + | int **B; /// Двумерный массив, отображающий шахматную доску. | ||
| + | int R = 0; /// Количество решений. | ||
| + | int var, varf, Number,n,l=0; /// Переменные, отвечающие за выбор пользователя и за количество фигур, которые нужно расставить. | ||
| − | + | using namespace std; | |
| − | |||
| − | '''Идея алгоритма''': Основная идея заключается в присваиванию клетке 1 из 3 значений, пустая клетка, битая клетка или клетка, в которой стоит фигура. | + | void NewMas() |
| − | В точку ставится фигура, дальше маркируются поля, в которые уже невозможно поставить фигуру, затем мы ставим следующую фигуру и снова маркируем поля, в которые не можем ничего поставить и так далее до нужного пользователю числа фигур. Поиск максимального числа это попытка поставить на доску как можно больше фигур, он пользуется алгоритмами первого пункта. | + | { |
| + | B = new int *[S]; | ||
| + | for (int i=0; i<S; ++i) | ||
| + | { | ||
| + | B[i]= new int [S]; | ||
| + | } | ||
| + | for (int i=0; i<S; ++i) | ||
| + | { | ||
| + | for (int k=0; k<S; ++k) | ||
| + | { | ||
| + | B[i][k]=0; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | void showBoard() /// Функция, которая выводит на экран доску с. | ||
| + | { | ||
| + | for (int a=0; a<S; ++a) | ||
| + | { | ||
| + | for (int b=0; b<S; ++b) | ||
| + | { | ||
| + | cout << B[a][b] << " "; | ||
| + | } | ||
| + | cout << '\n'; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | bool checkQ (int a, int b) | ||
| + | { | ||
| + | for(int i=0; i<a; ++i) /// Проверка столбца, в который мы хотим поставить ферзя; | ||
| + | { | ||
| + | if(B[i][b]) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | for(int i=1; i<=a&&b-i>=0; ++i) /// Проверка диагонали влево-вверх; | ||
| + | { | ||
| + | if(B[a-i][b-i]) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | for(int i=1; i<=a&&b+i<S; i++) /// Проверка диагонали вправо-вверх; | ||
| + | { | ||
| + | if(B[a-i][b+i]) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | |||
| + | bool checkR (int a, int b) | ||
| + | { | ||
| + | for(int i=0; i<a; ++i) /// Проверка столбца, в который мы хотим поставить ладью; | ||
| + | { | ||
| + | if(B[i][b]) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | |||
| + | bool checkE (int a, int b) | ||
| + | { | ||
| + | for(int i=1; i<=a&&b-i>=0; ++i) /// Проверка диагонали влево-вверх; | ||
| + | { | ||
| + | if(B[a-i][b-i]) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | for(int i=1; i<=a&&b+i<S; i++) /// Проверка диагонали вправо-вверх; | ||
| + | { | ||
| + | if(B[a-i][b+i]) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | |||
| + | bool checkH (int a, int b) | ||
| + | { | ||
| + | if (((b+2)<S)&&((a+1)<S)&&(B[a+1][b+2])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((b-2)>=0)&&((a+1)<S)&&(B[a+1][b-2])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-1)>=0)&&((b+2)<S)&&(B[a-1][b+2])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-1)>=0)&&((b-2)>=0)&&(B[a-1][b-2])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a+2)<S)&&((b+1)<S)&&(B[a+2][b+1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a+2)<S)&&((b-1)>=0)&&(B[a+2][b-1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-2)>=0)&&((b+1)<S)&&(B[a-2][b+1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-2)>=0)&&((b-1)>=0)&&(B[a-2][b-1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | |||
| + | bool checkK (int a, int b) | ||
| + | { | ||
| + | if (((a+1)<S)&&((b+1)<S)&&(B[a+1][b+1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a+1)<S)&&(B[a+1][b])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a+1)<S)&&((b-1)>=0)&&(B[a+1][b-1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-1)>=0)&&((b-1)>=0)&&(B[a-1][b-1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-1)>=0)&&((b+1)<S)&&(B[a-1][b+1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-1)>=0)&& (B[a-1][b])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a+1)<S)&&(B[a][b+1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | if (((a-1)>=0)&&(B[a][b-1])) | ||
| + | { | ||
| + | return false; | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | |||
| + | |||
| + | void Queen(int a) /// a - номер очередной строки в которую нужно поставить очередного ферзя. | ||
| + | { | ||
| + | if(a==S) | ||
| + | { | ||
| + | showBoard(); | ||
| + | std::cout << ++R << "\n\n"; | ||
| + | return; | ||
| + | } | ||
| + | for(int i=0; i<Number; ++i) | ||
| + | { | ||
| + | if(checkQ(a, i)) | ||
| + | { | ||
| + | B[a][i] = 1; | ||
| + | Queen(a+1); | ||
| + | B[a][i] = 0; | ||
| + | } | ||
| + | } | ||
| + | return; | ||
| + | } | ||
| + | |||
| + | void Rook (int a) | ||
| + | { | ||
| + | if(a==S) | ||
| + | { | ||
| + | showBoard(); | ||
| + | std::cout << ++R << "\n\n"; | ||
| + | return; | ||
| + | } | ||
| + | for(int i=0; i<Number; ++i) | ||
| + | { | ||
| + | if(checkR(a, i)) | ||
| + | { | ||
| + | B[a][i] = 1; | ||
| + | Rook(a+1); | ||
| + | B[a][i] = 0; | ||
| + | } | ||
| + | } | ||
| + | return; | ||
| + | } | ||
| + | |||
| + | void Elephant (int a) | ||
| + | { | ||
| + | if(a==S) | ||
| + | { | ||
| + | showBoard(); | ||
| + | std::cout << ++R << "\n\n"; | ||
| + | return; | ||
| + | } | ||
| + | for(int i=0; i<Number; ++i) | ||
| + | { | ||
| + | if(checkE(a, i)) | ||
| + | { | ||
| + | B[a][i] = 1; | ||
| + | Elephant(a+1); | ||
| + | B[a][i] = 0; | ||
| + | } | ||
| + | } | ||
| + | return; | ||
| + | } | ||
| + | |||
| + | void Horse (int a, int i) | ||
| + | { | ||
| + | if(a==S) | ||
| + | { | ||
| + | showBoard(); | ||
| + | std::cout << ++R << "\n\n"; | ||
| + | return; | ||
| + | } | ||
| + | for(int i=0; i<Number; ++i) | ||
| + | { | ||
| + | if(checkH(a, i)) | ||
| + | { | ||
| + | B[a][i] = 1; | ||
| + | Horse(a+1, i); | ||
| + | B[a][i] = 0; | ||
| + | } | ||
| + | } | ||
| + | return; | ||
| + | } | ||
| + | |||
| + | void King (int a, int i) | ||
| + | { | ||
| + | if(i==S) | ||
| + | { | ||
| + | showBoard(); | ||
| + | std::cout << ++R << "\n\n"; | ||
| + | return; | ||
| + | } | ||
| + | if(a==S) | ||
| + | { | ||
| + | showBoard(); | ||
| + | std::cout << ++R << "\n\n"; | ||
| + | return; | ||
| + | } | ||
| + | for(int a=0; a<Number; ++a) | ||
| + | { | ||
| + | if(checkK(a, i)) | ||
| + | { | ||
| + | B[a][i] = 1; | ||
| + | King(a, i+1); | ||
| + | B[a][i] = 0; | ||
| + | } | ||
| + | } | ||
| + | return; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | cout << "Welcome! Enter the size of the board" << endl; | ||
| + | cin >> S; | ||
| + | NewMas(); | ||
| + | cout << "What do you want to do: see all variants for max number (enter 1) or for your number (enter 2)" << endl; | ||
| + | cin >> var; | ||
| + | cout << "Choose the figure (1-queen; 2-rook; 3-elephant; 4-horse; 5-king)" << endl; | ||
| + | cin >> varf; | ||
| + | if ((var==1)&&(varf==1)) | ||
| + | { | ||
| + | Number=S; | ||
| + | Queen(0); | ||
| + | return 0; | ||
| + | } | ||
| + | if ((var==1)&&(varf==2)) | ||
| + | { | ||
| + | Number=S; | ||
| + | Rook(0); | ||
| + | return 0; | ||
| + | } | ||
| + | if ((var==1)&&(varf==3)) | ||
| + | { | ||
| + | Number=S; | ||
| + | Elephant(0); | ||
| + | return 0; | ||
| + | } | ||
| + | if ((var==1)&&(varf==4)) | ||
| + | { | ||
| + | Number=S; | ||
| + | Horse(0,0); | ||
| + | return 0; | ||
| + | } | ||
| + | if ((var==1)&&(varf==5)) | ||
| + | { | ||
| + | Number=S; | ||
| + | King(0,0); | ||
| + | return 0; | ||
| + | } | ||
| + | if (var==2) | ||
| + | { | ||
| + | cout << "Enter the number of figures" << endl; | ||
| + | cin >> n; | ||
| + | if (varf==1) | ||
| + | { | ||
| + | Number=n; | ||
| + | Queen(0); | ||
| + | //if (i==n) {showBoard();} | ||
| + | return 0; | ||
| + | } | ||
| + | if (varf==2) | ||
| + | { | ||
| + | Number=n; | ||
| + | Rook(0); | ||
| + | return 0; | ||
| + | } | ||
| + | if (varf==3) | ||
| + | { | ||
| + | Number=n; | ||
| + | Elephant(0); | ||
| + | return 0; | ||
| + | } | ||
| + | if (varf==4) | ||
| + | { | ||
| + | Number=n; | ||
| + | Horse(0,0); | ||
| + | return 0; | ||
| + | } | ||
| + | if (varf==5) | ||
| + | { | ||
| + | Number=n; | ||
| + | King(0,0); | ||
| + | return 0; | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | |||
| + | </syntaxhighlight> | ||
| + | </div> | ||
| + | |||
| + | |||
| + | '''[[Уманский Александр]]''' | ||
| + | |||
| + | '''Работа программы''': Программа предлагает 2 режима работы 1 режим это нахождение для 1 из 5 фигур таких расстановок L фигур, на доске M*N, что они не бьют друг друга, второй режим возможно найти максимальное число фигур, которое можно расставить на этом поле, чтобы они не били друг друга. | ||
| + | |||
| + | '''Идея алгоритма''': Основная идея заключается в присваиванию клетке 1 из 3 значений, пустая клетка, битая клетка или клетка, в которой стоит фигура. | ||
| + | В точку ставится фигура, дальше маркируются поля, в которые уже невозможно поставить фигуру, затем мы ставим следующую фигуру и снова маркируем поля, в которые не можем ничего поставить и так далее до нужного пользователю числа фигур. Поиск максимального числа это попытка поставить на доску как можно больше фигур, он пользуется алгоритмами первого пункта. | ||
Скачать можно [http://mech.spbstu.ru/File:Ch.rar тут]. | Скачать можно [http://mech.spbstu.ru/File:Ch.rar тут]. | ||
| + | |||
| + | |||
| + | |||
| + | '''[[Капитанюк Светлана]]''' | ||
| + | |||
| + | '''Краткое описание алгоритма''': Доска представлена в виде динамического массива. Если в клетке присутствует фигура, то тогада она обозначается '+', если же клетка осталась путсая, то тогда '0'. | ||
| + | |||
| + | '''Инструкция''': пользователь вводит размер доски, далее он выбирает то действие, которое он хотел бы выполнить: посчитать максимальное число возможных фигур на данной доске, или же расставить фигуры так, чтобы они не били друг друга. | ||
| + | |||
| + | Скачать можно [http://tm.spbstu.ru/File:Chess_03.zip тут]. | ||
| + | |||
| + | '''[[Демченко Артём]]''' | ||
| + | |||
| + | '''Основная идея программы''': Программа подсчитывает и выводит расстановку указанного кол-ва фигур на указанном поле и второй опицей выводит максимальную расстановку на поле размером size*size | ||
| + | |||
| + | Скачать можно [[:File:Chess.zip]] | ||
| + | |||
| + | '''[[Гильманов Илья]]''' | ||
| + | |||
| + | '''Щсновная идея программы''': пользователь вводит размер доски MxM , тип фигур, их количество. Программа рассчитывает максимально возможное количество фигур , которые можно расположить на доске, чтобы они не били друг друга. | ||
| + | |||
| + | Скачать можно [http://mech.spbstu.ru/File:CheEeeSss.rar здесь] | ||
