На рисунке изображена клетчатая доска. Будем считать, что фишка на этой доске видит другую фишку, если они расположены либо в одной вертикали, либо в одной горизонтали, причём между ними нет границ доски. Сколькими способами можно расставить 5 фишек на этой доске так, чтобы никакие две из них не видели друг друга?
https://uchebnik.mos.ru/cms/system/atomic_objects/files/011/970/643/original/6-7.png
function countWays(board, row, col, placed)
if placed = 5 // Если все 5 фишек размещены, считаем эту комбинацию валидной и увеличиваем счётчик
return 1
if col = 5 // Если достигли конца строки, переходим к следующей строке
return countWays(board, row + 1, 0, placed)
if row = 5 // Если достигли конца доски, возвращаем 0 (не валидная комбинация)
return 0
count = 0 // Инициализируем счётчик
for i = row to 5 // Перебираем все клетки доски, начиная с текущей строки и столбца
for j = col to 5
if isSafe(board, i, j) // Проверяем, видит ли фишка другую фишку по горизонтали и вертикали
board[i][j] = 1 // Размещаем фишку на доску
count += countWays(board, i, j + 1, placed + 1) // Рекурсивно размещаем следующую фишку на доску
board[i][j] = 0 // Убираем фишку с доски
end if
end for
end for
return count // Возвращаем общее количество валидных комбинаций
end function
function isSafe(board, row, col)
// Проверяем, видит ли фишка другие фишки по горизонтали и вертикали
for i = 0 to 4
if board[row][i] = 1 or board[i][col] = 1
return false
end if
end for
return true
end function
// Инициализируем доску
board = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
// Вызываем функцию для подсчёта количества валидных комбинаций
result = countWays(board, 0, 0, 0)
// Выводим результат
print result
Этот алгоритм рекурсивно перебирает все возможные комбинации фишек на доске и использует функцию `isSafe`, чтобы проверить, видит ли фишка другие фишки по горизонтали и вертикали. Если комбинация валидна, мы увеличиваем счётчик `count` и возвращаем общее количество валидных комбинаций в конце.
Таким образом, результатом работы алгоритма будет количество валидных комбинаций фишек на доске размером 5x5, где никакие две фишки не видят друг друга.Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет