|
В клетках таблицы 17×13 расставлены числа 1,2,…,221 в порядке возрастания (в первой строке слева направо от 1 до 13, во второй от 14 до 26 и т.д.). Фишка начала движение из клетки с номером 1 и переходя в соседние по стороне клетки, в конце концов попала в клетку с номером 221. Найдите наименьшую возможную сумму чисел в клетках, в которых побывала фишка (включая первую и последнюю клетки). задан 2 Янв '14 17:27 
Dromni86 |
|
Есть общий метод решения такого рода задач. Предположим, что таблица заполнена какими угодно числами. Рисуем новую таблицу, а каждую клетку которой будем вписывать наименьшую возможную сумму чисел для перемещения из левой верхней клетки в данную. Эту новую таблицу можно заполнять по горизонталям. Например, для той задачи, о которой здесь идёт речь, верхняя горизонталь новой таблицы будет заполнена числами 1, 3, 6, ..., 91. Теперь заполняем вторую горизонталь. Её первое число, очевидно, равно 15. А следующее число будет равно 18: добраться до второй слева клетки второй сверху горизонтали можно либо сверху, либо справа, и понятно, что сверху добираться выгоднее, потому что получится 3+15, а не 15+15. Далее всё заполняется по такому же принципу, и на каждом шаге мы сравниваем не более чем два способа, выбирая из них оптимальный. Фактически, мы каждый раз ориентируемся на соседа слева и соседа сверху, и выбираем наименьшее из двух чисел. Итог будет написан в крайней справа нижней клетке на последнем этапе. В данной задаче в процессе заполнения сразу будет видна закономерность оптимального движения. отвечен 2 Янв '14 19:23 
falcao |