Раздел: Документация
0 ... 62 63 64 65 66 67 68 ... 117 чтобы вычислять длины циклов и наименьшее общее кратное этих длин. К тому же вам будет нужно перссчитываать общее число непересекающихся циклов в перестановке и усреднить его по большому числу проб. Перестановка чисел 1,2,.... ,п есть их перегруппировка в некотором порядке. Например, при п = 8 перестановка /1 2345678\ 7Г~\ч73865412 переводит 1 в 7, 2 в 3, Зв8и т.д. Перегруппировка просто записана в нижней строке, которую мы будем обозначать как вектор р. Любая перестановка может быть записана в обозначениях непересекающихся циклов. Для тг это даст представление (17)(238)(46)(5), которое означает, что 7г можно получить, оставив 5 на месте; переставив 4 на место 6, а 6 на место 4; переставив 2 на место 3, 3 на место 8, а 8 на место 2 и переставив 1 на место 7, а 7 на место 1. Цикл (46) называется 2-циклом или транспозицией, (238) называется 3-циклом и т. д. Часто «1-цикл» (б) опускается при такой записи, но здесь мы будем включать его. Нас будет интересовать (кроме всего прочего) общее число непересекающихся циклов в представлении перестановки. В случае тг из (14.1) оно равно 4. (Достаточно понятно и верно, что разложение перестановки тг на непересекающиеся циклы полностью определяется самой тг, исключая то, что циклы могут быть записаны в другом порядке и элементы каждого цикла сами могут быть циклически переставлены. Например, наша перестановка 7Г равна также (5)(382)(71)(46),) Обозначим через S(n) множество всех перестановок чисел 1,2.... , п. Имеется п\ таких перестановок, поскольку имеется п положений для 1, п - 1 положений для 2 и т. д., а всю перестановку можно выбрать п(п-\){п-2)..Л=п\ способами. (i) В MATLABe есть функция randperm(п), порождающая случайную перестановку чисел 1,2,... , п, т. е. случайный элемент из S(n) Наберите randperm(10), чтобы получить случайную перестановку чисел 1,2,... ,10. Загляните в этот М-файл. Воспользуйтесь вашими знаниями о команде sort, чтобы описать работу randperm.т. (Если вы забыли команду sort, наберите help sort.) Напишите короткий М-файл, создающий 1000 случайных перестановок, и запасите их все как строки матрицы Ыдр размера 1000 х п. Подсказка: Начните с команды n=input(Наберите значение п) чтобы вы могли использовать разные значения п в разных примерах. Каждая случайная перестановка тогда порождается командой p=randperm(n); Вам понадобится команда цикла forj = 1:1000 выполняющаяся после строки ввода п. Если вы напишете внутри цикла bigp(j,:)=р; то вектор р сделаете j-й строкой матрицы Ыдр. Если вы хотите выполнить один за другим несколько примеров, то неплохо будет набрать {в MATLABe) » clear bigp между примерами или вставьте это в начало вашего М-файла. Теперь положите п = 5 и постройте гистограмму из столбцов матрицы Ыдр. (Обратите внимание, что hist(v,1:5) построит гистограмму вектора v из «столбиков», середины которых даются числами 1, 2, 3, 4, 5.) Распечатайте одну из этих гистограмм и убедитесь, что все столбики находятся на том уровне, который говорит, что числа 1, 2, 3, 4, 5 появляются в любой позиции перестановки с одной и той же частотой (и, следовательно, randperm. m является неплохим генератором случайных перестановок). (ii) Созданный для вас М-файл cycles .m генерирует случайную перестановку, а затем раскладывает ее на непересекающиеся циклы. Он делает это точно так, как делали бы вы, следуя за числами при перестановке, пока не получится цикл, и переходя затем к новому числу, чтобы сформировать следующий цикл. Чтобы помочь компьютеру остановиться, когда все числа от 1 до и будут «использованы» в циклах, элементы вектора р обнуляются по мере попадания в циклы. Попробуйте выполнить М-файл несколько раз, чтобы понять, что он делает. В одном случае, взяв, например, п = 10, разложите перестановку на циклы вручную и сравните ваш результат с компьютерным. (iii)Измените cycles.mтак. чтобы подсчитывались порядки (длины) циклов, а в конце определялось НОК этих длин. Было бы лучше, если бы длины запоминались в векторе, скажем, clength, который вначале определяется как пустой: clength = [] а затем этот вектор получает приращение каждый раз, когда будет определена очередная длина: clength = [clength newlength] где «newlength*> означает только что найденную длину. Чтобы найти НОК, сделайте следующее: положив I = HOK(a-i,a"2> • • • ,хк), вычислите последовательно li=-HOK(rBi,a-a), h = HOK(iba-3), h-i = HOK(I-, 2jxk), и тогда последнее lk-i даст искомое /. Можете также считать, что для двух чисел а, Ъ НОК(а, Ь) = -ft -р-.. Можете воспользоваться существующей функцией gcdiv.m, чтобы вычислить НОД. Таким образом, для вычисления НОК длин нужно выполнить команды MATLABa ord=clength(l); for i=2:length(clength) ord=(ord-fclength(i))/gcdiv(ord, clength(i)); end а затем, конечно, вы захотите вывести на экран получившееся значение ord. Сделайте несколько примеров с помощью этого М-файла. (iv)Измените randperm. m так, чтобы он также вычислял соответствующую перестановочную матрицу А перестановки 7г € .S(n)1). Она определяется как матрица, у которой для г = 1,... ,гав i-й строке в позиции тг (г) стоит 1, а остальные элементы строки равны 0. Так что вы сначала должны определить А = zeros(n,n), а затем выполнить цикл for i = 1: п A(i,p(i))=l; end: О Его следует сохранить под другим именем, поскольку randperm - функция системы. - Прим. перев. 0 ... 62 63 64 65 66 67 68 ... 117
|
