Начало
Учебные материалы
Метод преобразования
Идея метода преобразования Предварительная сортировка Метод исключения Гаусса Пирамиды и пирамидальная сортировка Схема Горнера Приведение задачи
Приведение задачи
Перед физиком и математиком ставят задачу вскипятить воду.
Оба наливают воду в чайник, зажигают плиту, ставят чайник на огонь и ждут, пока закипит.
У нас уже есть чайник, наполненный водой, и зажженная плита.
Цель та же: вскипятить воду.
Физик ставит чайник на огонь и ждет, пока вода закипит.
Математик выключает огонь, выливает воду из чайника и говорит: теперь задача сводится к предыдущей.
Если вам надо решить задачу, ее можно привести к другой задаче,
решение которой вам известно.
--
*Наименьшее общее кратное* двух
натуральных чисел `m` и `n`, обозначаемое как `"lcm"(m, n)`, определяется как
наименьшее натуральное число, делящееся и на `m`, и на `n`.
`"lcm"(m, n)` можно вычислить как произведение всех общих простых
множителей `m` и `n`, умноженное на произведение простых множителей `m`, не являющихся
множителями `n`, и на произведение простых множителей `n`, не являющихся
множителями `m`.
Нетрудно увидеть, что произведение `"lcm"(m, n)` и `"gcd"(m, n)` включает по одному разу
каждый из простых множителей `m` и `n`, следовательно, это произведение просто
равно произведению `m` и `n`. Это наблюдение приводит к формуле
`"lcm"(m, n)=(m*n)/("gcd"(m, n))`
где `"gcd"(m, n)` можно вычислить при помощи алгоритма Евклида.
--
Рассмотрим задачу подсчета путей между двумя вершинами графа.
Методом математической индукции нетрудно доказать,
что количество различных путей длиной `k> 0` от `i`-ой к `j`-ой вершине графа
равно `(i,j)`-омy элементу `A^k`, где `A` —
матрица смежности графа.
Таким образом, задача подсчета путей в графе может быть решена при помощи
алгоритма для вычисления соответствующей степени его матрицы смежности.
Алгоритмы быстрого возведения чисел в степень применимы и для возведения в степень матриц.
--
Предположим, требуется найти минимум
некоторой функции `f(x)`, и у нас есть алгоритм, позволяющий найти
максимум функции. Можно воспользоваться следующей формулой:
`min f(x) = - max [-f (x)]`.
Поиск точек экстремума функции тоже фактически основан
на приведении задачи, так как сводится к нахождению производной функции `f'(x)` и
решение уравнения `f'(x)=0`.
--
Многие задачи можно решить путем
приведения к одной из стандартных задач о графах.
Это верно, в частности, для
множества головоломок и игр. Вершины графа
обычно представляют возможные состояния рассматриваемой задачи, в то время как
ребра представляют разрешенные переходы между состояниями. Одна из вершин
графа представляет начальное состояние, а некоторая другая — конечное, целевое
состояние задачи (таких конечных вершин может быть несколько).
Такой граф называется *графом пространства состояний*. Таким
образом, описанное преобразование приводит задачу к вопросу о пути из начальной вершины в конечную.
---
##### Задания для практики
1. Даны таблицы десятичных логарифмов и антилогарифмов. Как выполнить умножение двух 3-разрядных чисел без использования операции умножения?
2. На координатной плоскости дано `n >= 3` точек. Разработайте алгоритм для проверки того факта, что все точки лежат внутри треугольника, вершинами которого являются три точки из данного множества.
3. Задача раскрашивания графа обычно формулируется как задача раскраски вершин: распределить минимальное количество цветов по вершинам данного графа так, чтобы никакие две смежные вершины не были окрашены в одинаковый цвет. Рассмотрим задачу раскрашивания ребер: распределить минимальное количество цветов по ребрам данного графа так, чтобы никакие два ребра, имеющие общую точку, не были окрашены в одинаковый цвет. Поясните, как задача раскрашивания ребер может быть приведена к задаче раскрашивания вершин.
