Перестановки. Лекция 23 - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Перестановки. Лекция 23. Доклад-сообщение содержит 29 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

перестановки лекция 23

Слайд 2

Описание слайда:

Про соревнования 3 мая 2013 Соревнования будут проходить в пятницу 3 мая, с 14-00, в 305-307 классах. Подходить для регистрации к 13-30 к 306 классу со студенческим билетом. Предложение такое, что одна решенная задача будет засчитываться как задача на экзамене, так как соревнования командные, то при решении в команде из 2-х человек надо будет решить две задачи. И при этом и проблем с допуском до экзамена у преподователя в группе не должно быть.

Слайд 3

Описание слайда:

План лекции Перестановки и инверсии Инверсии Связь со сложностью сортировки Алгоритм восстановления перестановки по таблице инверсий Итерационный алгоритм генерации всех таблиц инверсий Перебор перестановок Рекурсивный, через перебор таблиц инверсий, итерационный с лексикографическим упорядочением (Дейкстры)

Слайд 4

Описание слайда:

Перестановки Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке Для объектов а, b и с есть шесть перестановок аbс, acb, bac, bса. cab, cba. Далее будем рассматривать перестановки элементов множества {1, 2, 3, … , N}

Слайд 5

Описание слайда:

Перестановки Для множества из N элементов можно построить N! различных перестановок Первую позицию можно занять N способами Вторую — (N – 1) способом и т. д. На последнее место можно поставить только один оставшийся элемент Следовательно, число перестановок из N элементов равно N * (N −1) * (N − 2) * ... * 1 = N!

Слайд 6

Описание слайда:

Инверсии Пусть даны множество из N элементов 1,2, 3,..., N и его перестановка Пара называется инверсией (инверсионной парой) перестановки , если при i < j Единственной перестановкой, не содержащей инверсий, является упорядоченная перестановка 1, 2, 3, ... , N Каждая инверсия — это пара элементов перестановки, нарушающих ее упорядоченность

Слайд 7

Описание слайда:

Инверсии -- пример Перестановка 4, 1, 3, 2 имеет четыре инверсии (4,1), (3,2), (4,3) и (4,2) Почему?

Слайд 8

Описание слайда:

Таблица инверсий Таблицей инверсий перестановки а1, а2, ..., aN называется последовательность чисел b1, b2, …, bN, где bj = число инверсий вида (x, j) Пример П=591826473 ТИ=236402210

Слайд 9

Описание слайда:

Свойства таблиц инверсий Для элементов таблицы инверсий справедливы неравенства bN = 0 0

Слайд 10

Описание слайда:

Построение перестановки по таблице инверсий На каждом шаге вставляем следующий по величине элемент с учетом того, сколько элементов, больших него, должно стоять перед ним Таблица инверсий: 2 3 6 4 0 2 2 1 0 9 9 8 9 8 7 9 8 6 7 5 9 8 6 7 5 9 8 6 4 7 5 9 8 6 4 7 3 5 9 8 2 6 4 7 3 5 9 1 8 2 6 4 7 3

Слайд 11

Описание слайда:

Построение перестановки по таблице инверсий справа налево Вход N > 0 - количество элементов перестановки b1, b2 …, bN – ТИ, 0 ≤ bj ≤ N − j Алгоритм П = пустая последовательность цикл по j от N вниз до 1 вставить число j в П после bj элементов конец цикла Выход П − перестановка, соответствующая ТИ

Слайд 12

Описание слайда:

Построение перестановки по таблице инверсий слева направо Создается заготовка пустой перестановки длины N На каждом шаге для каждого элемента перестановки, начиная с 1, отсчитывается в ней столько пустых ячеек, какое число записано в соответствующей позиции в таблице инверсий В следующее за ними пустое место вставляется этот элемент Таблица инверсий 2 3 6 4 0 2 2 1 0 Перестановка

Слайд 13

Описание слайда:

Построение перестановки по таблице инверсий слева направо Вход N > 0 - количество элементов перестановки b1, b2 …, bN – ТИ, 0 ≤ bj ≤ N − j Алгоритм П = последовательность из N пустых элементов цикл по i от 1 до N с шагом 1 выполнять пропустить bi пустых мест в P поместить i на следующее пустое место конец цикла Выход П − перестановка, соответствующая ТИ

Слайд 14

Описание слайда:

Инверсионный метод поиска всех перестановок Таблицы инверсий взаимно однозначно соответствуют перестановкам Почему? Перебор ТИ сводится к перебору перестановок и наоборот

Слайд 15

Описание слайда:

Инверсионный метод поиска всех перестановок Рассмотрим таблицу инверсий как N-значное число в «системе счисления», где количество цифр, которое можно использовать в i-м разряде (с конца, начиная с 0) равно i Возьмем «нулевую» таблицу и будем последовательно прибавлять к ней в нашей СС единицу, пользуясь алгоритмом сложения с переносом для многоразрядных чисел Последовательно получим все ТИ и для каждой восстановим перестановку

Слайд 16

Описание слайда:

Генерация таблиц инверсии

Слайд 17

Описание слайда:

Нахождение следующей таблицы инверсий B = b1, b2, ..., bN – ТИ i = N не_всё = истина пока не_всё x = bi + 1 если x > N – i то bi = 0 i = i – 1 иначе bi = x не_всё = ложь всё всё Что же тут не так?

