На этом шаге мы приведем задачи для самостоятельного решения.

Определения, необходимые для решения задач.

(1) Совершенным числом называется натуральное число, равное сумме всех своих делителей, не считая его самого. Например, 6=1+2+3 - совершенное число.
(2) Дружественными числами называется пара чисел, обладающих таким свойством: сумма собственных делителей первого из них равна второму числу, а сумма собственных делителей второго числа равна первому числу.
Например, сумма делителей числа 220 равна
```
   1+2+4+5+10+11+20+22+44+55+110=284,
```
а сумма делителей числа 284 равна 220.
(3) Палиндромическим числом называется натуральное число, "читаемое" одинаково с обеих сторон. Например, 171 - палиндромическое число.
(4) Средней плотностью графа называется частное от деления количества его рёбер на количество вершин.

Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.

1. Обход графов в глубину

1^*. Используя обход в глубину, определите количество вершин в связном неориентированном графе.

2^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в глубину, сколько из них являются чётными.

3^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в глубину, сколько из них являются трёхзначными.

4^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в глубину, сколько из них являются палиндромическими.

5^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в глубину, сколько из них являются простыми.

6^*. Перенумеруйте вершины связного неориентированного графа в порядке обхода в глубину.

7^*. (По [1, с.165]) Перенумеруйте вершины связного неориентированного графа в порядке обхода в глубину и вычислите среднюю плотность графа. Можно ли оба эти действия выполнить за один обход графа?

8^*. Напишите функцию, определяющую в связном неориентированном графе длину пути из одной вершины в другую с помощью обхода в глубину.

9. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в глубину, сколько из них являются совершенными.

10. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в глубину, сколько из них являются дружественными.

11. Используйте обход связного неориентированного графа в глубину для определения всех вершин, находящихся на фиксированном расстоянии D от данной вершины.

2. Обход графов в ширину

0^*. Дайте название методу, отличающемуся от поиска в ширину на связном неориентированном графе только тем, что вновь достигнутая вершина помещается не в очередь, а в стек.

1^*. Используя обход в ширину, определите количество вершин в связном неориентированном графе.

2^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в ширину, сколько из них являются чётными.

3^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в ширину, сколько из них являются трёхзначными.

4^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в ширину, сколько из них являются палиндромическими.

5^*. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в ширину, сколько из них являются простыми.

6^*. Перенумеруйте вершины связного неориентированного графа в порядке обхода в ширину.

7^*. (По [1, с.165]) Перенумеруйте вершины неориентированного графа в порядке обхода в ширину и вычислите среднюю плотность графа. Можно ли оба эти действия выполнить за один обход графа?

8^*. Напишите функцию, определяющую в связном неориентированном графе длину пути из одной вершины в другую с помощью обхода в ширину.

9. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в ширину, сколько из них являются совершенными.

10. В вершинах связного неориентированного графа "хранятся" положительные целые числа. Подсчитайте с помощью обхода графа в ширину, сколько из них являются дружественными.

11. Используйте обход связного неориентированного графа в ширину для определения всех вершин, находящихся на фиксированном расстоянии D от данной вершины.

3. Вычисление компонентов связности графа

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

2. Реализуйте алгоритм проверки связности графа, изложенный в монографии [2, с.198-205].

4. Построение остовного дерева связного графа

1^*. Реализуйте алгоритм превращения заданного графа в дерево.

⁽¹⁾Дмитриева М.В., Кубенский А.А. Турбо Паскаль и Турбо Си: построение и обработка структур данных. СПб.: Изд-во СПбГУ, 1996. - 192 с.
⁽²⁾Пападимитриу Х., Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.

Со следующего шага мы начнем рассматривать классы и их экземпляры.

Предыдущий шаг Содержание Следующий шаг