Реферат: Генерация комбинаторных объектов - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Генерация комбинаторных объектов

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 22 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Реферат Генерация комбинаторных объектов Содержание Введение 3 1 Множе ство всех подмножеств 4 2 Перес тановки 7 3 Сочет ания 11 4 Разме щения 14 5 Перес тановки с повторениями 17 6 Сочет ания с повторениями 20 Заключ ение 23 Литера тура 24 Введение Существует набор задач, решение которых заключается в генерации всех элементов таких комбинаторных объектов как множество в сех подмножеств, перестановки, сочетания, размещения, перестановки с пов торениями, сочетания с повторениями. Для каждого сгенерированного элемента затем проверя ются какие-то свойства для конкретной задачи. В дальнейшем в данной работе предла гается следующий порядок изложения материала для каждого комбинаторно го объекта: пример, алгоритм, программа, комментарии к программе. 1 Множество вс ех подмножеств Пусть мы имеем множество из 4-х компонент - которые мы об означаем латинскими буквами A, B, C, D соответственно. И пусть по условиям задачи требуется выбрать подмноже ство, состоящее из нескольких компонент, обладающее некоторым свойство м. Предлагается такой способ решения задачи: мы генерируем ВСЕ возможные подмножества данного множества и для каждого из сгенерированных подмн ожеств проверяем удовлетворяет ли оно заданному свойству. Альтернатив ный вариант задачи - подсчитать ВСЕ подмножества данного множества, обла дающие заданным свойством. Например: Для множества из 4-х символов A,B,C,D множество всех подмнож еств включает в себя следующие множества: Пустое множество Одноэлементные множества: A , B , C , D Двухэлементные множества: A,B , A,C , A,D B,C , B,D , C,D Трехэлементные множества: A,B,C , A,B,D , A,C,D , B,C,D Четырехэлементное множество: A,B,C,D В случае, если порядок генерации подмножеств не играе т роли (а, например, в случае необходимости подсчитать все подмножества, о бладающие заданным свойством, так оно и есть) один из наиболее просто код ируемых алгоритмов генерации множества всех подмножеств выглядит след ующим образом. Заведем вектор B, состоящий из четырех чисел, каждое из которых может принимать значение 0 или 1. И будем считать, что значение 1 ука зывает на то, что соответствующий по номеру компонент исходного множест ва включается в множество, а значение 0 указывает на то, что элемент не вкл ючается. Рассмотрим теперь последовательность двоичных чисе л от 0 до 15 и соответствующие им подмножества: 4321 DCBA 0000 - Пустое множество 0001 A 0010 B 0011 AB 0100 C 0101 AC 0110 BC 0111 ABC 1000 D 1001 AD 1010 BD 1011 ABD 1100 CD 1101 ACD 1110 BCD 1111 ABCD Таким образом, всего имеется 16 различных подмножеств м ножества из 4-х элементов. В общем случае множество всех подмножеств множ ества из N элементов содержит 2N (два в степени N) элементов. Алгоритм, обеспечивающий такую генерацию множества в сех подмножеств из N элементов, может быть неформально описан следующим образом: Формируем массив, состоящий из N нулей - и рассматриваем его как пустое множество. Таким образом, начальное значение текуще го подмножества - пустое множество. Для получения следующего подмножества из текущего по дмножества обрабатываем текущий массив из чисел 0 или 1 следующим образо м: Справа (от первого элемента массива к последнему) ищем первое число, равное нулю. Если такое число не найдено - значит, текущее подмножес тво является последним - множеством, состоящим из всех элементов, и на это м алгоритм заканчивает свою работу. Если же элемент равный 0 найден, то он заменяется на 1, а в се числа справа от него (если таковые имеются) заменяются на нули. Более формализовано этот алгоритм может быть записан следующим образом: Ввод (N) Обнуление массива B из N+1 элемента Вывод (Пустое множество) Пока B[N+1]=0 i=1 Пока B[i]=1 де лать B[i]=0, i=i+1 B[i]=1 Вывод (множества, определяемого массивом B) Ниже приводится текст программы, которая считывает N - число элементов в м ножестве и выводит на экран множество всех подмножеств обозначая элеме нты соответствующими по порядку латинскими буквами: const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1..100] of byte; N,i : byte; begin readln(N); for i:=1 to N+1 do b[i]:=0; writeln (' Пустое множество '); while (b[N+1]=0) do begin i:=1; while B[i]=1 do begin B[i]:=0; inc(i); end; B[i]:=1; for i:=1 to n do if b[i]=1 then write(alphabet[i]); writeln; end; end. При необходимости обрабатывать (анализировать) постр оенные подмножества могут быть добавлены вызовы процедур обработки, по лучающие в качестве параметра массив B (указывающий своими единичными эл ементами номера элементов множества, включенных в текущее подмножеств о). 2 Перестановки Пусть мы имеем 4 компонента, обозначенные буквами A, B, C, D соответственно. Тогда множество всех перестановок из этих компонент б удет включать следующие элементы: ABCD BACD CABD DABC ABDC BADC CADB DACB ACBD BCAD CBAD DBAC ACDB BCDA CBDA DBCA ADBC BDAC CDAB DCAB ADCB BDCA CDBA DCBA Проиллюстрируем сначала алгоритм построения следую щей перестановки на примере перестановок из 9 компонент, обозначенных со ответственно цифрами от 1 до 9. Первая из таких перестановок это 1 2 3 4 5 6 7 8 9 Пусть текущая перестановка из 9 компонент: 1 9 5 8 4 7 6 3 2 Каким будет следующее значение перестановки, если мы строим ее в лексикографическом порядке (то есть в порядке возрастания ве личины числа, составленного из этих цифр)? Правильный ответ таков : 1 9 5 8 6 2 3 4 7 Как он получается? Прежде всего , необходи мо просматривать исходный массив от конца к началу , что бы найти первое число, которое МЕНЬШЕ предыдущего в наш ем случае - это 4 (7>6>3>2, а 4<7) Далее среди просмотренных чисел справа от найденной 4 мы ищем последнее число которое больше 4. Это число 6. (7>4, 6>4, 3<4, 2<4) Затем меняем эти 2 найденных числа (4 и 6) местами, получае м: 1 9 5 8 6 7 4 3 2 И теперь числа (справа от 6), которые составляют убывающ ую последовательность (7 4 3 2) , попарно меняем местами так, что бы они состави ли возрастающую последовательность (2 3 4 7) : 1 9 5 8 6 2 3 4 7 Это и есть следующая перестановка. А какая перестановка будет последней для данного прим ера? Надеюсь, что вдумчивый чита т ель догадался и сам: 9 8 7 6 5 4 3 2 1 Несколько неформально алгоритм построения следующе й перестановки по текущей может быть записан следующим образом: 1. От конца к началу перестановки ищем первый элемент B[i] такой, что B[i]0) и (B[i]>=B[i+1]), i=i-1 Если i=0 то конец работы Для j от i+1 до N если B[j]>B[i] то K=j Обмен значений B[i] и B[k] Для j от i+1 до (i+ ((N+1-i) div 2)) Обмен значений B[j] и B[N+i+1-j] Вывод текущей перестановки B Понятно, что цикл попарных перестановок "хвоста" массива B нельзя делать о т i+1 до N-го элемента - иначе элементы поменяются местами по 2 раза - и получить ся, что ничего не изменилось. Цикл нужно выполнить для половины этого "хво ста". Этому и служит несколько сложное для понимания значение конечной п еременной цикла: i+ (N+1-i) div 2 Ниже приводится программа, генерирующая все перестановки из N компонент, обозначенных N первыми буквами латинско го а л фавита. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1..100] of byte ; N,i,j,k : byte; Procedure SwapB(i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure WriteB; begin for i:=1 to N do write( alphabet[b[i]]); writeln; end; begin readln(N); for i:=1 to N do b[i]:=i; WriteB; while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit; for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(j,N+i+1-j); writeB; end; end. В программе введены 2 процедуры WriteB и SwapB. Процедура WriteB вызывается всякий раз, когда построена оч ередная перестановка. В данной программе процедура WriteB просто выводит со ответствующую последовательность латинских букв. Процедура SwapB(i,k) введена для упрощения понимания главно й программы. SwapB просто обменивает значени ями два элемента массива B - те, которые имеют индексы, соответствующие зна чениям параметров процедуры i и k. Процедура SwapB использует ся в тексте прогр аммы два раза 1) При обмене значениями двух найденных элементов с инд ексами I и K. 2) При обеспечении попарного обмена элементов "хвоста", в котором текущий элемент с индексом j обменивается местами со своим "пар тнером", находящимся на позиции N+i+1-j. Таким образом, I+1-ый элемент поменяется ( при J=I+1) местами с N-м элементом, I+2-ой элемент (при J=I+2) с N-1-ым и т.д. Общее число перестановок из N элементов равно N! (читает ся N факториал). Напомним, что N! = 1*2*3*...*N 3 Сочетания Пусть имеем 5 компонент, обозначенных латинскими букв ами A, B, C, D, E соответственно. Тогда все сочетания из этих 5 компонент по 3, выписанные в лексикографическом порядке (для букв и цифр от 1 до 5) будут таковы: ABC 123 ABD 124 ABE 125 ACD 134 ACE 135 ADE 145 BCD 234 BCE 235 BDE 245 CDE 345 Неформально алгоритм генерации последовательности чисел в лексикографическом порядке можн о записать следующим образом. Выберем наименьшие M из имеющихся N чисел и в ыпишем их в порядке возрастания - и выпишем их в порядке возрастания - 1 2 3 - эт о начальное сочетание. Очевидно, что наибольшие M чисел из имеющихся (3 4 5), вы писанные в порядке возрастания, составят последнее сочетание. Для того, что бы по текущему сочетанию получать следую щее, можно поступать следующим образом: Находим позицию в текущем сочетании, на которой не сто ит последнее из возможных значений, и затем увеличиваем его на 1. А все пос ледующие элементы сочетания получаем увеличением на 1 предыдущего элем ента сочетания. Например пусть текущее сочетание 1 3 5 Анализ начинаем с последней позиции сочетания. 5 - это последнее возможное значение, потому переходим к предыдущей позиции. 3 - это не последнее возможное значение для этой позиц ии (каковым является 4 в данном случае). Потому мы его увеличиваем на 1 - полу чаем 4. А число в следующей позиции получаем прибавлением 1 к этой 4-ке - и пол учаем 5. Таким образом следующее значение будет 1 4 5 Более формализовано этот алгоритм может быть записан следующим образом: Ввод N, M (из сколька, по ск олько) Заносим в массив B числа от 1 до M Это первое сочетание, выводим его Пока (истина) i=M Пока (i>0) и (b[i]=N-m+i), i=i-1 Если i=0 то работа завершена B[i]=B[i]+1 Для j от i+1 до M B[j]=B[j-1]+1; Вывод B - следующей перестановки Ниже приводится программа, которая считывает с клавиа туры значения N и M и выводит в лексикографическом порядке все сочетания и з N первых латинских букв по M. uses crt; const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1..100] of byte; N,M,i,j,k : byte; Procedure WriteB; begin for i:=1 to M do write(alphabet[b[i]]); writeln; end; begin readln(N,M); for i:=1 to M do b[i]:=i; WriteB; while (true) do begin i:=M; while (i>0) and (b[i]=N-m+i) do Dec(i); if i=0 then exit; Inc(B[i]); for j:=i+1 to M do B[j]:=B[j-1]+1; WriteB; end; end. Напомним, что общее число сочетаний из N элементов по M может быть вычислен о по формуле C (N,M) = N! / (M! * (N-M)! ) 4 Размещения Для генерации всех размещений из N элементов по M можно воспользоваться композицией алгоритмов, изложенных выше. То есть генер ировать все сочетания из N по M, а затем для каждого полученного сочетания генерировать все перестановки из M элементов. Например, при генерации всех размещений из 5 элементов по 3, в случае, если сами элементы обозначе ны латинскими буквами A,B,C,D,E нужно получить следующую последовательность, представленную для компактности в виде 10 строк, каждая из которых предст авляет все возможные сочетания из 3 букв первого элемента строки. А сами п ервые элементы строк как раз и представляют все возможные сочетания из 5 букв по 3. ABC ACB BAC BCA CAB CBA ABD ... ABE ... ACD ... ACE ... ADE ... BCD ... BCE ... BDE ... CDE CED DCE DEC ECD EDC Общее количество pазмещений - из N элементов по M может бы ть найдено по формуле: N! / (N-M)! Ниже приводится программа, которая вводит с клавиатур ы числа N, M и генерирует все возможные разм ещения из N букв по M. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; type barray = array [1..100] of byte; var b : barray; N,M,i,j,k : byte; z : longint; Procedure WriteB(B:barray); begin Inc(Z); Write (Z:3,' : '); for i:=1 to M do write(alphabet[b[i]]); writeln; end; Procedure SwapB(var B:barray;i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure PermuteAll(B:barray;N:byte); var i,k,j : byte; begin WriteB(B); while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit; for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(B,i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(B,j,N+i+1-j); WriteB(B); end; end; begin readln(N,M); for i:=1 to M do b[i]:=i; PermuteAll(B,M); while (true) do begin i:=M; while (i>0) and (b[i]=N-m+i) do Dec(i); if i=0 then exit; Inc(B[i]); for j:=i+1 to M do B[j]:=B[j-1]+1; PermuteAll(B,M); end; readln; end. Пояснения к программе: 1. Главная программа вводит числа N, M и генерирует по опис анному выше алгоритму все сочетания из N по M. Для каждого построенного в в екторе B сочетания вызывается процедура PermuteAll, которой в качестве параметр ов передаются текущее сочетание B и количество элементов в нем M. Процедур а PermuteAll генерирует для полученного сочетания все возможные перестановки. 2. Массив B передается в процедуру PermuteAll по значению (при объявлении процедуры при параметре B нет ключевого слова VAR) и потому изменения массива B в процедуре PermuteAll не влияют н а содержимое массива B в главной программ е. 3. В то же время для того, что бы процедура SwapB могла обмени вать значения в B и возвращать измененный массив в вызывающую ее процеду ру PermuteAll, массив B добавлен в параметры проце дуры SwapB с передачей по адресу - используя ключевое слово VAR. 4. Для передачи массива в качестве параметра заведен специальный тип BARRAY. 5. Для подсчета всех сгенерированных размещений используется переменная Z в процедуре WriteB. 5 Перестановки с повторениями Перестановки с повторениями допускают повторное исп ользование элементов. Например, пусть имеем множество, состоящее из двух символов A и двух символов B. Тогда все перестановки с повторениями из этих символо в будут таковы: AABB ABBA BABA ABAB BAAB BBAA В общем случае, если имеем N1 предметов 1-го вида N2 предметов 2-го вида ... Nk предметов K-го вида Общее количество перестановок може т быть вычислено по формуле N!/ (N1!*N2!*..*Nk!) Алгоритм аналогичен генерации пере становок без повторений за исключением формирования начальной переста новки: i=0; Для j от 1 до k Для m от 1 до N[j] i=i+1; B[i]=j; Ниже приводится программа генерации перестановок с в озвращениями. Количество K различных типов предметов, обозначенных лати нскими буквами вводится с клавиатуры. С клавиатуры также вводятся количества NN[j] предметов каждого типа. Сумма введенных NN[j] определяет общее количество элемен тов в каждой из генерируемых перестаново к. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1..100] of byte; N,i,j,k,m : byte; NN : array [1..100] of longint; Procedure SwapB(i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure WriteB; begin for i:=1 to N do write(alphabet[b[i]]); writeln; end; begin readln(K); N:=0; for i:=1 to K do begin read(NN[i]); N:=N+NN[i]; end; i:=0; for j:=1 to k do for m:=1 to NN[j] do begin Inc(i); B[i]:=j; end; WriteB; while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit; for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(j,N+i+1-j); WriteB; end; end. 6 Сочетания с повторениями Для множества символов от A до C и размера M=3 сочетания с повторениями будут следующими: CCC BCC BBC BBB ACC ABC ABB AAC AAB AAA Общее количество сочетаний = (N+M-1)! / (M!*(N-1)!) где N - количество симво лов M - по сколько символов в сочетании Основная идея генерации таких сочетаний с повторения ми заключается в следующем: Сочетания записываем в виде (N-1)-го нуля и M единиц ,где еди ницы заменяют символы, а нули выступают в pоли pазделителей. Напpимеp: ABB - 1 0 1 1 AAC - 1 1 0 0 1 C C C - 0 0 1 1 1 A B B A A C C C C При таком подходе для решения задачи достаточно сгене рировать все перестановки из M единиц и N-1-г о нуля. Ниже приводится программа, которая решает поставленн ую задачу. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1..100] of byte; N,i,j,k,M,N1 : byte; Procedure SwapB(i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure WriteB; var i,j : byte; begin j:=1; for i:=1 to N do if b[i]=0 then Inc(j) else write(alphabet[j]); writeln; end; begin readln(N1,M); N:=N1-1+M; for i:=1 to n1-1 do b[i]:=0; for i:=n1 to n1+m-1 do b[i]:=1; WriteB; while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit; for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(j,N+i+1-j); WriteB; end; end. Пояснения к программе: 1. Начальная перестановка формируется последовательн о из N1-1 нулей и M единиц. 2. В программе вывода перестановки WriteB осуществлены изме нения, соответствующие замыслу (нули - разделители, единицы - символы). Есл и текущий элемент массива B равен 0, то "становится активным" следующий сим вол. Если текущий символ массива B равен 1, то текущий активный символ выво дится на экран. Заключение Все программы для большей наглядности в качестве иллю страции оперируют с массивом символов от A до Z. Очевидно, что предлагаемые алгоритмы и программы практически не изменяются при работе с массивами элементов любого типа, требуемого по условиям задачи (например, массивам и чисел, слов, геометрических фигур и т.д.) Литература 1. Абдеев Р. Ф. Философия информационной цивилизации. - М.: Владос, 1994. 2. Адамар Ж. Исследование психологии процесса изобретения в области мате матики. - М.: Сов. радио, 1970. 3. Болтянский В.Г. Информатика и преподавание математики// Математика в шко ле. 1989. № 4.-С.86-90 4. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум. - М.: Радио и связь, 1982. 5. Вирт Н. Алгоритмы+Структуры данных=Программа. - М.:Мир, 1989 6. Вирт Н. Систематическое программирование: Введение. - М.: Мир, 1977. 7. Громов Г.Р. Очерки информационной технологии. - М.: ИнфоАрт, 1993. 8. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978. 9. Ильенков Э. В. Философия и культура. - М.: Полит. лит., 1991. 10. Йодан Э. Структурное проектирование и конструирован ие программ. - М.: Мир, 1979. 11. Майерс Г. Надежность программного обеспечения. - М.: Мир, 1980. 12. Махмутов М.И. Организация проблемного обучения в школе. - М., 1986.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Когда в России выдаётся тёплая зима, из собора парижского Дома инвалидов доносится голос Наполеона:
- Вот щас бы!!!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Генерация комбинаторных объектов", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru