Предыдущая страница реферата | 8  9  10  11  12  13  14  15  16  17  18 | Следующая страница реферата

1, 2, 4, 3, 5

1, 2, 4, 5, 3

1, 2, 5, 3, 4

1, 2, 5, 4, 3

1, 3, 2, 4, 5

Чтобы попроще описать найденный прием, введем некоторые понятия.

Пару соседних чисел (в перестановке) назовем упорядоченной, если первое число в паре меньше

второго.

Рассмотрим некоторую перестановку Оп. Найдем первую с конца перестановки упорядоченную пару. Так в перестановке ?n =(1, 3, 5, 4, 2) первая с конца упорядоченная пара есть пара (3, 5). Первое число такой пары назовем обрывающим. Перестановочный хвост в ?n образует последовательность чисел, начиная с обрывающего.

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

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

Рис. 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 |(4, 5) - |––> (5, 4) |
| |4, 5) | | | |
|2|(1, 2, 3, |3 |(3, 5, 4) - |—>• (4, 3, 5)|
| |5, 4) | | | |
|3|(1, 2, 4, |3 |(3, 5) - |––> (5, 3) |
| |3, 5) | | | |
|4|(1, 2, 4, |4 |(4, 5, 3)- |––> (5, 3, 4)|
| |5, 3) | | | |
|5|(1, 2, 5, |3 |(3, 4) - |––> (4, 3) |
| |3, 4) | | | |
|6|(1, 2, 5, |2 |(2, 5, 4, 3)|—>(3, 2, 4, |
| |4, 3) | |- |5) |

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

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

[pic]

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

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

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

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

Рекомендуем скачать другие рефераты по теме: реферат безопасность, рассказы, сообщение.



Предыдущая страница реферата | 8  9  10  11  12  13  14  15  16  17  18 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки