Задача о шахматном коне

[Cash]

Fedya
Конечно, это все любопытно. Более того, это даже, скорее всего, и верно.
Доказать строго свои выкладки сможете?
И главный вопрос - для чего все это вы проделали?

[Fedya]

ИСН
Someone
longstreet
Cash


Очень благодарен за помощь!
Я просто попытался придумать алгоритм подсчета расстояния, если нет доски, а только координаты точек.

-- 29.08.2012, 19:00 --

Cash

Это очень сырой вариант, просто идея, которая пришла в голову. Можно, конечно, и доработать.

-- 29.08.2012, 19:02 --

Ответ на главный вопрос. Это последняя из задач которые нужно решить. И она почему-то вызвала наибольшие трудности

[longstreet]

Someone в сообщении #612070 писал(а):

Fedya в сообщении #612067 писал(а):

Боюсь, это будет весьма затруднительно.

ИСН в сообщении #612162 писал(а):

Если на формулу не рассчитываете (и правильно делаете)

А, кстати, почему? В чём именно препятствие?

[Cash]

Цитата:

Это последняя из задач которые нужно решить. И она почему-то вызвала наибольшие трудности

Я не пойму, какую именно задачу вы так решаете?

[Fedya]

Это первый и второй пункты приведенной выше задачи

[Cash]

Ну и какое отношение к данной задаче имеют ваши рассуждения?
п.2. У нас есть путь длины 3: c5-e4-f6-g8.
Есть ли путь короче? Путь длины 2 может быть? Длины 1?
Ответ на оба вопроса занимает половину строки, вместо той простыни неоформившихся мыслей, что вы привели...

[ИСН]

Один студент © писал на заказ крутилку баннеров для сайта. Он взялся за дело с размахом и для начала написал целую собственную графическую библиотеку. Потом ему не понравилось, как браузер обращается с куками, и он начал писать ещё и собственный браузер. Потом - собственную операционную систему. А потом дверь вылетела от сильного пинка, и к нему ворвался разъярённый заказчик с бейсбольной битой.
- - - - - - - -
Зачем Вы ищете алгоритм подсчета расстояния? Спрашивают ли его у нас? Нужен ли он?

[Fedya]

Cкорее всего вы правы. Но я думал суть второго пункта не в том чтобы просто найти этот путь. Это просто. А в том, чтобы показать возможность вычислить путь для произвольных двух клеток заданных шахматными координатами без использования доски

[arseniiv]

Ну да, доска нужна ровно постольку, поскольку на ней удобно клетки раскрашивать в разные цвета.

[Cash]

Там тоже без проблем. Если нам нужно из клетки $(0, 0)$ попасть в $ (m, n)$. Тогда для квадрата $0 \le m, n \le 3$ перебираем вручную. Для остальных - очевидная формула
$d(m,n)=\max ( \lceil n/2 \rceil, \lceil m/2 \rceil, \lceil (m+n)/3\rceil) + \varepsilon$,
где $\varepsilon$ равно $0$ или $1$, в зависимости от того - попадаем или не попадаем в цвет.

-- Ср авг 29, 2012 22:33:20 --

Точнее, очевидно
$d(m,n) \ge \max ( \lceil n/2 \rceil, \lceil m/2 \rceil, \lceil (m+n)/3\rceil) + \varepsilon$
Для равенства нужно еще путь подобрать, но с этим проблем быть не должно.

-- Ср авг 29, 2012 22:39:50 --

А для решения п.2 исходной задачи достаточно только показать, что
$d(m,n) \ge (m+n)/3$

[Fedya]

Хорошо, а если нам нужно из точки (k;l) попасть в точку (m;l), причем ты не знаем цвет клеточек?

-- 29.08.2012, 22:40 --

(m;n) конечно

[Cash]

Как это не знаем?

[Fedya]

Знаем, это я не того подумал. Но даже если знаем, как тогда?

[Cash]

Расстояние будет равно $d(|m-k| , |n-l|)$