Организация строительства и управление качествомРефераты >> Управление >> Организация строительства и управление качеством
Рис. 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-перестановки?
