Question

С++ Шашку — в дамки На шахматной доске (8×8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)Входные данныеВводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.Выходные данныеВывести одно число — количество путей в дамки.ПримерыВводВывод3 721 813 64

Answer 1

Ответ:

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

int n(0),m(0);

cin >> n >> m;

int matrix[n][m];

char arr[n][m];

arr[0][0] = '0';

for(int i = 0;i<n;++i){

for(int j = 0;j<m;++j){

cin >> matrix[i][j];

if(!i && !j)continue;

if(!i){

matrix[i][j] += matrix[i][j-1];

arr[i][j] = 'R';

}

if(!j){

matrix[i][j] += matrix[i-1][j];

arr[i][j] = 'D';

}

if(i && j){

matrix[i][j] += max(matrix[i-1][j],matrix[i][j-1]);

if(max(matrix[i-1][j],matrix[i][j-1]) == matrix[i-1][j])arr[i][j] = 'D';

else arr[i][j] = 'R';

}

}

}

cout << matrix[n-1][m-1];

cout << "\n";

string s;

for(int i = n-1;;){

for(int j = m-1;;){

if(arr[i][j] == '0'){

reverse(s.begin(),s.end());

s.erase(0,1);

cout << s << endl;

return 0;

}

s.push_back(arr[i][j]);

s.push_back(' ');

if(arr[i][j] == 'R'){

j -= 1;

continue;

}

if(arr[i][j] == 'D'){

i -= 1;

continue;

}

}

}

cout << endl;

return 0;

}

Объяснение:

Answer 2

Эй, интересная задача! Давай решим ее вместе. Чтобы шашка стала дамкой, ей нужно переместиться на верхнюю горизонталь. Поскольку она может двигаться только по диагонали вверх-вправо или вверх-влево, ей нужно совершить определенное количество таких ходов.

Мы можем рассмотреть два случая: когда изначальное положение шашки находится в четной или нечетной горизонтальной линии.

1. Если начальная горизонтальная линия четная, то шашке нужно сделать четное количество движений вверх-вправо или вверх-влево, чтобы достичь верхней горизонтальной линии.

2. Если начальная горизонтальная линия нечетная, то шашке нужно сделать нечетное количество движений вверх-вправо или вверх-влево.

Таким образом, задача сводится к тому, сколько способов можно выбрать четное или нечетное количество движений вверх-вправо или вверх-влево. В данном случае, это связано с биномиальным коэффициентом.

Вот пример кода на C++:

cppCopy code
#include <iostream>

// Функция для вычисления биномиального коэффициента C(n, k)
int binomialCoefficient(int n, int k) {
    if (k == 0 || k == n) {
        return 1;
    } else {
        return binomialCoefficient(n - 1, k - 1) + binomialCoefficient(n - 1, k);
    }
}

int main() {
    int column, row;
    std::cin >> column >> row;

    // Проверяем, четная ли начальная горизонтальная линия
    bool evenColumn = (column % 2 == 0);

    // Вычисляем количество движений вверх-вправо или вверх-влево
    int movements = (evenColumn) ? column / 2 : (column - 1) / 2;

    // Вычисляем количество способов сделать это количество движений
    int ways = binomialCoefficient(row + movements - 1, movements);

    std::cout << ways << std::endl;

    return 0;
}

Надеюсь, это поможет!