Как определить, является ли число суммой квадратов некоторых чисел?

У меня алгоритмический вопрос: Как определить, равно ли число сумме квадратов некоторых различных чисел? Например : 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;
    }
}

Я думаю, что ОП имел в виду 50 = 4 * 4 + 5 * 5 + 3 * 3.

rakarnik 31.03.2022 00:28

Ха-ха! Вы правы, похоже, что кто-то отредактировал сейчас. ?

Fogmeister 31.03.2022 00:29

Покажите свое решение для 2 чисел, и кто-нибудь подскажет, как его обобщить.

500 - Internal Server Error 31.03.2022 00:30

Извините, я думаю, что это была проблема Markdown...

Mohammadreza Razavian 31.03.2022 00:30

Разве это не верно для всех положительных целых чисел, поскольку вы можете использовать 1² + 1² + 1² + ... + 1².

Raymond Chen 31.03.2022 01:32

@RaymondChen ОП упомянул в вопросе «разные числа», поэтому я думаю, что 1 ^ 2 + 1 ^ 2 +... + 1 ^ 2 не будет правильным ответом.

Breakpoint 31.03.2022 06:24

@Breakpoint ах, я пропустил требование, чтобы термины были разными. Оказывается, ответ по-прежнему прост: все положительные целые числа выражаются в виде суммы различных квадратов, за исключением конечного списка oeis.org/A001422, поэтому вам просто нужно проверить, есть ли число в списке.

Raymond Chen 31.03.2022 06:44

@RaymondChen, это очень впечатляющее решение O (1)!

Breakpoint 31.03.2022 06:50
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
8
158
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Эта проблема является вариантом Проблема суммы подмножества.

Здесь вам нужно будет создать свой собственный набор (что объясняется ниже), и ваше число является целевой суммой для задачи.

Чтобы создать набор, сформируйте массив чисел [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 порядка

большое спасибо, а как определить количество чисел в квадрате?

Mohammadreza Razavian 01.04.2022 10:37

@ Вы можете просто взять все целые числа от 1 до квадратного корня из целевого числа и возвести их в квадрат, это то, что я сделал в ответе

Tomer Geva 01.04.2022 10:46

Как насчет количества состояний, которое мы можем записать в виде суммы нескольких разных квадратов? Например, для 25: мы можем записать это как 5 ^ 2 + 0 и 3 ^ 2 + 4 ^ 2.

Mohammadreza Razavian 01.04.2022 11:32

В этом случае вы просто возвращаетесь counts[number]

Tomer Geva 01.04.2022 11:34

Другие вопросы по теме