2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 16:26 
Fedya
Конечно, это все любопытно. Более того, это даже, скорее всего, и верно.
Доказать строго свои выкладки сможете?
И главный вопрос - для чего все это вы проделали?

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 17:57 
ИСН
Someone
longstreet
Cash


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

-- 29.08.2012, 19:00 --

Cash

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

-- 29.08.2012, 19:02 --

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

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 19:02 
Someone в сообщении #612070 писал(а):
Fedya в сообщении #612067 писал(а):
Боюсь, это будет весьма затруднительно.

ИСН в сообщении #612162 писал(а):
Если на формулу не рассчитываете (и правильно делаете)

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

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 20:00 
Цитата:
Это последняя из задач которые нужно решить. И она почему-то вызвала наибольшие трудности

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

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 20:04 
Это первый и второй пункты приведенной выше задачи

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

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

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

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 20:43 
Ну да, доска нужна ровно постольку, поскольку на ней удобно клетки раскрашивать в разные цвета.

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 21:21 
Там тоже без проблем. Если нам нужно из клетки $(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$

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 21:39 
Хорошо, а если нам нужно из точки (k;l) попасть в точку (m;l), причем ты не знаем цвет клеточек?

-- 29.08.2012, 22:40 --

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

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 21:41 
Как это не знаем?

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 21:45 
Знаем, это я не того подумал. Но даже если знаем, как тогда?

 
 
 
 Re: Задача о шахматном коне
Сообщение29.08.2012, 21:53 
Расстояние будет равно $d(|m-k| , |n-l|)$

 
 
 [ Сообщений: 29 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group