Бывалый
Группа: Пользователи
Сообщений: 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,67 и 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 - получили, то что нужно. всё Один вариант есть. Для получения других вариантов, думаю, нужно видоизменять циклически первоначальную последовательность и уже для каждой измененной применять вышеописанный алгоритм. Как то так.
|