2015-10-22
583
1. 
.
2. 
.
3. 
4. 
делителей.
5. 24.
6. 
.
7. 211.
8. 
.
9. Ответ: n + 1.
10. 
.
11. 
.
12. Ни одного способа.
13. 
.
14. 
.
15. 
.
Материалы для семинаров
(Задача 6 – это ознакомительный материал!)
ОТВЕТЫ ДЛЯ САМОКОНТРОЛЯ
В задаче номер 4 решение аналогично решению для систем счисления (вспомните тему «Целые числа»!), а в задаче номер 3 надо воспользоваться правилом произведения, а в некоторых случаях – и правилом перехода к дополнению.
Графы (ДОПОЛНИТЕЛЬНЫЙ МАТЕРИАЛ)
Определение
Граф — это совокупность непустого множества вершин и множества пар его вершин.
Обычно связи между вершинами представляют как дуги, соединяющие эти вершины.
Граф называют ориентированным, если отмечено направление всех дуг (от одной вершины к другой).
Граф называют планарным, если можно изобразить его на плоскости.
Пример.
Квадрат с диагоналями является планарным графом (проверьте!). А пятиугольник с диагоналями не является планарным графом.
Деревья *
Дерево или древовидный граф – это связный граф без циклов.
|
|
|
Такое название дано потому, что любой древовидный граф можно нарисовать так, что он будет похож на дерево-растение. На таком изображении видны «корень» и «ветви». Листьями в дереве называются вершины, соединённые с графом только одной дугой.
В деревьях число вершин всегда на единицу меньше числа дуг. В самом деле, если мы будем отстригать от дерева листья вместе с дугами, на которых они висят, то разность между числом вершин и числом дуг меняться не будет. В конце стрижки останется одинокая вершина. Следовательно, эта разность равна единице.
В ориентированном дереве, в котором дуги идут от корня к ветвям, выходящие дуги связывают родительскую вершину с дочерними, а входящие – с родительскими.
Особую популярность имеют двоичные деревья, в которых у каждой вершины может быть не более двух детей – правая ветвь и левая. Информацию об этом дереве можно хранить, например, так: каждая вершина содержит ссылку на своих детей и своего родителя.
