2014 dxdy logo

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

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





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


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

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


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

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


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

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


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

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


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

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


05/09/12
2293
Алгоритм навскидку (не факт, что минимизирующий число вращений):
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
2293
Мой алгоритм не дает минимальное количество вращений - например, на последовательности $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
2293
Не знаю насчет мутантом, а условию задачи эти два движения вполне удовлетворяют. Так что на практике при таких исходных данных их и будет два.

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


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

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


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

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


22/11/10
1138
Любопытная задача. Можно свести к динамическому программированию. Получится полиномиальный алгоритм. Степень, правда, не очень ...
Прежде всего, отметим, что все эти повороты коммутируют, посему можно сначала провести все повороты, в которых самым левым будет 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

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



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

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


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

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