distance
Advanced Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору 2.2.1. Напечатать все перестановки чисел 1..n (то есть пос- ледовательности длины n, в которые каждое из чисел 1..n входит по одному разу). Решение. Перестановки будем хранить в массиве x[1],..., x[n] и печатать в лексикографическом порядке. (Первой при этом будет перестановка <1 2...n>, последней - <n...2 1>.) Для сос- тавления алгоритма перехода к следующей перестановке зададимся вопросом: в каком случае k-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следу- ющих членов (членов с номерами больше k). Мы должны найти на- ибольшее k, при котором это так, т. е. такое k, что x[k] < x[k+1] > ... > x[n]. После этого x[k] нужно увеличить мини- мальным возможным способом, т. е. найти среди x[k+1], ..., x[n] наименьшее число, большее его. Поменяв x[k] с ним, остается рас- положить числа с номерами k+1, ..., n так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке. Алгоритм перехода к следующей перестановке. {<x[1],...,x[n-1], x[n]> <> <n,...,2, 1>.} k:=n-1; {последовательность справа от k убывающая: x[k+1] >...> x[n]} while x[k] > x[k+1] do begin | k:=k-1; end; {x[k] < x[k+1] > ... > x[n]} t:=k+1; {t <=n, x[k+1] > ... > x[t] > x[k]} while (t < n) and (x[t+1] > x[k]) do begin | t:=t+1; end; {x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]} ... обменять x[k] и x[t] {x[k+1] > ... > x[n]} ... переставить участок x[k+1] ... x[n] в обратном порядке Замечание. Программа имеет знакомый дефект: если t = n, то x[t+1] не определено. | Всего записей: 878 | Зарегистр. 28-03-2004 | Отправлено: 20:49 10-11-2006 | Исправлено: distance, 20:50 10-11-2006 |
|