дку зростання. Сполучення з двох чисел (k = 2) друкуються так:
i1: = 1 to n do
for i2: = i1 + 1 to n do (i1, '', i2);
Сполучення з трьох чисел (k = 3) так:
for i1: = 1 to n doi2: = i1 + 1 to n doi3: = i2 + 1 to n do (i1, '', i2, '', i3);
Однак, якщо кількість чисел у поєднанні задається змінною, то доведеться вдатися до рекурсії.
Combinations (, k: integer;
// Масив, в якому будемо формувати поєднання
var Indexes: array of integer;
// Лічильник глибини рекурсії: integer);
var, i_min: integer;: string; d
end;
.6 Завдання на графах
Графом називають графічне зображення, що складається з вершин (вузлів) і з'єднують деякі пари вершин ребер (рис. 11а).
Більш строго: граф - сукупність безлічі вершин і безлічі ребер. Безліч ребер - підмножина евклідова квадрата безлічі вершин (тобто ребро з'єднує рівно дві вершини). p> Ребер можна також присвоїти напрямок. Граф в цьому випадку називається орієнтованим (рис. 11б). br/>В
Рис. 11. (А) Граф. (Б) Орієнтований граф. br/>
Теорія графів знаходить застосування в самих різних областях. Кілька прикладів:
Логістика та транспортні системи. Вершинами будуть склади з товарами або пункти призначення, а ребра - дороги, їх з'єднують. p> Маршрутизація мереж. Вершини - комп'ютери, з'єднані в мережу, ребра - зв'язки між ними. Вирішується завдання про шляхи передачі даних з одного комп'ютера на інший. p> Комп'ютерна хімія. Моделі у вигляді графів використовуються для опису шляхів протікання складних реакцій. Вершини - беруть участь у реакціях речовини, ребра - шляхи перетворень речовин. Також графом є ​​зображення структур молекул: вершини - атоми, ребра - хімічні зв'язки. p> Електричні мережі.
Сайти в Інтернеті можна вважати вузлами орієнтованого графа, ребрами якого будуть гіперпосилання.
Сучасна теорія графів являє собою потужну формальну систему, яка має неозоре безліч застосувань.
Шляхом або ланцюгом у графі називається послідовність вершин, в якій кожна вершина з'єднана ребром з наступного. Шляхи, в яких початкова та кінцева вершина збігаються, називають циклами. Якщо для кожної пари вершин існує шлях їх з'єднують, то такий граф називають зв'язковим. p> У програмуванні використовуються три способи зберігання в пам'яті інформації про структуру графів.
) Матриці суміжності
Квадратна матриця M, де як рядки, так і стовпці відповідають вершинам графа. Якщо вершини з номерами i та j з'єднані ребром, то Mij = 1, інакше Mij = 0. Для неорієнтованого графа матриця, очевидно, симетрична. Орієнтований граф задається антисиметричною матрицею. Якщо ребро виходить з вузла i і п...
