2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Код Давинчи
Сообщение04.02.2014, 16:57 


10/05/13
251
Привет! Задача такая:
У вас есть устройство чтото вроде этого:
Изображение
но вместо латинских букв там находятся цифры 0-9.
За один ход можно:
Повернуть непрерывных сегмент колес в одном направлении, вверх или вниз.
Это что у вас есть.

Входные данные:
Вам дано текущее состояние устройства, вектор цифр.
И еще один вектор цифр - то состояние которые вы должны получить минимальным количеством ходов.

На выходе вы должны дать число, минимальное количество ходов.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 01:24 
Заслуженный участник
Аватара пользователя


15/10/08
11533
frankenstein в сообщении #822698 писал(а):
За один ход можно:
Повернуть непрерывных сегмент колес в одном направлении, вверх или вниз.
Это что у вас есть.

Как это будет сказать по-русски?

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 01:35 
Заслуженный участник


23/07/08
10626
Crna Gora
Непрерывных сегмент колес — это подмножество $S$ множества всех колес устройства, такое, что если колеса $a$ и $b$ принадлежат $S$, а колесо $c$ расположено между $a$ и $b$, то и $c$ принадлежит $S$.

-- Чт фев 13, 2014 00:47:08 --

Да, и таких сегмент колес за один ход не просто поворачивается в одном направлении, а еще и все его колеса поворачиваются на равное количество щелчков.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 14:15 
Заслуженный участник


27/04/09
28128
Добавлю очевидное: если все цифры написаны на колёсах в одном и том же порядке, как буквы на картинке, то задача свести $a_i$ к $b_i$ сводится к задаче сведения $a_i-b_i$ к $0$. Таким образом, кстати, ещё и количество колёс во входе присутствует только один раз.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 14:20 
Заслуженный участник


23/07/08
10626
Crna Gora
Точно! Приятное упрощение.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 14:25 
Заслуженный участник


27/04/09
28128
Следующий естественный шаг — хотя не знаю, насколько полезный для ответа — рассмотреть группу преобразований этой солонки. У неё $n$ колёс и $n-1$ делений на непрерывных сегмент колёс и два способа — вращать левый или вращать правый. Получаем базовые вращения $1_L,\ldots,(n-1)_L,1_R,\ldots,(n-1)_R$ на одну цифру, скажем, вверх, и остальные базовые вращения как их степени. Может, разложение на вращения отдельных колёс $\hat1,\ldots,\hat n$ что-то дадут?

Стоит заметить, что все эти элементы коммутируют из-за особенностей этого разложения и вращений отдельных колёс.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 14:43 
Заслуженный участник


23/07/08
10626
Crna Gora
Я тоже добавлю очевидное. В формулировке arseniiv (а, следовательно, и в оригинальной) для $n$ колёс достаточно $n$ ходов. Поворачиваем первое колесо, пока оно не совпадет со вторым. Дальше вращаем первые два колеса, пока не совпадут с третьим. На последнем шаге крутим все колёса вместе, устанавливая нули.

Но если кто-то хочет $o(n)$... :wink:

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 19:32 
Заслуженный участник
Аватара пользователя


15/10/08
11533
То есть загадочный "непрерывных сегмент колёс" это просто несколько поясков, поворачивающихся вместе... Понятно, что ходов нужно не более количества поясков, но вероятно (вследствие самого факта существования задачи) минимальное необходимое значение ещё несколько меньше.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 19:37 
Заслуженный участник


23/07/08
10626
Crna Gora
... и не перемежаемых (или -ющихся?) не поворачивающимися вместе с ними.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 19:42 
Заслуженный участник
Аватара пользователя


15/10/08
11533
Вообще-то, поскольку устройство так и просится в лапы (выгодно отличаясь тем от своеобычных в олимпиадном разделе хроносинкластических семнадцатимерных летающих пингвинов), то возникает сильное желание ограничить допустимые движения до проворота левой и правой части относительно одной плоскости. Плоскость, понятно, можно выбирать произвольно.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 19:52 
Заслуженный участник


23/07/08
10626
Crna Gora

(Оффтоп)

В Гугле (или другом поисковике) в разделе Картинки наберите Cryptex. Так эта штука называется. Увидите много вкусных картинок.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение13.02.2014, 19:56 
Заслуженный участник
Аватара пользователя


15/10/08
11533

(Оффтоп)

А, так это что-то известное! Нет, смотреть не буду. Меньше сил потрачу на забывание.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение14.02.2014, 13:12 


10/05/13
251
arseniiv в сообщении #825869 писал(а):
Добавлю очевидное: если все цифры написаны на колёсах в одном и том же порядке, как буквы на картинке, то задача свести $a_i$ к $b_i$ сводится к задаче сведения $a_i-b_i$ к $0$. Таким образом, кстати, ещё и количество колёс во входе присутствует только один раз.

Да, упрощение очевидное. Но что делать после того как вы вычислили $a_i-b_i$. Будут ли гарантировать все описанные методы что, полученное решение будет минимальным из множества всех решений.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение14.02.2014, 13:43 
Заслуженный участник


27/04/09
28128
Вообще-то, был описан один метод:
svv в сообщении #825890 писал(а):
Поворачиваем первое колесо, пока оно не совпадет со вторым. Дальше вращаем первые два колеса, пока не совпадут с третьим. На последнем шаге крутим все колёса вместе, устанавливая нули.
и он не гарантирует минимальность числа ходов, что тоже написано. :wink:

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение14.02.2014, 20:49 
Заслуженный участник


23/07/08
10626
Crna Gora
Ну, а второй очевидный метод — это просто отдельное вращение по одному всех $n$ колес. :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group