Материал: 24_41

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

у даному разі граничним є не елемент зі значенням 6, а той, ЩО стоїть на шостому місці у поточній послідовності. Отже, якщо 6-й елемент менший від того, що стоїть праворуч, і його не обхідно внести до розгляду, то зрозуміло, що на даному етапі для відновлення спадання правого фрагмента послідовності два останні елементи необхідно поміняти місцями (мал. 1, в). Після такого обміну можна констатувати два факти: граничним елементом є елемент, що займає шосту позицію у заданій послі довності, і її фрагмент, що знаходиться справа від граничного елемента, утворює упорядковану під послідовність (мал. 1, г). Поки що залишимо питання з'ясування характеру упорядкова ності елементів цієї підпослідовності без відповіді: у даному разі один елемент може утворювати як зростаючу, так і спадну підпослідовність. Отже, ми отримали два варіанти розташуван ня елементів заданої послідовності (мал. 1, а та г).

Просуваючись далі, підключимо до нашого фрагмента ще один елемент зліва, тобто розглянемо у послідовності, зображе ній на малюнку 2, а, три останніх елементи справа. Тепер гра ничним елементом буде елемент, розташований на 5-й позиції. Як бачимо, серед цих трьох елементів упорядкування відсутнє. «Порушником» є новий підключений елемент, і його треба

поміняти місцями з одним із елементів цього самого фрагмента послідовності. Але з яким саме із тих двох, що знаходяться праворуч (мал. 2, а)? Давайте не забувати, що ми намагаємося У кінцевому варіанті перевести нашу послідовність у стан «за спаданням», і фрагмент із двох останніх елементів задовольняє цю умову. Ця сама умова збережеться тоді і тільки тоді, коли ми знайдемо перший елемент справа, що перевищує той, що має бути включений до нашого фрагмента, тобто граничний елемент. Таким на малюнку 2, а є крайній справа елемент. Після обміну отримаємо послідовність, зображену на малюнку 2, б, у якій два останні елементи упорядковані за спаданням. І це зрозуміло, оскільки перед обміном в упорядкованому фрагменті послідовності були всі елементи, більші за той, який ми підключили, і претендентом на обмін був крайній справа елемент: менший з них увійшов у фрагмент, а більший вийшов за межі фрагмента і став на місце граничного. Ми не порушили спадання фрагмента, але «закинули» туди новий елемент послідовності (мал. 2,6).

Що нам дали описані дії? Чи одержали ми наступний ва ріант перестановки? Виявляється, що ні. Хоча два останні елементи підпослідовності упорядковані за спаданням, тобто ми створили ситуацію, до якої прагнемо у кінцевому варіанті, однак на даному кроці ми вчинимо наступне. Скажімо, так: для того, щоб не втратити жодного варіанта перестановок, кожного разу, коли по праву сторону від граничного елемента буде отримано упорядковану за спаданням підпослідовність, ми будемо максимально її «пошкоджувати». Для цього перево дитимемо підпослідовність правих елементів у стан упорядку вання за зростанням так, як це було на початку. А у нашому випадку два останніх елементи заданої послідовності поміняє мо місцями (мал. 2, б). Тим самим почнемо наш алгоритм упо рядкування фрагмента з початку, але вже з новим включеним туди елементом (мал. 2, в).

Залишилось відповісти на таке запитання: чи не втрачено одного з варіантів перестановок при зміні упорядкованості еле ментів підпослідовності зі спадання на зростання? Ні, не втра чено: цей варіант з'явиться на кроці генерації наступного пе реставлення і це ми побачимо далі.

На малюнку 3, а-и продемонстровано кілька кроків одер жання наступних варіантів перестановок.

Пересвідчитися у коректності такого алгоритму можна, якщо подивитися на варіанти послідовностей як на послідов ність звичайних чисел, що зростають за своїми значеннями: 1234567, 1234576, 1234657, 1234675, 1234756, 1234765, 1235467, ..., 7654321.

а)

є)

у{

_А

ь-

J—

)

<Ч

1 2 3 4 5 6 7

б )

1 2 3 4 5 6 7

1 2 3 4 6 7 5

'л~ґч

•

г-Г\—

ІҐ

•>

< •

чJ

-с

•4

-с

JЧ

<ч

1 2

1 2 3 4 7 5 6

