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

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

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. Пусть это верно для (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

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

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

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

 Скачать реферат