Поиск всех последовательностей чисел от 1 до n, где сумма соседних чисел является квадратом10.09.2024 17:30

ремарка:

В данной статье представлено решение задачи по нахождению всех возможных цепочек чисел в матрице, соответствующих определенным условиям. Однако следует отметить, что это решение не претендует на звание оптимального. Подход, описанный здесь, может иметь свои ограничения и не всегда быть самым эффективным для всех возможных сценариев. Автор не утверждает, что предложенный метод является наилучшим или универсальным способом решения подобных задач. Важно понимать, что существует множество альтернативных подходов, и оптимальное решение может варьироваться в зависимости от конкретных требований и условий задачи.

Описание задачи:

Необходимо найти все возможные последовательности чисел от 1 до n (задает пользователь), удовлетворяющие следующему условию: сумма двух соседних чисел в последовательности должна быть квадратом целого числа.

Формальные требования:

  1. Входные данные:

  2. Выходные данные:

    • Список всех возможных последовательностей чисел от 1 до n, где сумма двух соседних чисел в последовательности является квадратом целого числа (далее квадратное число или анологично).

  3. Ограничения:

    • Последовательности должны включать только числа от 1 до n без повторений.

    • последовательность должна состоять из всех чисел от 1 до n

Оптимизация поиска с помощью матрицы связей

наивный подход предполагает перебор всех возможных последовательностей, однако, этот метод предпологает перебор n!, последовательностей, что очень много даже при относительно малых n и соответственно не быстро и может памяти не хватить.

Чтобы улучшить производительность и сократить количество проверяемых вариантов, используется матрицу связей. Эта матрица помогает существенно снизить количество комбинаций, которые необходимо проверять, за счет предварительного анализа допустимых переходов между числами.

Построение матрицы связей

  1. Определение квадратных чисел: Сначала необходимо определить все возможные квадратные числа, которые могут быть результатом суммы двух чисел от 1 до n. Это делается для того, чтобы упростить проверку условий при построении матрицы связей.

  2. Создание матрицы связей: Мы создаем матрицу n×n, где элемент в позиции (i,j) равен true, если сумма чисел i и j является квадратом целого числа. В противном случае, элемент равен false. Это позволяет нам легко и быстро проверять, допустим ли переход от числа i к числу j в последовательности.

  3. Использование матрицы для генерации последовательностей: Используя построенную матрицу связей, мы можем находить все возможные последовательности. Начав с любого числа, мы проверяем матрицу, чтобы определить, к каким числам можно перейти на основе условия, что сумма должна быть квадратом. Это значительно сокращает количество вариантов и упрощает процесс поиска.

реализации алгоритма на 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

n = 17

n = 17

P.S. код можно глянуть тут

© Habrahabr.ru