Подразделы

Другие разделы

Дата и время

09/04/2025 23:56:47

Авторизация

Метод преобразования

Идея метода преобразования Предварительная сортировка Метод исключения Гаусса Пирамиды и пирамидальная сортировка Схема Горнера Приведение задачи

Приведение задачи

Пусть у нас есть пустой чайник, спички, газовая плита. Перед физиком и математиком ставят задачу вскипятить воду. Оба наливают воду в чайник, зажигают плиту, ставят чайник на огонь и ждут, пока закипит.

У нас уже есть чайник, наполненный водой, и зажженная плита. Цель та же: вскипятить воду. Физик ставит чайник на огонь и ждет, пока вода закипит. Математик выключает огонь, выливает воду из чайника и говорит: теперь задача сводится к предыдущей.

Если вам надо решить задачу, ее можно привести к другой задаче, решение которой вам известно.

Наименьшее общее кратное двух натуральных чисел $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$ .

Многие задачи можно решить путем приведения к одной из стандартных задач о графах.

Это верно, в частности, для множества головоломок и игр. Вершины графа обычно представляют возможные состояния рассматриваемой задачи, в то время как ребра представляют разрешенные переходы между состояниями. Одна из вершин графа представляет начальное состояние, а некоторая другая — конечное, целевое состояние задачи (таких конечных вершин может быть несколько). Такой граф называется графом пространства состояний. Таким образом, описанное преобразование приводит задачу к вопросу о пути из начальной вершины в конечную.

Задания для практики

Даны таблицы десятичных логарифмов и антилогарифмов. Как выполнить умножение двух 3-разрядных чисел без использования операции умножения?
На координатной плоскости дано $n >= 3$ точек. Разработайте алгоритм для проверки того факта, что все точки лежат внутри треугольника, вершинами которого являются три точки из данного множества.
Задача раскрашивания графа обычно формулируется как задача раскраски вершин: распределить минимальное количество цветов по вершинам данного графа так, чтобы никакие две смежные вершины не были окрашены в одинаковый цвет. Рассмотрим задачу раскрашивания ребер: распределить минимальное количество цветов по ребрам данного графа так, чтобы никакие два ребра, имеющие общую точку, не были окрашены в одинаковый цвет. Поясните, как задача раскрашивания ребер может быть приведена к задаче раскрашивания вершин.