Как можно переместить ладью в правый нижний угол квадрата, чтобы максимизировать сумму чисел в клетках, в которых ладья останавливалась? Квадрат имеет размер 15×15 клеток, в каждой записано целое число. Ладья начинает в левом верхнем углу и может двигаться только вправо или вниз.
Подробный ответ:
Объяснение: Чтобы найти максимальную сумму чисел, при которой ладья переместится в правый нижний угол квадрата, можно воспользоваться динамическим программированием. Для этого создадим вспомогательный массив с теми же размерами, что и исходный квадрат, и будем заполнять его по следующему правилу:
1. Для клеток первой строки и первого столбца вспомогательного массива, значения будут равны сумме значений предыдущих клеток.
2. Для остальных клеток вспомогательного массива, значение в каждой клетке будет равно максимальному значению из двух возможных путей: сверху или слева от текущей клетки плюс значение текущей клетки исходного квадрата.
После заполнения вспомогательного массива, максимальная сумма чисел, которую можно получить, будет находиться в правом нижнем углу вспомогательного массива.
Пример использования: Пусть исходный квадрат имеет размер 3×3 и заполнен следующими числами:
| 1 | 2 | 3 |
|—|—|—|
| 4 | 5 | 6 |
| 7 | 8 | 9 |
С помощью динамического программирования получим следующий вспомогательный массив:
| 1 | 3 | 6 |
|—|—|—|
| 5 | 8 | 12 |
| 12 | 15 | 21 |
Максимальная сумма чисел, которую можно получить, и переместить ладью в правый нижний угол квадрата равна 21.
Совет: Для лучшего понимания алгоритма, можно взять квадрат меньшего размера и проследить шаги вручную. Также можно рассмотреть способы оптимизации алгоритма для более быстрого вычисления.
Упражнение: В квадрате размером 5×5 с числами:
| 1 | 3 | 5 | 7 | 9 |
|—|—|—|—|—|
| 2 | 4 | 6 | 8 | 10 |
| 11 | 13 | 15 | 17 | 19 |
| 12 | 14 | 16 | 18 | 20 |
| 21 | 23 | 25 | 27 | 29 |
Какая максимальная сумма чисел будет получена, если переместить ладью в правый нижний угол?