Слайд 18

Описание слайда:

Поиск следующей по алфавиту перестановки (алг. Дейкстры) П. b = b1, b2, …, bN предшествует п. c = c1, c2, …, cN в алфавитном (лексикографическом) порядке, если b1=c1, b2=c2, …, b[k-1]=c[k-1] и bk < сk для некоторого k Перестановка 1 2 3 4 5 предшествует перестановке 1 2 4 5 3 (k = 3) Первой перестановкой в алфавитном порядке является перестановка 1,2,3, ..., N, а последней — N, N-1, N-2, ..., 1

Слайд 19

Описание слайда:

Алгоритм Дейкстры От заданной перестановки перейдем к следующей за ней в алфавитном порядке и т.д., пока не получим N, N-1, …, 1 Например, для перестановки 1 4 6 2 9 5 8 7 3 следующей по алфавиту является перестановка 1 4 6 2 9 7 3 5 8

Слайд 20

Описание слайда:

Генерация следующей по алфавиту перестановки Вход П = a1, a2, …, a[N-1], aN – перестановка N > 0 элементов Алгоритм Начиная с последнего элемента, найдем такой номер i, что ai+1 > ... > aN и ai < a[i+1] Если такого i нет, то П – последняя в алф. порядке Обозначим aj наименьший элемент среди тех a[i+1], …, aN, которые строго больше ai Поменяем местами ai и aj Упорядочим a[i+1], …, aN по возрастанию Выход Cледующая по алфавиту перестановка

Слайд 21

Описание слайда:

Пример построения следующей по алфавиту перестановки Для перестановки 1 4 6 2 9 5 8 7 3 Найти следующую по алфавиту.

Слайд 22

Описание слайда:

Рекурсивный метод поиска всех перестановок Метод рекурсивного перебора перестановок основан на идее сведения исходной задачи к аналогичной задаче на меньшем наборе входных данных

Слайд 23

Описание слайда:

Пример рекурсивного перебора для M= {1,2,3,4}

Слайд 24

Описание слайда:

Реализация на языке Си typedef char string[256]; void permut(string start, string rest) { int lenr = strlen(rest), lens = strlen(start); int i=0; string sl="", s2=""; if (lenr == 0) printf(“%s\n”, start); else { for (i = 0; i < lenr; i++) { /* Добавляем i-ый символ к строке start */ strcpy(sl,start); strncpy(sl+lens,rest+i,1); strncpy(sl+lens+1,"\0",1); /* Удаляем i-ый символ из строки rest */ strncpy(s2,rest,i); strncpy(s2+i,rest+i+l,lenr-i-1); strncpy(s2+lenr,"\0", 1); /* Рекурсивный переход */ permut( s1, s2 ); } } /* sl+lens ≡ &(sl[lens]) */ } /* rest+i ≡ &(rest[i]) */

Слайд 25

$Реализация на языке Си #include typedef char mystring_t[256]; void permut(mystring_t start, mystring_t rest) { int lenr = strlen(rest); if (0 ==...$

Описание слайда:

Реализация на языке Си #include typedef char mystring_t[256]; void permut(mystring_t start, mystring_t rest) { int lenr = strlen(rest); if (0 == lenr) printf("%s\n", start); else { int i; for (i = 0; i < lenr; i++) { mystring_t mystart="", myrest=""; strcpy (mystart, start); strcpy (myrest, rest); append (mystart, delete (myrest, i) ); permut (mystart, myrest); } } } // TODO: написать append и delete

Слайд 26

Описание слайда:

Генерация всех перестановок методом Кнута Идея Рекурсивная генерация начиная с пустой перестановки методом расширения базового множества перестановки элементами 1, 2, 3, и т.д. Если построены все перестановки длины N, то для каждой такой перестановки можно построить N+1 перестановку длины N+1 Пример Для перестановки 3241 можно построить 5 различных перестановок длины 5 53241 35241 32541 32451 32415

Слайд 27

Описание слайда:

Генерация перестановок методом Кнута – способ 1 Пусть дана перестановка длины N Допишем в конец перестановки числа (2i+1)/2 (0 4 3 5 1 2 3 2 4 1 2.5 --> 4 2 5 1 3 3 2 4 1 3.5 --> 3 2 5 1 4 3 2 4 1 4.5 --> 3 2 4 1 5

Слайд 28

Описание слайда:

Генерация перестановок методом Кнута – способ 2 Пусть дана перестановка длины N: a1 a2 … aN Дописать в конец перестановки числа k 1 4 3 5 2 1 3 2 4 1 2 --> 4 3 5 1 2 3 2 4 1 3 --> 4 2 5 1 3 3 2 4 1 4 --> 3 2 5 1 4 3 2 4 1 5 --> 3 2 4 1 5

Слайд 29

Описание слайда:

Заключение Перестановки и инверсии Инверсии Связь со сложностью сортировки Алгоритм восстановления перестановки по таблице инверсий Итерационный алгоритм генерации всех таблиц инверсий Перебор перестановок Рекурсивный, через перебор таблиц инверсий, итерационный с лексикографическим упорядочением (Дейкстры), Кнута с перенумерацией

Теги Перестановки Лекция

Похожие презентации