Генерация подмножеств в лексикографическом порядке.

Определение. Пусть A=(x1,…,xn) и B=(y1,…,yn), xi,yiÎ{0,1}, 1£i£n. Будем говорить, что множество А предшествует множеству B лексикографическом порядке ,если существует i, 1£i£n, xi<yi и xj=yj для любого j, 1£j<i; обозначим это А<B.

Упражнение. Пусть 0 £ a < b <2n, a, b - натуральные; представим a и b в двоичной системе с выписыванием всех n двоичных разрядов и пусть a = и b = . Доказать, что тогда (x1,...,xn) < (y1,...,yn).

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

program SET1(, output);

const n= ; n1= ; {n1=n+1}

var s : array [1..n1] of 0..1;

i,j : integer;

begin

for i:=1 to n1 do s[i]:=0;

while s[n1]=0 do

begin

for i:=1 to n do write(s[i]); writeln;

i:=1;

{**} while s[i]=1 do

begin s[i]:=0; i:=i+1 end;

{*} s[i]:=1

end

end.

Комментарий. Пусть множеству s соответствует число s, тогда множеству, следующему за s, соответствует число s+1.

Упражнения. 1.Доказать корректность алгоритма SET1.

2. Показать, что условие цикла {**} проверяется 2n+1-1 раз.

3. Определить вычислительную сложность алгоритма.

4. Написать программу генерации всех подмножеств в лексикографическом порядке, если s описано как SET OF 1..n.

Замечания. 1.Следует отметить, что в системе команд любой вычислительной машины имеются команды, выполняющие арифметическое сложение двоичных последовательностей определенной длин, таких, как 8 бит - 1 байт, 16 - 2 байта и тому подобное. Кроме того, часто имеются специальные программные конструкции (например, макрокоманды, выполняющие сложение более длинных двоичных последовательностей). Непосредственное применение таких команд в программе SET1 может существенно улучшить ее временные характеристики.

2. Для построения других алгоритмов генерации подмножеств, представляет интерес свойства последовательности значений переменной i перед исполнением оператора {*}. Заметим, что этот оператор {*} исполняется 2n раз, при этом последнее значение i=n+1 приводит к окончанию генерации всех подмножеств для множества из n-элементов. Пусть In обозначает эту последовательность значений переменной i за исключением последнего. In можно трактовать как последовательность номеров позиций младшей единицы в двоичном разложении чисел 1, 2, ..., 2n-1. По построению двоичной позиционной системы последовательность In удовлетворяет следующему рекурсивному определению

I1=1, In= In-1,n, In-1

(первый раз единица в n-ой позиции появляется для числа 2n-1, при этом во всех других позициях с 1-ой по (n-1)-ую значения становятся нулевыми, затем для чисел 2n-1+1,..., 2n-1 повторяется процесс заполнения единицами позиций с номерами меньшими n).

Упражнение. Доказать, что если In-1=i1, i2, ..., i , n>1, то In=1, i1+1, 1, i2+1, 1, ..., i +1, 1.

 








Дата добавления: 2015-08-11; просмотров: 870;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.