2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задачка про перестановки
Сообщение23.07.2006, 21:28 


09/04/06
12
Germany
Не уверена что можно пердложить конструктивное решение, но вдруг:

Есть Н шариков на прямой у каждого есть приписанное число ч1,..., чН - перемещаемость
Операция: соседние шарики можно менять местами, при этом перемещаемость шарика, который оказался правее исходной позиции уменьшается на 1.

Нужно: найти как поменять шарики местами так, чтобы все оказались на своих местах и перемещаемость у всех была 0 (рассматриваются только случаи когда это возможно)

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


17/10/05
3709
:evil:
Cronopio писал(а):
Нужно: найти как поменять шарики местами так, чтобы все оказались на своих местах и перемещаемость у всех была 0 (рассматриваются только случаи когда это возможно)

Уж не стоят ли они сразу на своих местах? А менее иронически, что значит шарик стоит на своем месте? Есть ли е него номер помимо чН? Или имеется в виду то же самое место, с которого шарик начал?

 Профиль  
                  
 
 
Сообщение23.07.2006, 22:46 
Заслуженный участник


09/02/06
4382
Москва
Предлагаю такой алгоритм. Берём шарик с максимальным числом перемещаемостью и начинаем его двигать слева направо, пока у него перемещаемость максимальна или не дошли до правого конца. Потом берём следующий шарик с максимальным числом перемещаемости и перемещаем слева направо, пока он не дошёл до правого конца или не потерял максимальность и т.д. Если задача имеет решение, то этот способ обнуляет все числа перемещаемости.
Только, что значит в свои места я не понял из приведённого условия задачи.

 Профиль  
                  
 
 
Сообщение23.07.2006, 22:50 


09/04/06
12
Germany
извините, плохо сформулировала

у шариков есть еще номера. Изначально первый шарик стоит на месте номер 1, на этому же месте он должен оказаться после перестановок (поэтому проблема, шарик нужно переставлять и обратно, что уменьшает перемещаемость остальных шриков, которая и так могла быть уже 0)

 Профиль  
                  
 
 
Сообщение23.07.2006, 23:05 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Все шарики изначально стоят на своих местах? Т.е. задача по сути в том, чтобы избавиться от перемещаемости, вернув в итоге все на место? Правильно ли я понял, что при смене местами двух соседних шариков перемещаемость одного уменьшается на 1 (того, который перемещается слева направо), а перемещаемость второго не меняется?

 Профиль  
                  
 
 
Сообщение23.07.2006, 23:20 


09/04/06
12
Germany
PAV
да, именно так

 Профиль  
                  
 
 
Сообщение24.07.2006, 06:41 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Поскольку задача конечна (каждая перестановка уменьшает сумму "подвижностей" на единицу), то возможен полный перебор. Полный перебор является хотя и медленным, но конструктивным алгоритмом, который либо выдаст положительный ответ, либо остановится, доказав, что решения не существует.

1) если сумма подвижностей нечетна, то (если я не ошибаюсь), решения не существует, и искать бесполезно.

2) Задачу уместно решать методами динамического программирования, это заметно сократит переборы (за счет увеличения затрат памяти).

 Профиль  
                  
 
 
Сообщение24.07.2006, 11:54 


09/04/06
12
Germany
незваный гость
Ну шариков 100, перемещаемость у всех порядка 20, суммы естественно четные (на это я поставила проверку)
А сложность алгоритма - порядка Н в степени суммарная перемещаемость... Итого: не реально
Должно быть очень сильно облегчающее пербор соображение, но я догадаться никак не могу

 Профиль  
                  
 
 
Сообщение24.07.2006, 11:57 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
А откуда такая задача, если не секрет? Просто учебная или за ней что-то более существенное стоит?

 Профиль  
                  
 
 
Сообщение24.07.2006, 12:45 


09/04/06
12
Germany
PAV
Честно говоря, скорее учебная. Задачка по программированию, с соревнований, чуть-чуть преобразованная.

Решение точно есть

 Профиль  
                  
 
 
Сообщение24.07.2006, 23:25 


21/06/06
1721
Ну а вообще задача, наверно имеет решение только в том случае, если самый правй шарик имеет самую низкую перемещаемость, то есть стоит на своем месте. Ну а дальше по моему просто элеменарно, меняем местами два соседних туда-сюда, до тех пор, пока эта перемещаемость не обнулится. Или я, что то не так понял?

 Профиль  
                  
 
 
