IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Перестановки троек
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


Привет всем. Задачка такова: "Энциклопедия «вычислительная техника» содержит семь томов. они стоят на полке в такой последовательности:1,5,6,2,4,3,7.Надо расставить их в правильном порядке, действуя по правилу: переставить три рядом стоящих тома в начало, конец или между двумя другими книгами, не меняя при этом порядка этих трех томов."

Каким алгоритмом пользоваться, чтобы найти все возможные (если не все, то хотябы не менее пяти) варианты таких перестановок? Натолкните на мысль правильную, пожалуйста.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


алгоритм случайной перестановки мне помог.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(samec @ 10.05.2010 13:16) *
алгоритм случайной перестановки мне помог.
Гм.
Быстрый взгляд на проблему - тоже..
Я пока не могу понять, возможно ли это для всех мыслимых конфигураций, или нет (как в 15-шках). Я понимаю, что задача не в том состоит, и все же интересно.
Надо будет подумать еще..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


Алгоритм, который даёт один единственный вариант "правильной расстановки".
Так вот, сам алгоритм.
Берём первый том
а)если он не находится на предпоследнем или последнем месте, то просто переставляем его(вместе с двумя соседями) на первое место:
б)иначе, циклически переставляем последние четыре элемента, после чего идём к пункту а.

в примере к задаче первый том итак стоит на своём месте - так что ничего никуда не гоним.

Затем так же поступаем со вторым томом:
в примере:
было 1,5,6,2,4,3,7 (взяли 2,4,3 и воткнули между 1 и 5)
стало 1,2,4,3,5,6,7


повторяем эти действия до тех пор, пока не поставим на свои места все тома, кроме последних четырёх.

для нашего примера:
было 1,2,4,3,5,6,7 (взяли 3,5,6 и воткнули между 2 и 4)
стало 1,2,3,5,6,4,7


Потом, когда остались последние 4 тома, делаем вот что:
циклически переставляем последние четыре тома так, чтобы четвёртый с конца том оказался на своём месте.
для нашего примера:
было 1,2,3,5,6,4,7(взяли 6,4,7 и воткнули между 3 и 5)
1,2,3,6,4,7,5(взяли 4,7,5 и воткнули между 3 и 6)
1,2,3,4,7,5,6.
четвёртый с конца том оказался на своём месте.


теперь нужно как то менять местами последние три тома между собою - не нарушая последовательности всех предыдущих томов.
делаем это вот по такому правилу:
a,b,c,d,f -> d,a,b,c,f -> c,f,d,a,b -> a,b,c,f,d - d и f поменялись местами - остальные элементы остались на месте.

в нашем примере нужно поменять 7 и 5 местами
a,b,c,d,f -> d,a,b,c,f делаем вот так:
было 1,2,3,4,7,5,6 (взяли 2,3,4 и вотнули между 7 и 5)
стало 1,7,2,3,4,5,6



затем
d,a,b,c,f -> c,f,d,a,b делаем так:
было 1,7,2,3,4,5,6 (берём 7,2,3 и засовываем после 5)
стало 1,4,5,7,2,3,6



и наконец последнее действие по обмену, c,f,d,a,b -> a,b,c,f,d - делаем так:
было 1,4,5,7,2,3,6 (взяли 4,5,7 и засунули после 3)
стало 1,2,3,4,5,7,6


7 и 5 обменялись местами.
Такми же образом меняем 7 и 6 между собою местами:
1,2,3,4,5,7,6
1,2,7,3,4,5,6
1,2,5,6,7,3,4
1,2,3,4,5,6,7 - получили, то что нужно.

всё smile.gif
Один вариант есть.

Для получения других вариантов, думаю, нужно видоизменять циклически первоначальную последовательность и уже для каждой измененной применять вышеописанный алгоритм.
Как то так.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 8:53
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name