Комбинаторика и теория графов 2014 — различия между версиями
AKramar (обсуждение | вклад) (→Домашние задания) |
AKramar (обсуждение | вклад) (→Домашние задания) |
||
| Строка 24: | Строка 24: | ||
===== Домашние задания ===== | ===== Домашние задания ===== | ||
* (11.09.14) Упражнения 1.10, 1.11, 1.12, 1.13, 1.14 и 1.17 | * (11.09.14) Упражнения 1.10, 1.11, 1.12, 1.13, 1.14 и 1.17 | ||
| + | * (25.09.14) Упражнения 2.6, 2.7, 2.8, 2.9, 3.4 и задачи на программирование, которые нужно отправлять Евгению Краско | ||
| + | Условие: Первая программа преобразует дерево в код Прюфера. Вторая — восстанавливает по коду дерево. | ||
| + | |||
| + | Формат описания дерева такой: в первой строке записано число вершин n; далее, каждая следующая строка содержит список смежности очередной вершины — последовательность номеров её соседей, разделённых пробелами. Вершины нумеруются с 0 до n-1. Например: | ||
| + | 4 | ||
| + | 1 | ||
| + | 0 2 | ||
| + | 1 3 | ||
| + | 2 | ||
| + | |||
| + | Формат описания кода Прюфера: в первой строке число вершин n, во второй — код, состоящий из n-2 позиций, разделённых пробелами. Для вышеприведённого дерева описание кода выглядит так: | ||
| + | 4 | ||
| + | 1 2 | ||
| + | |||
| + | Программы считывают данные из стандартного потока ввода, печатают результат в стандартный поток вывода (всё в оговорённом формате). Обе программы должны работать за линейное время. Программы должны быть взаимно-обратны в следующем смысле: при перенаправлении вывода одной на ввод другой, должно получаться исходное дерево/код. Проверять поступающие данные на правильность не надо: считайте, что вводимые данные корректны. | ||
Версия 21:40, 1 октября 2014
Содержание
Лекции
Омельченко Александр Владимирович
Четверг, 3 пара
Практика
Краско Евгений Сергеевич, Кноп Александр
Четверг, 4 пара
Комбинаторика
Домашние задания
- (4.09.14) Задачи
- (18.09.14) Упражнения 2.7, 2.9, 3.6, 3.7, 3.8, 3.9, 3.10
Теория графов
Домашние задания
- (11.09.14) Упражнения 1.10, 1.11, 1.12, 1.13, 1.14 и 1.17
- (25.09.14) Упражнения 2.6, 2.7, 2.8, 2.9, 3.4 и задачи на программирование, которые нужно отправлять Евгению Краско
Условие: Первая программа преобразует дерево в код Прюфера. Вторая — восстанавливает по коду дерево.
Формат описания дерева такой: в первой строке записано число вершин n; далее, каждая следующая строка содержит список смежности очередной вершины — последовательность номеров её соседей, разделённых пробелами. Вершины нумеруются с 0 до n-1. Например: 4 1 0 2 1 3 2
Формат описания кода Прюфера: в первой строке число вершин n, во второй — код, состоящий из n-2 позиций, разделённых пробелами. Для вышеприведённого дерева описание кода выглядит так: 4 1 2
Программы считывают данные из стандартного потока ввода, печатают результат в стандартный поток вывода (всё в оговорённом формате). Обе программы должны работать за линейное время. Программы должны быть взаимно-обратны в следующем смысле: при перенаправлении вывода одной на ввод другой, должно получаться исходное дерево/код. Проверять поступающие данные на правильность не надо: считайте, что вводимые данные корректны.
