Тема 18. Обработка вещественных выражений в электронных таблицах

18.06 Шахматные фигуры

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела обработка вещественных выражений в электронных таблицах
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#6333

Ладья ходит по шахматной доске размера 10 × 10  . Найдите модуль разности между количеством путей из точки (1,1)  в точку (3,7)  и количеством путей из точки (1,1)  в точку (4,5)  (первое число — номер строки, второе — номер столбца), если ладья может ходить только вверх и вправо.

Показать ответ и решение

Решение руками

Сначала посчитаем, количество путей в ячейки

(1, 1),(1, 2),...,(1, 10),

(2, 1),(3, 1),...,(10, 1).

Пусть Aij  — количество путей, ведущих в клетку (i,j ).

A11 = 1  (т.к. мы стартуем из этой клетки),

A12 = A11,

A   = A   + A   ,...,A    = A   + A   + ...+  A  .
 13     11     12      110     11     12         19

Аналогично с A21, A31,...,A101.  Далее заметим, что количество способов попасть в любую клетку, это сумма всех клеток, которые находятся ниже и левее данной.

Динамически посчитаем все остальные Aij  способом, описанным выше, и ответом будет |A37 − A45| .

Пример программы на Python  для решения данной задачи. В программе все индексы на 1  меньше, т.к. нумерация начинается с 0  .

 

Решение программой

dp = []
for i in range(10):
    a = []
    for j in range(10):
        a.append(0)
    dp.append(a)
# dp[i][j] - количество способов прийти в клетку с номерами i и j
# [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, 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, 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, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# т.к. в питоне индексация с нуля, то dp[0][0] будет обозначать клетку
# с номером строки 1 и с номером столбца 1
dp[9][0] = 1  # сколько существует способов попасть из клетки (1, 1) в неё же?
# Ответ: ровно 1 способ - ничего не делать
for i in range(9, -1, -1):
    for j in range(10):
        for k in range(1, 10):
            if i == 9:
                if j - k >= 0:
                    dp[i][j] += dp[i][j - k]
            elif j == 0:
                if i + k < 10:
                    dp[i][j] += dp[i + k][j]
            else:
                if i + k < 10:
                    dp[i][j] += dp[i + k][j]
                if j - k >= 0:
                    dp[i][j] += dp[i][j - k]
# ответ
print(abs(dp[7][6] - dp[6][4]))
# выведем табличку для наглядности
print(" " * 7, end="")
for k in range(1, 11):
    print(f"{k:>10}", end="")
print()
print("-" * 112)
for i in range(10):
                                                                                                    
                                                                                                    
    for j in range(10):
        if j == 0:
            print(f"{10 - i:>10}|", end="")
        print(f"{dp[i][j]:>10}", end="")
    print()

Ответ: 271
Рулетка
Вы можете получить скидку в рулетке!