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