рефераты по менеджменту

Организация строительства и управление качеством

Страница
15

Реупорядочить перестановочный хвост означает:

1) заменить обрывающее число на наименьшее из перестановочного хвоста число, превосходящее обрывающее;

Рис. 7. Блок-схема Алгоритма-1 получения всех n-перестановок.

2) все остальные числа из перестановочного хво­ста (вместе с обрывающим) расположить в порядке возрастания.

Так в нашей перестановке σn= (1, 3, 5, 4, 2) об­рывающее число есть 3, перестановочный хвост есть последовательность (3, 5,4, 2).

Заметим, что обрывающего числа не найдется только в перестановке, в которой все числа располо­жены в порядке убывания. В нашем алгоритме это сигнал того, что решение закончено.

Введение понятий «обрывающего числа», «пере­становочного хвоста», «реупорядочения» позволяет упростить описание алгоритма построения всех га-пе-рестановок. Этот алгоритм — назовем его Алгоритмом-1—представлен блок-схемой на рис. 7. Получе­ние первых нескольких перестановок по этому алго­ритму отображено в табл. 4.

Таблица 4

Первые 6 перестановок, полученные согласно Алгоритму-1

Перестановка

Обрывающее

число

Перестановочный хвост и его реупорядочение

1

(1, 2, 3, 4, 5)

4

(4, 5) -

––> (5, 4)

2

(1, 2, 3, 5, 4)

3

(3, 5, 4) -

—>• (4, 3, 5)

3

(1, 2, 4, 3, 5)

3

(3, 5) -

––> (5, 3)

4

(1, 2, 4, 5, 3)

4

(4, 5, 3)-

––> (5, 3, 4)

5

(1, 2, 5, 3, 4)

3

(3, 4) -

––> (4, 3)

6

(1, 2, 5, 4, 3)

2

(2, 5, 4, 3) -

—>(3, 2, 4, 5)

Нетрудно убедиться в том, что Алгоритм-1 дей­ствительно решает поставленную задачу. Этот факт очевиден для п == 1, можно проверить и для га == 2. Пусть это верно для (n— 1), т.е. алгоритм действи­тельно получает все различные перестановки в случае п — 1 элементов. Но если применить этот алгоритм для п элементов, то цифра 1, стоящая на первом ме­сте в исходной перестановке, будет заменена на 2, только когда она станет обрывающим числом, т. е. когда будут получены все (п—1)! различных пере­становок остальных чисел. Точно так же цифра 2 на первом месте в перестановках будет заменена на 3 только после получения всех (п— I)! различных пе­рестановок остальных элементов и т. д. Это и озна­чает, что алгоритм получает все п-(п—1)! переста­новок, при этом среди них не будет совпадающих.

Другой алгоритм — Алгоритм-2 — получения всех n-перестановок представлен блок-схемой на рис. 8.

Рас. 8. Блок-схема Алгоритма-2 получения всех n-перестановок.

Только один термин в блок-схеме рис. 8 нуждается в пояснении.

Назовем «вращением» некоторой последователь­ности А чисел замену ее другой последовательностью В, где число, стоящее в А на первом месте, оказы­вается в В на последнем месте, взаимное расположение других чисел не меняется. Так вращение (1, 2, 3) приводит к (2,3, 1).

Табл. 5 поясняет ход решения по этому алгоритму при получении первых нескольких перестановок.

Таблица 5

Первые перестановки, полученные согласие Алгоритму-2

Перестановка

 

Вращаемая часть

Результат вращения

1

(1, 2, 3, 4, 5)

т

=5:(1, 2, 3, 4, 5)

(2, 3, 4, 5, 1)

2

(2, 3, 4, 5, )

т

=5: (2, 3, 4, 5, 1)

(3, 4, 5, 1, 2)

3

(3, 4, 5, ), 2)

т

=5:(3, 4, 5, 1, 2)

(4, 5, 1, 2, 3)

4

(4, 5, 1, 2, 3)

т

=5:<4, 5, 1, 2, 3)

(5, 1, 2, 3, 4)

5

(5, 1, 2, 3, 4

т

=5: (5, 1, 2, 3, 4)

(1, 2, 3, 4, 5)

   

т

=4:(1, 2, 3, 4)

(2, 3, 4, 1)

6

(2, 3, 4, 1, 5)

т

=5:(2, 3, 4, !, 5)

(3. 4, 1, 5, 2)

У п р .а ж н е н и е II*. Понравилось ли вам изложение Ал­горитма-1? Могли бы вы улучшить его разъяснение? Могли бы вы доказать, что по Алгоритму-2 действительно получают все n-перестановки?

Упражнение 12*. Не могли бы вы предложить алго­ритм получения всех n-перестановок, отличный от изложенных? Уверены ли вы, что по этому алгоритму можно получить дей­ствительно все перестановки? Оглавление

Табличный метод расчёта сетевых моделей (графиков)

Перейти на страницу номер:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 
 16  17  18  19  20  21  22  23  24  25  26  27 

© 2010-2024 рефераты по менеджменту