ремарка:
В данной статье представлено решение задачи по нахождению всех возможных цепочек чисел в матрице, соответствующих определенным условиям. Однако следует отметить, что это решение не претендует на звание оптимального. Подход, описанный здесь, может иметь свои ограничения и не всегда быть самым эффективным для всех возможных сценариев. Автор не утверждает, что предложенный метод является наилучшим или универсальным способом решения подобных задач. Важно понимать, что существует множество альтернативных подходов, и оптимальное решение может варьироваться в зависимости от конкретных требований и условий задачи.
Описание задачи:
Необходимо найти все возможные последовательности чисел от 1 до n
(задает пользователь), удовлетворяющие следующему условию: сумма двух соседних чисел в последовательности должна быть квадратом целого числа.
Формальные требования:
-
Входные данные:
-
Натуральное число
n
, определяющее диапазон чисел от 1 доn
(где n≥1n \geq 1n≥1).
-
-
Выходные данные:
-
Список всех возможных последовательностей чисел от 1 до
n
, где сумма двух соседних чисел в последовательности является квадратом целого числа (далее квадратное число или анологично).
-
-
Ограничения:
-
Последовательности должны включать только числа от 1 до
n
без повторений. -
последовательность должна состоять из всех чисел от 1 до
n
-
Оптимизация поиска с помощью матрицы связей
наивный подход предполагает перебор всех возможных последовательностей, однако, этот метод предпологает перебор n!
, последовательностей, что очень много даже при относительно малых n и соответственно не быстро и может памяти не хватить.
Чтобы улучшить производительность и сократить количество проверяемых вариантов, используется матрицу связей. Эта матрица помогает существенно снизить количество комбинаций, которые необходимо проверять, за счет предварительного анализа допустимых переходов между числами.
Построение матрицы связей
-
Определение квадратных чисел: Сначала необходимо определить все возможные квадратные числа, которые могут быть результатом суммы двух чисел от 1 до
n
. Это делается для того, чтобы упростить проверку условий при построении матрицы связей. -
Создание матрицы связей: Мы создаем матрицу
n×n
, где элемент в позиции(i,j)
равенtrue
, если сумма чиселi
иj
является квадратом целого числа. В противном случае, элемент равенfalse
. Это позволяет нам легко и быстро проверять, допустим ли переход от числаi
к числуj
в последовательности. -
Использование матрицы для генерации последовательностей: Используя построенную матрицу связей, мы можем находить все возможные последовательности. Начав с любого числа, мы проверяем матрицу, чтобы определить, к каким числам можно перейти на основе условия, что сумма должна быть квадратом. Это значительно сокращает количество вариантов и упрощает процесс поиска.
реализации алгоритма на Scala
для начала нужно определить все возможные комбинации из двух чисел которые могут дать квадратное число
, стоит заметить что для произвольного натурально n, квадратные числа могут быть больше самого n (так для n = 15
есть пары дающие 25
в сумме, например 12 и 15
) и таким образом надо смотреть все возможные пары для чисел меньших или равных 2 * n - 1
(поскольку это максимальная сумма которая может быть
//метод для поиска всех квадратных числе возможны, которые можно соствит из чисел от 1 до n def squareNumbersLessThan(n: Int): Seq[Int] = { //начинаю с 2, поскольку 1 в этой задаче не интересует //ищу до корня из n поскольку оно и покажыт максимальный корень округленый в лево //и соответственно можно построить все числа квадратные до него (2 to math.sqrt(n).toInt).map(x => x * x) } /** * Находит все уникальные пары чисел от 1 до n, сумма которых равна n, * при этом исключая пары, содержащие нули. * * Метод генерирует последовательность пар чисел (x, y) таких, что: * - x и y — числа от 1 до n * - сумма x и y равна n * - x не равно y * - x и y не равны нулю (хотя для чисел от 1 до n это условие избыточно) * */ def findUniquePairsFunctional(n: Int): Seq[(Int, Int)] = { (1 to n).map(x => (x, n - x)).filter { case (x, y) => x != y }.filter { case (x, y) => y != 0 && x != 0} } val n: Int = readInt()//читаем n введеное пользователем val squares: Seq[Int] = squareNumbersLessThan(n * 2 -1) //находим все возможные квадраты val allPairs = squares.flatMap(findUniquePairsFunctional) // находи все пары которые интересуют.
создадим матрицу и методы для работы с ней
/** * Создает квадратную матрицу размером n x n, где все элементы инициализированы значением false. * * @param n Размер матрицы (число строк и столбцов). * @return Квадратная матрица размером n x n, заполненная значениями false. */ def createMatrix(n: Int): Array[Array[Boolean]] = { Array.tabulate(n, n)((_, _) => false) } /** * Выводит матрицу в виде строки, где элементы 1 и 0 отображаются в виде "1" и "0" соответственно. * Значения в строках разделены символом " | ". * * @param matrix Квадратная матрица значений типа Boolean. */ def printMatrix(matrix: Array[Array[Boolean]]): Unit = { matrix.foreach(row => println(row.map(if (_) "1" else "0").mkString(" | "))) } /** * Обновляет значение в указанной ячейке матрицы и возвращает новую матрицу. * Создается новая копия матрицы, чтобы избежать изменения исходной матрицы. * * @param matrix Исходная матрица значений типа Boolean. * @param row Индекс строки, в которой нужно обновить значение. * @param col Индекс столбца, в котором нужно обновить значение. * @param value Новое значение для указанной ячейки. * @return Новая матрица с обновленным значением. */ def updateMatrixValue(matrix: Array[Array[Boolean]], row: Int, col: Int, value: Boolean): Array[Array[Boolean]] = { val updatedMatrix = matrix.map(_.clone()) if (row >= 0 && row < updatedMatrix.length && col >= 0 && col < updatedMatrix(row).length) { updatedMatrix(row)(col) = value } updatedMatrix } /** * Находит все ячейки в указанной строке матрицы, где значение равно true. * Возвращает список пар координат (индексов) ячеек с истинным значением. * * @param matrix Квадратная матрица значений типа Boolean. * @param rowIndex Индекс строки, в которой нужно найти значения true. * @return Последовательность пар координат (индексов) ячеек, где значение равно true. */ def findTrueInRow(matrix: Array[Array[Boolean]], rowIndex: Int): Seq[(Int, Int)] = { if (rowIndex >= 0 && rowIndex < matrix.length) { matrix(rowIndex).zipWithIndex.collect { case (value, colIndex) if value => (rowIndex, colIndex) } } else { println(s"Row index $rowIndex is out of bounds!") Seq.empty } }
ну и финальный метод который и найдет все цепочки
/** * Находит все возможные цепочки чисел в матрице, где каждое число в цепочке соединяется с другим числом, * если их сумма является квадратом. Цепочки формируются из всех чисел от 1 до n, удовлетворяющих условиям. * * @param matrix Квадратная матрица значений типа Boolean, где значение true обозначает допустимое соединение * между числами, и false обозначает отсутствие соединения. * @return Список всех цепочек чисел, которые можно построить, начиная с любого числа и соблюдая условия соединения. */ def findAllChains(matrix: Array[Array[Boolean]]): List[Seq[Int]] = { val n = matrix.length /** * Рекурсивная функция для поиска всех цепочек, начиная с текущего числа. * * @param cursor Текущее число, от которого начинается поиск. * @param acc Накопленная цепочка чисел, которая обновляется по мере рекурсивного поиска. * @param nums Список оставшихся чисел, которые могут быть добавлены в цепочку. * @return Список всех цепочек, начинающихся с текущего числа. */ def loop(cursor: Int, acc: Seq[Int], nums: Seq[Int]): List[Seq[Int]] = { // Находит все числа в строке `cursor`, которые могут быть добавлены в цепочку val pairs = findTrueInRow(matrix, cursor).map(_._2).filter(num => nums.contains(num)).toList // Если есть допустимые пары для продолжения цепочки if (pairs.nonEmpty) { // Рекурсивно строит цепочки, добавляя текущее число и продолжая поиск pairs.flatMap { num => loop(num, acc ++ Seq(num), nums.filter(_ != num)) } } else { // Если нет допустимых пар, возвращает текущую цепочку как один из результатов List(acc) } } // Создает список всех чисел от 1 до n-1, для использования в качестве начальных точек цепочек val fullNums = (1 until n).toList // Запускает рекурсивный поиск цепочек для каждого числа, начиная с полного списка fullNums.flatMap(num => loop(num, Seq(num), fullNums.filter(_ != num))) }
ну и остаеться тлько вызвать метод и отсеять неподходящии по размеру цепочки
lazy val emptyMatrixPairs = createMatrix(n + 1) // создаем пустую матрицу //заполняем матрицу lazy val fullMatrixPairs = allPairs.foldLeft(emptyMatrixPairs) { case (agg, (x, y)) => updateMatrixValue(agg, x, y, true) } //выведем чтоб посмотреть что там printMatrix(fullMatrixPairs) //получаем все квадратные цепочки и отсеиваем те что по длине меньше n val res = findAllChains(fullMatrixPairs).filter(_.size == n) println(res) // выводим println(res.size) // выводим
пример для n = 17
P.S. код можно глянуть тут
ссылка на оригинал статьи https://habr.com/ru/articles/842246/
Добавить комментарий