видалення елемента 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) необхідно кожному поняттю присвоїти число, яке буде показувати кількість елементів цього стану.
Також необхідно мати деякий масив, кожен елемент якого буде вказувати на поняття, що відповідає номеру поняття в вихідному понятті. Елементи цього масиву будуть змінюватися, відповідно з перебором варіантів.
В
Мова програмування
Для реалізації алгоритмів була обрана мова програмування Turbo Pascal 7.0. У цій мові є всі необхідні кошти для цих алгоритмів, і сама мова є простим для розуміння. Тому вибір ліг саме на нього. p> Для алгоритмів нам знадобляться поняття покажчиків і записів.
Запис у Pascal'е описується так:
<імя_тіпа> = | <ім'я_змінної>: record
<список полів і їх типів>
end;
Наприклад,
Var point: record
x, y: integer;
color: byte
end;
Звертаються до полів запису так:
Nx: = point.x + point.y;
Point . color : = 3;
Покажчики описуються так:
<імя_тіпа> = | <ім'я_змінної>: ^ < ім'я типу >
Наприклад, k : ^ integer - покажчик на ціле. Звернення до вм...