Сообщение25.07.2006, 07:30 
Заслуженный участник


09/02/06
4382
Москва
Sasha2 писал(а):
Ну а вообще задача, наверно имеет решение только в том случае, если самый правй шарик имеет самую низкую перемещаемость, то есть стоит на своем месте. Ну а дальше по моему просто элеменарно, меняем местами два соседних туда-сюда, до тех пор, пока эта перемещаемость не обнулится. Или я, что то не так понял?

Это неверно. Например n шариков с перемещаемостью 1 для всех кроме крайней правой, а у последнего перемещаемость n-1. Задача решается почти однозначно. Вначале все шарики начиная со второго перепрыгивают через этот шарик, а потом он перепрыгывает через остальные.
Неверно и то, что задача решается обнулением чисел перемещаемости начиная с крайнего.
Например 4 шарика с перемещаемостями (2n+1,1,n,n) n>1 (первый ход самим левым шаром)или (n,n,1,2n+1)(первый ход третьим шаром).
Так как шары не должны сместится с места, то количество перепрыгиваний через данный шарик должен равняться числу перемещений этого шарика. Например, если у шарика число перемещений равна нулю, то этот шарик разрывает цепочку шариков, так как нельзя через него перепрыгивать и нельзя его сдвинуть.

 Профиль  
                  
 
 
Сообщение25.07.2006, 08:21 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Cronopio писал(а):
Задачка по программированию, с соревнований, чуть-чуть преобразованная.

В разделе "Математика" интересует только принципиальная разрешимость. :D По-моему, гвоздь не от этой стенки, а точнее, задача из неправильного форума.

Но это, наверное, уже не важно, коль скоро мы поняли друг друга и задачу вместе.

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

 Профиль  
                  
 
 
Сообщение25.07.2006, 11:14 
Заслуженный участник


09/02/06
4382
Москва
Назовём промежутеи между соседними шарами с числом перемещаемостью 0 связной компонентой. Для этого форьмально добавим ещё шары с номерами 0 и n+1 с числом перемещаемости 0.
Определим для каждой связной компоненты число $S=\sum_i x_i -2max_i x_i.$
Тогда необходимым и достаточным условием существования решения является то, что для каждой связной компоненты S является неотрицательным чётным числом.
О необходимости этого условия уже говорилось и оно очевидно. Достаточность получается алгоритмом обнуления чисел перемещаемости. Так как в каждой компоненте обнуление идёт независимо, будем считать, что что у нас одна компонента связности, т.е. все числа перемещаемости положительные целые.
Для доказательства достаточности можно предъявить соответствующий алгоритм.
Обозначим через y(i) суммы чисел перемещаемости слева от i -го шара, а через z(i) справа.
Тогда можно определить левую (i,k) операцию как k шаров слева по очереди перепрыгивают через i шар, а потом i шар перепрыгивает через них. При этом каждый шар может перепрыгивать t(j)>0 раз через i-ый шар, соответственно их числа перемещаемости уменьшается на t(j), а у i-го шара на t(i-1)+t(i-2)+...t(i-k). Аналогично можно определить правую (I,k) операцию. Каждая такая операция возвращает все шары на свои места и уменьшает числа перемещаемости указанным образом. Несложно доказать, что если исходное положение удовлетворяет необходимому условию, то существует левая или правая операция указанного типа, которая уменьшает числа перемещаемости и после применения этой операции не нарушается необходимое условие. Это доказывает достаточность и составляет алгоритм обнуления.

 Профиль  
                  
 
 
Сообщение27.07.2006, 10:18 


09/04/06
12
Germany
незваный гость
Есть надежда что найдутся хорошие математические соображения, похволяющие ее решить, поэтому сюда и отправлена

Руст Да, об этом я думала и операции такие определяла. Проблема в том, что они кажется не исчерпыва.т все возмодности. Например в такой позиции: 10 1 1 1 1 10 надо свести 10-тки вместе и менять их местами 8 раз а потом вернутьна место. Я не вижу как это получится операциями вида "переместить влево/вправо на к а потом обратно".

На компоненты разбивала. Думала например вычесть из всех перемещаемостей наименьшую и смотреть на получившиеся. Но оно, конечно, честенько приводит к неразрешимым позициям

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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