Не получается дописать программу

Question

Для положительного целого числа n найдите наименьшее количество полных квадратных чисел (например, 1, 4, 9, 16, ...), сумма которых равна n. Например, если n = 12, верните 3, потому что 12 = 4 + 4 + 4; если n = 13, вернуть 2, потому что 13 = 4 + 9

Я решил сделать так.. В массив squares записываю все квадратные числа,которые <= n.В переменную compare записывал максимальное квадратное число, после сравнивал с n: если оно меньше, то я к compare заново прибавляю то же квадратное число; если больше, то отнимал это число и прибавлял квадратное, стоящее позади максимального. И так, пока n не будет == compare.

В коде у меня находится вариант, который начинается от последнего элемента из массива с квадратными числами. А мне надо найти всевозможные варианты, что записал бы в массив arrSteps. Я пытался засунуть это в еще один цикл, но ничего не вышло. Хелп <3

findMinSquares(parseInt(prompt('number')))

function findMinSquares(n) {
  if (n == 0)
    return +console.log(0)
  if (n == 1)
    return +console.log(1)

  // в массиве squares хранятся все квадратные числа (до n)
  let squares = []
  squares = squaresNumber(n)
  console.log(squares)

  let arrSteps = []
  let compare = 0
  let steps = 0

  let s = squares.length - 1
  for (; s >= 0;) {
    compare += squares[s]
    if (compare == n) {
      ++steps
      arrSteps.push(steps)
      console.log(arrSteps)

    } else if (compare > n) {
      compare -= squares[s]
      s--
    } else if (compare < n) {
      ++steps
    }
  }

}

function squaresNumber(n) {
  let i = 1
  let arr = []
  while (i * i <= n) {
    arr.push(i * i)
    i++
  }
  return arr
}

Answer 1

Искать разложение не нужно. Теорема Лагранжа о сумме четырёх квадратов утверждает что числа вида 4^k(8m + 7) представимы как сумма четырех квадратов. Все остальные представимы как сумма трех или менее квадратов (теорема Лежандра о трёх квадратах).

Решение ниже пытается проверить что число представимо одним квадратом, затем четырьмя, затем двумя. Если ни один вариант не подошел, то ответ - три квадрата. Самая сложная проверка для пары квадратов - там перебор. Число вариантов в переборе не более sqrt(n).

const isSquare = n => {
    const sq = Math.floor(Math.sqrt(n));
    return n === sq * sq;
};

// see https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem
const nSquares = n => {
    if (isSquare(n)) {
        return 1;
    }

    // n = 4^k(8m + 7) ?
    let m = n;
    while (m % 4 == 0) {
        m /= 4;
    }
    if (m % 8 == 7) {
        return 4;
    }

    // is n sum of two squares?
    for (let k = 1; k * k <= n / 2; ++k) {
        if (isSquare(n - k * k)) {
            return 2;
        }
    }

    return 3;
};

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

rl.on('line', line => console.log(nSquares(parseInt(line))));

$ echo 310 | node represent-n-as-sum-of-squares.js
3
$ echo 496 | node represent-n-as-sum-of-squares.js
4
$ echo 1000000001 | node represent-n-as-sum-of-squares.js 
3

P.S. В статье из Кванта Суммы квадратов и целые гауссовы цисла тема разложения рассмотрена очень подробно. Там есть условие того что число представимо в виде пары квадратов. Условие опирается на разложение числа на простые. Самая тяжелая часть решения выше (поиск пар) может быть заменена на этот критерий. Вопрос что быстрее - искать пары перебором или разложить число на простые.

БЛОГ НА HUSL

Не получается дописать программу

Ответы (1 шт):