н{"

1 -

•II*»

(•

ч_

-с

("-с

-С

)

<-?

—ч5

1 2

є)

1 2 3 4 7 6 5

Мал. З

_ 1

_ J

•

fcl

tor

—

_/S_

ІT^

__A—

-c

7V^

— C

-c

1 2

ж)

з)

в) 1 2 3 5 4 6 7

Мал. З (продовження)

Оскільки ми не завжди маємо справу з числами, то у загаль ному випадку будемо говорити про елементи деякої послідов ності елементів. Вважатимемо, що за певною ознакою можна визначити відношення між заданими елементами: більше, менше, дорівнює. Використовуючи наведене вище наочне схе матичне представлення генерації перестановок, сформулюємо алгоритм побудови лексикографічної послідовності заданих елементів.

1.Сформувати початковий стан розташування елементів «за зростанням».

2.Рухатися заданою послідовністю справа наліво, аналізу ючи поточні елементи. Крок до наступного елемента вліво ви конується лише у разі, якщо перехід здійснюється до елемента, що не більший від попереднього. Рухаючись таким чином послідовністю справа наліво, буде визначено граничний еле мент.

3.Знову почати рух від останнього елемента послідовності справа наліво, порівнюючи значення кожного поточного еле мента зі значенням граничного елемента, визначеного у п. 2. Рух припиняється тоді, коли трапиться елемент, більший за значенням від граничного елемента.

4.Поміняти місцями елементи із п. 2 та п. 3.

5.Усі елементи, розташовані після граничного елемента, розмістити у зворотному порядку, тобто в порядку зростання. Це можна зробити досить ефективно: оскільки цей фрагмент послідовності нами вже попередньо упорядкований за спадан ням, то для упорядкування його за зростанням необхідно лише поміняти місцями елементи, розміщені симетрично відносно центрального елемента даного фрагмента.

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

надати всім елементам заданої послідовності порядкові номери і організувати перестановки саме цих чисел.

Отже, надалі вважатимемо, що масив значень а[і], з еле ментів якого формуються перестановки, містить порядкові но мери заданої послідовності Ь[і]: 1, 2, 3, ..., N.

Процедура, що реалізує описаний алгоритм отримання всіх пе рестановок N заданих елементів, мовою Pascal виглядатиме так:

procedure perm; var і, k, с: byte; begin

i:=n;

while a[i - 1] > a[i] do dec(i);

k : = i - 1; i:=n;

while a[i] < a[k] do dec(i); c:=a[k];a[k] :=a[i];a[i] :=c;

for і := 1 to (n - k) div 2 do begin

{Визначення елемента, який порушує} {спадання послідовності.}

{Визначення елемента,} {який є претендентом для обміну.} {Обмін визначених елементів.} {Упорядкування за зростанням} {фрагмента послідовності,} {що знаходиться справа}

|c:=a[k + i];a[k + i] :=a[n- і + 1]; а[п - і + 1] := с {від позиції обміну.} end;

end;

Результатом виконання процедури perm буде один із ва ріантів його перестановки. Для одержання всіх перестановок необхідно використати цю процедуру в основній програмі у вигляді такого фрагмента:

f : = 1 ;

f o r І := 1	to П do	{Підрахунок кількості перестановок.}
f : = f * i ;
f o r І := 1	to П do	{Формування стартового стану масиву порядкових номерів.}
а[і]:=і;

f o r І := 1 to П do {Виведення першого варіанта перестановок заданих елементів.}

write(b[a[i]], ' '); writeln;

f o r І := 1 to f - 1 do	{Генерація решти перестановок порядкових номерів.}
begin
perm;
f o r j := 1 to П do	{Виведення поточної перестановки заданих елементів.}
write(b[a[j]],'');
writeln;
end;

А які зміни необхідно внести в алгоритм, щоб змінити лек сикографічний порядок визначених варіантів перестановок на зворотний? Зрозуміло, що необхідно:

Смотрите также:


«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
Значение, сущность и содержание социально — педагогической деятельности в организации для детей-сирот и детей, оставшихся без попечения родителей
Проактивные методы PR-деятельности российских авиационных компаний «Россия», «Азимут»
__RGR2
__RGR2
_11_А. Франс для эл версии
_3 тема - Диффузия
_Антонян Ю.М., Психология преступника и расследования преступлений