КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Генерация мультимножеств
Begin GRAY (n) GRAY (m-1) end end; begin for i:=1 to n do s[i]:=0; end. Упражнение. 1. Проверить, что при n=4 программа действительно генерирует требуемую последовательность. 2. Показать, что в процессе исполнения оператора строки {2} вызов процедуры GRAY происходит 2m-1 раз. 3. Доказать корректность программы SET2. 4. Определить вычислительную сложность программы SET2. Упорядоченную последовательность двоичных n-разрядных наборов обычно называют кодами Грея n-го порядка(происхождение этого названия см. [4]), если каждый набор в этой последовательности отличается от предыдущего изменением только одного разряда. Пусть задана некоторая перестановка <a1,...,an>. Нетрудно видеть, что если мы в строке {1} программы SET2 заменим оператор печати на write (s[a[i]]), то модернизируемая программа будет также строить коды Грея. Их обычно называют симметрично-отраженными. Можно показать, что существует n! различных симметрично-отраженных кодов Грея, начинающихся с нулевого кодового слова. Упражнение. Для какого наименьшего n существует несимметрично отраженный код Грея, начинающийся с нулевого кодового слова. Перейдем к построению итеративного варианта алгоритма SET2. Здесь достаточно учесть равенство In = Pn: program SET3; const n=; var s: array [1..n] of 0..1; i,j,k,p: integer; {0} for k:=1 to n do s[k]:=0; i:=0; {i определяет число сгенерированных подмножеств} repeat for k:=1 to n do write(s[k]); writeln; {1} i:=i+1; p:=1; j:=i; {2} while j mod 2 = 0 do begin {j*2p-1 = i} j:=j div 2; p:= p+1 end; {p определяет номер изменяемого разряда} if p <= n then {3} s[p]:=1-s[p] {4} until p>n end. Комментарий. Пусть после выполнения оператора {1} i имеет двоичное разложение bm...bp0...0, где bp=1 (или до выполнения оператора {1} значение i в двоичной системе выглядело как bm...bp+101...1 (сравните с программой SET1)). Для определения p достаточно выполнить оператор {2}. Условие {4} означает, что уже сгенерировано 2n кодовых слов.
Упражнение. Определить вычислительную сложность программы SET3. Улучшить временные характеристики приведенной программы можно за счет замены цикла {2} более совершенной конструкцией. Здесь возможны два подхода. Первый основан на непосредственном применении машинных команд, а второй - на использовании определенной закономерности в последовательности номеров изменяемых разрядов в текущем кодовом слове. Перейдем к изложению первого способа. Предположим, что порядок генерируемых кодовых слов меньше чем длина машинного слова в арифметических и логических командах ЭВМ. Пусть знак º обозначает команду по разрядного сравнения двух слов (т.е. в результате получается новое слово, в котором единицы стоят только а тех разрядах, которые различны в заданных словах). Знак & обозначает поразрядную конъюнкцию двух слов. Применив эти команды, можно улучшить временные характеристики программы SET3. В самом деле s можно хранить в упакованном виде в одном слове. Пусть в i1 хранится значение i до выполнения оператора {1}, т.е. i1=i-1. Тогда оператор {0} эквивалентен s:=0; оператор {2} - p:=(iºi1)&i; оператор {3} - s:=sºp; условие {4} записывается как i=2n. Пример. Пусть длина машинного слова равна 16. После оператора {1} i=3984. Тогда машинное представление: i=0000 1111 1001 0000 i1=i-1=0000 1111 1000 1111 iºi1=0000 0000 0001 1111 p=(iºi1)&i=0000 0000 0001 0000 Случай когда n совпадает с длиной машинного слова, поддается подобной модификации, но требует учета ‘переполнения’ слов. Упражнение. Используя равенство In = Pn показать, что если 0£i<n и bnbn-1...b0-двоичное представление i, записанное в n+1 позиции и Gi=g1g2...gn i-ый по порядку код Грея, генерируемый программой SET3, то gk = bn-k+bn-k+1, 1£k£n. Построить программу генерации кодов Грея на основе последнего равенства. Второй способ [4] строится на хранении в памяти последовательности значений номеров изменяемых разрядов в текущем кодовом слове, т.е. на хранении значений последовательности Pn. Вследствие рекурсивного определения Pn естественно организовать хранение ее элементов в виде стека. В этом случае генерация ее элементов может быть описана по следующей итеративной схеме:
1) {инициализация стека} Вначале стек содержит элементы n,n-1,...,1 (с 1 в вершине). 2) Алгоритм выталкивает верхний элемент i и помещает его в последовательность. 3) В стек добавляются элементы i-1,i-2,...,1. 4) Повторяются выполнения с шага 2 до тех пор, пока стек не опустошится. Упражнения. 1.Доказать корректность приведенного алгоритма. 2. Написать программу генерации Pn по этому алгоритму. 3. Оценить временную и емкостную сложность полученной программы. Отметим, что занесение значений в стек фактически совпадает с занесением значений параметра m в стек исполняемой программы при вызовах процедуры GRAY из SET2, и поэтому не дает существенного выигрыша по сравнению с алгоритмами SET2 и SET3. Однако если организовать стек в виде списочной структуры особого типа, при которой действия по включению на шаге 3 элементов i-1,i-2,...,1 в стек выполняются за постоянное число операций, независящих от i, то можно заметно улучшить временные характеристики алгоритма. Пусть стек хранится в массиве (t0,t1,...,tn), при этом t0 указывает на верхний элемент в стеке, и для каждого i>0 ti определяет значение расположенное в стеке под элементом i, если i находится в стеке. Заметим, что элементы i-1,i-2,...,1 помещаются в стек после удаления элемента i за счет изменения значения t0 на 1.Если i нет в стеке, то значение ti может быть, вообще говоря, любым, так как не оказывает никакого влияния на вычисления. Однако его значение разумно установить равным i+1, т.к. по свойству алгоритма, в случае когда в следующий раз элемент i+1 будет помещен в стек, элементом, находящимся над ним, будет i. Удаление из стека элемента i в этом случае может быть осуществлено за счет пересылки ti-1 в ti. Алгоритм порождения последовательности Pn на языке Паскаль может быть записан так: program PN; const n=; n1 =; {n1=n+1; } var t: array [0..n] of 1..n1; {стек} p: integer; begin for p:=0 to n do t[p]:=p+1; {инициализация стека} p:=0;
while p<n1 do begin p:=t[0]; {1} if p<>n1 then begin writeln (p); {2} t[p-1]:=t[p]; {3} t[p]:=p+1; if p<>1 then t[0]:=1 {4} end end end. Упражнения. 1.Протестируйте программу PN при n=3. 2. Докажите корректность алгоритма генерации последовательности Pn для произвольного n. Замечание. Если оператор {1} поместить после оператора {2}, то оператор {4} можно исключить, т.к. в этом случае неверные значения t[0] будут исправляться оператором {3}. Учитывая последнее замечание, алгоритм генерации кодов Грея на основе порождения последовательности Pn по алгоритму Pn может быть записан так: program SET4; const n =; n1 =; n2 =; {n1=n+1; n2= n+2} var t: array [0..n1] of 1..n2; s: array [1..n1] of 0..1; i,p: integer; begin for i:=1 to n1 do begin s[i]:=0; t[i]:=i+1 {инициализация стека} end; p:=0; t[0]:=1; {1} while p<n1 do begin for i:=1 to n do write(s[i]); writeln; p:=t[0]; s[p]:=1-s[p]; t[0]:=1; t[p-1]:=t[p]; t[p]:=p+1 end end. Комментарий. Добавление в массивы t и s n+1-х элементов сделано для того, чтобы сократить число проверок внутри цикла {1}. Для представления данных некоторых задач более естественными, чем множества являются множества с повторениями элементов, или мультимножества. При записи мультимножеств с каждым элементом удобно связывать неотрицательное целое число, указывающее количество повторений этого элемента. Пример. Мультимножество (x, x, x, y, y, z, z, z, u) удобно записывать как (3×x, 2×y, 3×z, 1×u). Применение коэффициентов кратности удобно также для представления мультимножеств при построении алгоритмов. Пусть x<y<z<u, тогда множество (3×x, 2×y, 3×z, 1×u) представимо как (3,2,3,1). Таким образом, если для представления подмножеств некоторого базового множества из n элементов были использованы n-последовательности нулей и единиц, то для представления мультимножеств, которые можно построить на базе этого множества, удобно использовать n-кортежи неотрицательных целых чисел. Упражнения. 1. Пусть задано мультимножество A=(m1,....,mn), mi³0, 1£i£n. Доказать, что А имеет мультиподмножеств. 2. Пусть A=(m,...,m), где базовое множество содержит n элементов. Написать программу генерации всех мультиподмножеств А в лексикографическом порядке. заметим, что подобная генерация фактически совпадает с выводом всех чисел от 0 до mn-1 d m-ричной позиционной системе.
3.Написать программу генерации всех мультиподмножеств А из предыдущего упражнения, при котором каждое последующее мультиподмножество отличается от предыдущего вставкой или удалением одного элемента. Генерация начинается с представления пустого множества. (Вначале постройте рекурсивный алгоритм генерации, например, воспользовавшись последовательностью C10; C20;...; CP0; CP1;...; C11; C12;...; CP2; CP3;...,где р=mn, которая определяет генерацию мультимножеств (n+1)-го порядка. Затем постройте итеративный алгоритм, подобный SET3.)
Дата добавления: 2014-01-04; Просмотров: 419; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |