В клетках таблицы 17×13 расставлены числа 1,2,…,221 в порядке возрастания (в первой строке слева направо от 1 до 13, во второй от 14 до 26 и т.д.). Фишка начала движение из клетки с номером 1 и переходя в соседние по стороне клетки, в конце концов попала в клетку с номером 221. Найдите наименьшую возможную сумму чисел в клетках, в которых побывала фишка (включая первую и последнюю клетки).

задан 2 Янв '14 17:27

изменен 16 Янв '14 20:19

Deleted's gravatar image


126

10|600 символов нужно символов осталось
2

Есть общий метод решения такого рода задач. Предположим, что таблица заполнена какими угодно числами. Рисуем новую таблицу, а каждую клетку которой будем вписывать наименьшую возможную сумму чисел для перемещения из левой верхней клетки в данную. Эту новую таблицу можно заполнять по горизонталям. Например, для той задачи, о которой здесь идёт речь, верхняя горизонталь новой таблицы будет заполнена числами 1, 3, 6, ..., 91. Теперь заполняем вторую горизонталь. Её первое число, очевидно, равно 15. А следующее число будет равно 18: добраться до второй слева клетки второй сверху горизонтали можно либо сверху, либо справа, и понятно, что сверху добираться выгоднее, потому что получится 3+15, а не 15+15. Далее всё заполняется по такому же принципу, и на каждом шаге мы сравниваем не более чем два способа, выбирая из них оптимальный. Фактически, мы каждый раз ориентируемся на соседа слева и соседа сверху, и выбираем наименьшее из двух чисел. Итог будет написан в крайней справа нижней клетке на последнем этапе.

В данной задаче в процессе заполнения сразу будет видна закономерность оптимального движения.

ссылка

отвечен 2 Янв '14 19:23

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×3,711

задан
2 Янв '14 17:27

показан
1010 раз

обновлен
2 Янв '14 19:23

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru