Реферати

Курсова робота: Деякі способи розбивки безлічей

Профспілки як форма соціального партнерства. Зміст Уведення ...... 3 Поняття системи соціального партнерства і роль профспілок ...... 4 Участь російських профспілок у становленні механізму соціального партнерства ...... 8

Бухгалтерська звітність при реорганізації організацій. Ліквідація фірм по Росії Усі види ліквідації юр. обличчя надійно Повна гарантія Об'єднані Юристи Звітність через інтернет З "Такском-Спринтер" здача

Расчетно графічне завдання за курсом загальної теорії. БЛОК I "ОБЩЯЯ ТЕОРІЯ СТАТИСТИКИ" ЗАДАЧА № 1 За даними про поквартальний товарообіг підприємства в 1998 році: Показники Квартал 1998 р. Обсяг товарообігу (тис. руб.)

Крос-культурні розходження і проблеми просування в міжнародному маркетингу. Балтійська Міжнародна академія Доповідь на тему: " Крос-культурні розходження і проблеми просування в міжнародному маркетингу Виконав: студент 4 курси

Загальні елементи SQL. Загальні елементи SQL 5.1 <Символ> (<character>) Функція Визначає термінальні символи мови й елементи рядків. Формат <character> ::=

Уведення

У наш бурхливо розвивається століття, здавалося б, всі алгоритми, які можна придумати, уже придумані. Але іноді зустрічаються задачі, для яких немає придатних алгоритмів. Бути може тому, що задача рідко чи зустрічається, швидше за все для цієї задачі немає ефективних алгоритмів (а, швидше за все, їх і зовсім не існує).

У цій роботі буде обговорюватися тема розбивок безлічей.

У [1] автор дає кілька таких алгоритмів: генерування всіх підмножин n-елементної безлічі, генерування всіх k-елементних підмножин безлічі {1, ..., n} у лексикографічному порядку, генерування всіх розбивок безлічі {1, ..., n} (на цьому алгоритмі зупинимося подробней), перебування всіх розбивок числа.

Перший з цих алгоритмів використовує идеюбинарного коду Грея, інші засновані на чи видаленні додаванні одного елемента. Останній алгоритм використовує схему розбивки більшого числа на менші числа.

Постановка задачі

Формулювання першої задачі, що ми розглянемо, виглядає так: необхідно згенерувати всі розбивки безлічі, що містить n елементів.

Для формулювання другої задачі необхідно ввести деякі поняття.

Отже, дане безліч, що складається з n елементів. Кожен елемент цієї безлічі утворить деяке поняття. Два чи більше поняття можуть бути об'єднані в нове поняття. Відмітна риса понять - узяття їх у круглі дужки.

Задача виглядає так: згенерувати всі поняття, що можуть бути утворені з n елементів. Наприклад, для n=3 маємо такі поняття (круглі дужки на початку і наприкінці опущені для стислості): (*)**, (*)(*)*, (*)(*)(*), (**)*, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).

Математичне обґрунтування

Під розбивкою n-елементної безлічі Х на k блоків будемо розуміти довільне сімейство , таке, що для 1£і < j£k і для 1£i£k. Підмножини будемо називати блоками сімейства π. Безліч усіх розбивок безлічі Х на k блоків будемо позначати , а безліч усіх розбивок через П (Х). Очевидно, що (більш того, є розбивкою безлічі П (Х)).

Число Стирлинга другого рода(n,k) визначається як число розбивок n-елементної безлічі на k блоків:

де |X|=n.

Очевидно, що S(n,k)=0 для k > n. Приймають також S(0,0)=1, тому що порожнє сімейство блоків є відповідно до визначення розбивкою порожньої безлічі. З числами Стирлинга другого порядку зв'язано багато зацікавлених тотожностей:

S(n,k)=S(n-1,k-1)+k(n-1,k) для 0 < k < n, (1)

S(n,n)=1 для n≥0, (2)

S(n,0)=0 для n > 0. (3)

Формули (2) і (3) очевидні. Для доказу формули (1) розглянемо безліч усіх розбивок безлічі {1, ..., n} на k блоків. Ця безліч розпадається на два різних класи: тих розбивок, що містять одноелементний блок {n}, і тих розбивок, для яких n є елементом більшого (принаймні, двухелементного) блоку. Потужність першого класу дорівнює S(n-1,k-1), тобто така, яке число розбивок безлічі {1, ..., n-1} на (k-1) блоків. Потужність іншого класу складає k(n-1,k), тому що кожній розбивці безлічі {1, ..., n-1} на k блоків відповідає в цьому класі в точності k розбивок, утворених додаванням елемента n по черзі до кожного блоку.

Формули (1)-(3) дозволяють легко обчислювати значення S(n,k) навіть для великих значень n і k.

От інша рекуррентная залежність:

для k≥2. (4)

Для доказу тотожності розглянемо безліч усіх розбивок S(n,k) безлічі Х={1, ..., n}. Ця безліч розпадається на різні класи, що відповідають різним підмножинам безлічі Х, що є блоками, що містять елемент n. Відзначимо, що для кожної b-елементної підмножини утримуючого елемент n, існує в точності S(n-b,k-1) розбивок безлічі Х на k блоків, що містять В в якості блоку. Дійсно, кожна така розбивка однозначна відповідає розбивці безлічі Х\У на k-1 блоков. b-елементна безліч утримуюче елемент n, можна вибрати способами; таким чином,

Число Беллаопределяется як число всіх розбивок n-елементної безлічі

де |X|=n.

Іншими словами,

Доведемо рекуррентную залежність, зв'язану з числами Белла:

(5)

(приймаємо ). Доказ проводиться аналогічно доказу тотожності (4). Безліч усіх розбивок безлічі Х={1, ..., n+1} можна розбити на різні класи в залежності від блоку В, що містить елемент n+1, чи - що рівнозначно - у залежності від безлічі Х\В. Для кожної безлічі існує в точності розбивок безлічі Х, що містять В в якості блоку. Групуючи наші класи в залежності від потужності безлічі Х\У, одержуємо формулу (5).

Тепер опишемо алгоритм генерування всіх розбивок безлічі.

Відзначимо, що кожна розбивка p безлічі {1,..., n} однозначно визначає розбивка безлічі {1,...,n-1}, що виникло з p після видалення елемента n з відповідного блоку (і видаленню простого блоку, що утворився, якщо елемент n утворював одноелементний блок). Навпроти, якщо дана розбивка безлічі {1, ..., n-1}, легко знайти всі розбивки π безлічі {1, ..., n}, такі що , тобто наступні розбивки:

Якщо нам даний список усіх розбивок безлічі {1, ..., n-1}, те список усіх розбивок безлічі {1, ...,n}, будемо створювати, заміняючи кожну розбивку σ у списку на відповідну йому послідовність (6). Якщо звернути порядок послідовності (6) для кожної другої розбивки , то елемент n буде рухатися поперемінно вперед та назад, і розбивки "на стику" послідовностей, утворених із сусідніх розбивок списку мало відрізняються один від іншого.

Розбивка безлічі {1, ..., n} ми будемо представляти за допомогою послідовності блоків, упорядкованої по зростанню самого маленького елемента в блоці. Цей найменший елемент блоку ми будемо називати номером блоку. Відзначимо, що номера сусідніх блоків, узагалі говорячи, не є сусідніми натуральними числами. У цьому алгоритмі ми будемо використовувати перемінні pred[і], sled[і], 1≤і≤n, що містять відповідно номер попереднього і номер наступного блоку з номером і (sled[і]=0, якщо блок з номером і є останнім блоком розбивки). Для кожного елемента і, 1≤і≤n, номер блоку, що містить елемент і, буде зберігатися в перемінної blok[і], напрямок, у якому "рухається" елемент і, буде закодовано в булевской перемінної wper[і] (wper[і]=true, якщо і рухається вперед).

Можна показати, що середнє число кроків, необхідних для побудови кожного наступного розбивки, обмежено постійної, що не залежить від n(звичайно, якщо не враховувати число кроків, необхідних для написання розбивки).

(1 2 3 4)

(1 2 3)(4)

(1 2)(3)(4)

(1 2)(3 4)

(1 2 4)(3)

(1 4)(2)(3)

(1)(2 4)(3)

(1)(2)(3 4)

(1)(2)(3)(4)

(1)(2 3)(4)

(1)(2 3 4)

(1 4)(2 3)

(1 3 4)(2)

(1 3)(2 4)

(1 3)(2)(4)

Табл.1. Послідовність розбивок безлічі {1,2,3,4}

Опишемо тепер алгоритм рішення задачі про перерахування всіх понять.

Рекурсивний алгоритм використовувати не можна, тому що всі рішення подзадачи меншої розмірності необхідно скомбінувати з усіма рішеннями подзадачи розмірності, що залишилася. Тому, будемо просто перебирати усі варіанти.

Ідея така: зберігаємо всі розбивки меншої розмірності і комбінуємо їхній так, щоб

1) вони не повторювалися;

2) кількість елементів нової розбивки не було б більше кількості елементів n.

Отже, нехай ми маємо два початкових стани: (*) і *. Для n=2 маємо тільки одне вихідне поняття: (*)*. Для n=3 необхідно скомбінувати усі відомі раніше стани з урахуванням умов 1)-2).

Умову 1) забезпечимо з таких розумінь: кожному елементу привласнити порядковий номер і комбінувати поняття так, щоб порядковий номер наступного поняття не перевершував порядковий номер попереднього поняття, а також стежити, щоб виконувалася умова 2). Звідси видно, що повторень не буде, і ми перелічимо всі поняття.

Для реалізації умови 2) необхідно кожному поняттю привласнити число, що буде показувати кількість елементів цього стану.

Також необхідно мати деякий масив, кожен елемент якого буде вказувати на поняття, що відповідає номеру поняття у вихідному понятті. Елементи цього масиву будуть мінятися, відповідно до перебору варіантів.

Мова програмування

Для реалізації алгоритмів була обрана мова програмування TurboPascal 7.0. У цій мові є всі необхідні засоби для цих алгоритмів, і сама мова є простим для розуміння. Тому вибір припав саме на нього.

Для алгоритмів нам знадобляться поняття покажчиків і записів.

Запис у Раsсаl'е описується так:

< ім'я_типу > =| < ім'я_перемінної > :record

< список полів і їхніх типів >

end;

Наприклад,

Varpoint:record

x,y: integer;

color:byte

end;

Звертаються до полів запису так:

Nx:=point.x+point.y;

Point.color:=3;

Покажчики описуються так:

< ім'я_типу > =| < ім'я_перемінної > :^ < ім'я типу >

Наприклад,k:^integer- покажчик на ціле. Звертання до вмісту покажчика:t:=k^, а запис значення в комірку пам'яті, куди вказує k, виглядає так:k^:=10. Але, чтобі використовувати покажчики, необхідно спочатку виділити пам'ять під них. Це робиться за допомогою командиnеw:

New(k);

Щоб звільнити пам'ять, якщо покажчик уже не буде потрібний, використовують

Dispose(k);

Оператори присвоювання, арифметичних операцій і циклів схожі в багатьох мовах, тому їх описувати не коштує.

Реалізація алгоритмів

Генерування розбивок безлічі

У табл.1 представлені розбивки для n=4, генерируемие наступним алгоритмом:

program razbienie_mnozhestwa(input,output);

var i,j,k,n:byte;wper:array[1..255]of boolean;

sled,pred,blok:array[1..255]of byte;

procedure write_razbienie; {процедура, що виписує розбивку на екран}

var

i,j:byte;

begin

j:=1; {номер першого блоку}

repeat

write('(');

for і:=j to n do if blok[і]=j then write(і, ' '); {есличислоіизблокаj, топишеметочисло}

j:=sled[j]; {наступний по номері блок}

write(')');

until j=0;

WRITELN

end;

begin

write('input n:');

readln(n); {уводимо кількість елементів безлічі}

for і:=1 to n do begin {строимразбиение{{1, ..., n}}}

blok[i]:=1;

wper[i]:=true

end;

sled[1]:=0;

write_razbienie; {виписатьразбиение}

j:=n; {активний елемент}

