2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Код Давинчи
Сообщение14.02.2014, 22:18 
Заслуженный участник
Аватара пользователя


15/10/08
7392
Можно зафиксировать число вращений и находить для оных множество достижимых состояний. Потом прибавлять по вращению и находить, находить, находить... И если вдруг окажется, что все возможные состояния покрываются ранее уже продемонстрированной оценки сверху, то оный факт и даст нам искомое.

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


23/07/08
7032
Харьков
Утундрий, погодите... мне вдруг показалось, что от состояния 12345678901234567890... (и многих других, конечно) можно перейти к нулевому только за $n$ ходов (ну, чуть меньше, учитывая, что некоторые колеса уже нули; это фигня).

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


15/10/08
7392
Нельзя ли по-конкретнее? Если найдётся хоть одно состояние, которое не перевести в заказанное менее чем за $n$ ходов, то это уже результат. Впрочем, сильно зависящий от соотношения количества символов и количества колёс.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение15.02.2014, 00:41 


05/09/12
2292
svv, напишите исходное состояние без нулей, длиннее 9 цифр, и я перейду меньше, чем за $n$ ходов, оставаясь в рамках условий задачи.

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


23/07/08
7032
Харьков
Так я сильно не настаиваю. :D

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение15.02.2014, 01:16 


05/09/12
2292
Алгоритм навскидку (не факт, что минимизирующий число вращений):
1) рассматриваем массив цифр, ищем каких больше всего, допустим, их $k$. Вычитаем из $n$ $k-1$ - получаем нужное число вращений.
2) рассматриваем отдельно каждый интервал между позициями тех цифр, количество которых максимально - по логике пункта 1. До тех пор, пока в интервалах не останется максимум по одной цифре каждого вида.
ЗЫ если у нас получилось на определенном шаге равное количество разных цифр - пробежать оба варианта до самого конца (как граф) и из всех веток выбрать с минимумом вращений.

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


10/05/13
251
Что-то подсказывает, что это задача динамического программирования.

 Профиль  
                  
 
 Re: Код Давинчи
Сообщение15.02.2014, 17:16 


05/09/12
2292
Мой алгоритм не дает минимальное количество вращений - например, на последовательности $23332$ он даст $3$ вращения (крайние двойки до троек и хором все тройки до нулей), а минимум - $2$ (тройки до двоек и двойки до нулей). Но если искать не максимум, а просто перебирать все варианты, тогда конечно будет достигнут минимум. Правда, по первому впечетлению, это будет не быстро и не оптимально.

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


15/10/08
7392
_Ivana в сообщении #826857 писал(а):
на последовательности 23332 он даст 3 вращения

На практике их и будет три.
_Ivana в сообщении #826857 писал(а):
тройки до двоек и двойки до нулей

Для осуществления этого движения надо мутантом быть...

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


05/09/12
2292
Не знаю насчет мутантом, а условию задачи эти два движения вполне удовлетворяют. Так что на практике при таких исходных данных их и будет два.

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


23/07/08
7032
Харьков
Мутанты — это хорошо. Собственно, мы здесь все мутанты.

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


15/10/08
7392
Погодите, а он "переламывается" или по нему просто пояски крутятся?

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


22/11/10
1124
Любопытная задача. Можно свести к динамическому программированию. Получится полиномиальный алгоритм. Степень, правда, не очень ...
Прежде всего, отметим, что все эти повороты коммутируют, посему можно сначала провести все повороты, в которых самым левым будет 1 колесо. Потом второе и т.д. Далее, замечаем, что если у двух "вложенных" поворотов общее граничное колесо, то их можно заменить на два "непересекающихся" по колесам поворота . Например, два поворота колес 1-2-3-4-5 и 3-4-5 можно заменить на 1-2 и 3-4-5. Отсюда вытекает, что каждое конкретное колесо может быть граничным не более двух раз, причем если два раза - то один раз левым и один раз правым. Отсюда вытекает, что определяющим является набор не столько чисел в начальной расстановке, сколько разностей между соседними колесами (по модулю 10 или чего-там-надо). Ну и, наконец, надо заметить, что порядок в этих разностях несущественный. Важна лишь "брутто-формула": сколько разностей равны 1, сколько 2 и т.д. А это прямая дорога к ДП.
Пример. Пусть исходная позиция на колесах 25341. Надо привести ее к 00000. Для определенности будем брать разности с левым колесом. Тогда добавляем фиктивное "самое левое колесо" с 0. Получим 025341. После этого последовательность разностей получится 2 3 -2 1 -3
Между прочим, отсюда видно, что потребуется 3 поворота. Каждый поворот одну разность увеличивает, а другую уменьшает на одно и то же число. Поэтому выгодно искать пары разностей отличающихся знаком. Таких тут 2. Итак сначала крутим первые два колеса. Получим 03341. Потом крутим колеса 2-3-4. Получим 00011. Ну и наконец последние пару колес.
Проверим, что ничего не изменится, если разности переставить как угодно. Например
1 -3 - 2 2 3. Это соответствует начальной позиции 1 8 6 8 1. Тут уж ясно что делать. И тоже 3 поворота.

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

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



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

Сейчас этот форум просматривают: Andrey A


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

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