У меня алгоритмический вопрос: Как определить, равно ли число сумме квадратов некоторых различных чисел? Например : 50 = 4*4 + 5*5 + 3*3
И, если это так, как я могу найти количество состояний, которые мы можем записать в виде суммы нескольких различных квадратов?
25 = 5^2 + 0 или 3^2 + 4^2 и имеет 2 состояния.
Я в порядке с двумя числами, и я знаю, что мы можем решить это с помощью рекурсии.
Вот мой код в java для 2 чисел:
import java.util.Scanner;
public class SemiCharismatic {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
input.close();
if (isSquare(number) == true) {
System.out.print("YES");
System.exit(0);
} else {
for (int i = 1; i < number; i++) {
int j = number - i;
if (isSquare(i) == true && isSquare(j) == true) {
System.out.print("YES");
System.exit(0);
}
}
System.out.print("NO");
}
}
static boolean isSquare(int number) {
boolean result = false;
if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) {
result = true;
}
return result;
}
}
Ха-ха! Вы правы, похоже, что кто-то отредактировал сейчас. ?
Покажите свое решение для 2 чисел, и кто-нибудь подскажет, как его обобщить.
Извините, я думаю, что это была проблема Markdown...
Разве это не верно для всех положительных целых чисел, поскольку вы можете использовать 1² + 1² + 1² + ... + 1².
@RaymondChen ОП упомянул в вопросе «разные числа», поэтому я думаю, что 1 ^ 2 + 1 ^ 2 +... + 1 ^ 2 не будет правильным ответом.
@Breakpoint ах, я пропустил требование, чтобы термины были разными. Оказывается, ответ по-прежнему прост: все положительные целые числа выражаются в виде суммы различных квадратов, за исключением конечного списка oeis.org/A001422, поэтому вам просто нужно проверить, есть ли число в списке.
@RaymondChen, это очень впечатляющее решение O (1)!
Эта проблема является вариантом Проблема суммы подмножества.
Здесь вам нужно будет создать свой собственный набор (что объясняется ниже), и ваше число является целевой суммой для задачи.
Чтобы создать набор, сформируйте массив чисел [square of numbers from {1 to sqrt(n)}]
Итак, ваш массив будет выглядеть так: [1,4,9... sqrt(n)^2]
Чтобы объяснить, почему sqrt(n): Квадрат любого числа, большего, чем sqrt(n), также будет больше, чем n. Следовательно, добавление к нему большего количества не приведет к решению.
Затем примените алгоритм подмножества, как описано здесь.
isSubsetSum(set, n, sum)
= isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0
Это можно рассматривать как проблему обмена монет (см. здесь).
Один из методов решения проблемы обмена монет является рекурсивным, как предложил другой ответ:
def is_sum_squared_rec(number, candidates=None, idx=None):
if candidates is None:
candidates = np.arange(1, int(np.floor(np.sqrt(number)))+1) ** 2
idx = len(candidates) - 1
if (number > 0 and idx == -1) or number < 0:
return False
if number == 0:
return True
return is_sum_squared_rec(number, candidates, idx-1) or is_sum_squared_rec(number-candidates[idx], candidates, idx-1)
А вот другим нерекурсивным способом реализации задачи размена монет в этом случае будет следующий:
def is_sum_squared(number):
counts = [1] + [0] * number
candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
for candidate in candidates:
for jj in range(number, candidate-1, -1):
counts[jj] += counts[jj - candidate]
return counts[number] > 0
Этот метод позволяет избежать избыточных вычислений и должен быть быстрее, чем рекурсивный метод.
Нерекурсивный метод можно улучшить, поскольку нам не нужен весь подсчет, если только его можно разбить на сумму кандидатов. поэтому мы можем ввести условие ранней остановки:
def is_sum_squared_early_stop(number):
counts = [1] + [0] * number
candidates = np.arange(1, int(np.floor(np.sqrt(number))) + 1) ** 2
for candidate in candidates:
for jj in range(number, candidate-1, -1):
counts[jj] += counts[jj - candidate]
if counts[number] > 0:
return True
return counts[number] > 0
Время выполнения нерекурсивного алгоритма составляет O (n * sqrt (n)) и требования к скейпу — O (n).
для number = 400
время получилось следующим:
%timeit is_sum_squared_rec(400)
1.88 ms ± 177 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared(400)
1.05 ms ± 76.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit is_sum_squared_early_stop(400)
796 µs ± 127 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Улучшение почти в 3 раза. При проверке с помощью number=3000
получаем:
%timeit is_sum_squared_rec(3000)
1.81 s ± 152 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit is_sum_squared(3000)
24.5 ms ± 581 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit is_sum_squared_early_stop(3000)
14.3 ms ± 556 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
А у нас разница более чем на 2 порядка
большое спасибо, а как определить количество чисел в квадрате?
@ Вы можете просто взять все целые числа от 1 до квадратного корня из целевого числа и возвести их в квадрат, это то, что я сделал в ответе
Как насчет количества состояний, которое мы можем записать в виде суммы нескольких разных квадратов? Например, для 25: мы можем записать это как 5 ^ 2 + 0 и 3 ^ 2 + 4 ^ 2.
В этом случае вы просто возвращаетесь counts[number]
Я думаю, что ОП имел в виду 50 = 4 * 4 + 5 * 5 + 3 * 3.