while j > 1 do begin {задача циклу - переміщення "активного" елементаjв сусідній блок - у попередній чи наступний (в останньому випадку може виникнути необхідність створення нового блоку виду {j}, а потім визначення активного елемента в знову утвореній розбивці}

k:=blok[j]; {процес переносу активного елемента;k- номер активного блоку}

if wper[j] then begin {jдвижетсявперед}

if sled[k]=0 then begin {k-последнийблок}

sled[k]:=j; {j-одноелементний блок}

pred[j]:=k;

sled[j]:=0

end;

if sled[k] > j then begin {jобразуетновийблок}

pred[j]:=k; {усі блоки праворуч від блоку з номеромксодержат елементи, большиеj. Звідси випливає, чтоjобразует новий одноелементний блок}

sled[j]:=sled[k];

pred[sled[j]]:=j;

sled[k]:=j

end;

blok[j]:=sled[k] {переносимо наш елемент в активний блок з номеромк}

end

else begin {jдвижетсяназад}

blok[j]:=pred[k]; {помещаемjвпредидущийблок}

if k=j then if sled[k]=0 then sled[pred[k]]:=0 else begin

sled[pred[k]]:=sled[k];

pred[sled[k]]:=pred[k]

end

end;

write_razbienie;

j:=n;

while(j > 1)and

((wper[j]and(blok[j]=j))or(not wper[j]and(blok[j]=1))) do begin

wper[j]:=not wper[j];

dec(j)

end

end

end.

Кількість усіх розбивок можна порахувати використовуючи числа Белла і рекуррентную формулу (5).

Генерування всіх понять

Для реалізації даної задачі на Раsсаl'е вводимо наступні типи даних і перемінних:

1) тип k - покажчик на запис, полючи якої: s - буде містити поняття; p - кількість елементів у понятті; next - посилання на наступне поняття;

2) перемінні f, pot типу k; f - указує на перше поняття, тобто на просте поняття *; pot - поточне поняття;

3) масив str1 типу k - буде містити посилання на кожне поняття в складеному понятті;

program dyscretics_optimisation(input,output);

uses crt;

const

max=12;

r:byte=0;

type

k=^el;

El=record

S: string;

P: 1..Max-1;

Next: k

End;

Label met;

Var

Pot, f, l: k;

Str1: array[1..Max]of k;

Pow: 2..Max;

K1, i, j, ll: 1..Max;

Sum: 0..Max;

Fil: text;

Ki:string[2];

begin

Readln(POW); {уводимо кількість простих понять}

Str(POW, ki);

Assign(fil,ki+'.mvp'); { поняття, щовийшли, будемо записувати у файл, що містить у своєму імені кількість елементів безлічі і з розширенням ".mvp"}

Rewrite(fil);

