Cool Folders ® :: Форум Игротека :: О зайце и матричном поле

О зайце и матричном поле

№ 1

Большой Грызь

Дата : 26-06-06, Пнд, 04:11:22

Сегодня с утра пришла в голову такая вот задача (предысторию потом расскажу, кому интересно

).

Есть поле, расчерченное в виде матрицы NxN клеток.
По полю по какой-то замысловатой траектории бегает заяц.
С каждой клетки заяц может перебежать на любую из восьми соседних клеток.

Можно пронумеровать клетки поля по рядам: первый ряд - от 1 до N, второй ряд - от N+1 до 2N и так далее до N*N.
В этом случае, как бы заяц не бегал, а максимальная разница между двумя последовательными клетками на его пути будет N+1: если он перебегает по диагонали вправо на следующий ряд или влево на предыдущий.

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

...everything is possible cause noone has to hide beyond the invisible...

О зайце и матричном поле

№ 2

kobaandrew

Дата : 13-07-06, Чтв, 02:39:14

наверное можно если использовать "ход быка", то есть когда нумерация подходит к концу строки, она продолжается вниз, а затем от конца строки к началу. Но в этом случае минимальная разница в номерах клеток будет где-нить в конце/начале строки, а максимальная наоборот в начале/конце этой же строки.
Ход быка:

1-------------------------------------------------------------------------------N
N*2-------------------------------------------------------------------------------N+1

О зайце и матричном поле

№ 3

Большой Грызь

Дата : 13-07-06, Чтв, 02:41:11

Так ведь задано:

уменьшить максимальную разницу между двумя последовательными клетками на пути зайца вне зависимости от его траектории.

А в Вашем варианте, если он с левой верхней клетки пойдёт вниз - разница будет N*2-1. А это больше N+1 уже для N=3..

Only those who attempt the absurd will achieve the impossible.. (Escher)