New(f); {виділяємо пам'ять під перше поняття}

Pot:=f;

F^. S:='*'; {і инициализируем його}

F^.P:=1;

New(f^.next); {виділяємо пам'ять під друге поняття}

Pot:=f^.next;

Pot^.s:='(*)'; {і також його инициализируем}

Pot^.p:=1;

Pot^.next:=nil;

for і:=2 to POW do begin {основнойциклпрограмми}

Forj:=1toidostr1[j]:=f; {установлюємо початкові покажчики поняття, размерностиі, на перше поняття}

Ifi=POWthenstr1[1]:=f^.next; {еслиіравно кількості елементів безлічі, те необхідно змінити покажчик на перше подпонятие нашого поняття, тому що уже відзначалося вище, поняття, що складається тільки з простих подпонятий виводити не треба. Але, такі поняття залишаємо для подзадач меншої розмірності, тому що в комбінації з рішеннями інших подзадач, одержимо вже поняття, що містить не тільки прості поняття}

Whilestr1[1] < > nildobegin{поки покажчик першого подпонятия не досягне кінця списку подпонятий виконувати}

New(pot^.next); {виділити пам'ять під чергове поняття}

Sum:=0; {ця перемінна служить як лічильник, що після наступного циклу буде містити кількість елементів у новому понятті}

K1:=1; {номер першого подпонятия. Перше подпонятие має завжди, якщо можна так виразитися, "більш пізня адреса", чи, точніше, усі подпонятия, що випливає за першим, отримані чи раніш одночасно з ним. Це також стосується другого подпонятие щодо третього, четвертого і т.д., третього щодо четвертого, п'ятого і т.д., і т. д.}

Ifi=powthenpot^.next^.s:=''elsepot^.next^.s:='('; {еслиіравно кількості елементів безлічі, то нам не потрібні дужки на початку (їх домовилися опустити)}

Whilesum < idobegin{покаколичество елементів у новому понятті менше розмірності подзадачи, виконати}

Pot^.next^.s:=pot^.next^.s+str1[k1]^.s;{додати в поняття подпонятие з номеромк1}

Sum:=sum+str1[k1]^.p; {додати розмірність, доданого подпонятия}

Inc(k1); {увеличитьк1на 1}

End;

If(sum > і)or(k1=2)thenbegin{якщо кількість елементів отриманого поняття більше розмірності задачі илик1=2, тобто додане тільки одне поняття в подпонятие, те, щоб уникнути зайвих дужок і неправильних рішень виконати}

Dispose(pot^.next); {звільнити пам'ять, займану цим "неправильним" поняттям}

Pot^.next:=nil;{указати, що попереднє поняття було останнім}

Ifk1=2thenbreak{еслик1=2, то вийти з основного циклу програми}

End

Elsebegin

Ifi=POWthenbegin{якщо розмірність поточної подзадачи дорівнює розмірності основної задачі, те}

Writeln(fil,pot^.next^.s); {записати поняття у файл}

Writeln(pot^.next^.s); {і вивести на екран}

Dispose(pot^.next); {звільнити пам'ять, займану поняттям, тому що поняття розмірності задачі нам більше не знадобляться}

Pot^.next:=nil

End

Elsebegin{інакше инициализируем поняття до кінця}

Pot:=pot^.next;

Pot^.s:=pot^.s+')'; {закриваемскобку}

Pot^.next:=nil; {указуємо, що це поняття останнє в списку}

Pot^.p:=I{указуємо кількість елементів, що містяться в понятті}

End

End;

Forj:=k1-1downto2dobegin{k1зараз показує кількість подпонятий останнього поняття плюс 1. Тому в цьому циклі, що спробує визначити наступну комбінацію понять і використовується переменнаяк1. Ця частина програми розглядає випадок, коли подпонятия будуть ставати не наступними за списком подпонятиями (принаймні не усі), а будуть відбуватися інші переходи. Тобто цей цикл розрахований на те, щоб не дозволити подпонятию з великим номером за списком у понятті бути великим по абсолютній адресі (за часом створення)}

If (str1[j]^.next=str1[j-1]) and (str1[j+1]=str1[j]) or ((j=k1-1) and (str1[j] < >

Str1[j-1]))thenbegin{якщо за подпонятием з номеромjпо списку випливає подпонятие з номеромj-1і подпонятия з номеромjиj+1збігаються, илиjравно кількості подпонятий і останні два поняття збігаються (порівняння йде по абсолютних адресах розташування понять у пам'яті), те}

str1[j]:=str1[j]^.next; {подпонятие з номеромjпереходит на наступне за списком подпонятие}

Forj:=J+1tok1-1dostr1[j]:=f; {а всі наступні подпонятия, стають рівними першому (елементарному) подпонятию}

gotomet{хоча застосування оператора безумовного переходу вважається поганим стилем програмування, але тут він виправданий, щоб не заплутувати програму новими циклами}

End;

End;

Forj:=k1-1downto2dobegin{новий цикл, що переключить відповідні подпонятия. Ми виділяємо це в новий цикл, тому що потрібно було перевірити на наявність "граничних" переходів (див. попередній цикл)}

Ifstr1[j] < > str1[j-1]thenbegin{якщо подпонятия з номерамиjи (j-1) не збігаються, те}

Str1[j]:=str1[j]^.next; {подпонятие з номеромjстановится наступним за списком (часу створення подпонятием)}

Forj:=j+1tok1dostr1[j]:=f; {а всі идущие за ним подпонятия в списку подпонятий, що складають поняття стають елементарними}

gotomet{виходимо з циклу}

End

End;

Str1[1]:=str1[1]^.next; {якщо не виконалися умови попередніх двох циклів, то настав час переключати перше подпонятие}

forj:=2toidostr1[j]:=f; {і, соответствено, що випливають подпонятия сделатьелементарними}

Met: end

End;

Close(fil);{закритьфайл}

Repeat {і}

Pot:=f^.next;

Dispose(f); {звільнити пам'ять, займану списком усіх можливих подпонятий}

F:=pot

Until f < > nil

end.

Література

1. В. Липский, Комбінаторика для програмістів, пров. з польського, М. - Світ,1988