Идеальные квадраты - кто-нибудь может объяснить следующую математику?

#c #math #square-root #perfect-square

#c #математика #квадратный корень #идеальный квадрат

Вопрос:

Постановка задачи:

 Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4   4   4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4   9.

Используя следующие знания о квадратах (приведенные ниже), мы можем реализовать следующее решение.

Натуральное число равно…

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

… сумма двух квадратов тогда и только тогда, когда каждый простой множитель, равный 3 по модулю 4, имеет четную степень при разложении числа на простые множители.

… сумма трех квадратов тогда и только тогда, когда она не имеет вида 4a(8b 7) с целыми числами a и b .

… сумма четырех квадратов. Точка. Нет условия. Вам никогда не нужно больше четырех.

 int numSquares(int n) {
    while (n % 4 == 0)
        n /= 4;
    if (n % 8 == 7)
        return 4;
    for (int a=0; a*a<=n;   a) {
        int b = sqrt(n - a*a);
        if (a*a   b*b == n)
            return 1   !!a;
    }
    return 3;
}

Вопрос:

Может кто-нибудь помочь мне понять, чего именно мы пытаемся достичь, следуя циклу for? Я здесь немного потерялся.

 for (int a=0; a*a<=n;   a) {
    int b = sqrt(n - a*a);
    if (a*a   b*b == n)
        return 1   !!a;
}

1. return 1 !!a; то же if(a == 0) return 1; else return 2; самое, что и . Тогда у вас есть 4 return значения для 4 возможных случаев.

2. Спасибо, но чего мы достигаем, когда делаем b = sqrt(n - a*a) ? Я специально не понимаю, почему n - a*a ?

3. Это проверяет, является ли n сумма двух квадратов, что происходит n - a * a , если для некоторых она сама является идеальным квадратом a .

Ответ №1:

Цикл пытается найти два квадрата, сумма n которых равна .

Вместо того, чтобы пробовать каждую комбинацию чисел, чтобы увидеть, можем ли мы возвести их в квадрат, и они складываются в n , мы просто перебираем возможности для одного из чисел — это a . Мы возводим это в квадрат a*a и вычитаем это из n . Затем мы получаем целую часть квадратного корня из этой разницы, и это b . Если a ² b ² складывается n , это пара квадратов, которые мы ищем.

Нам нужно вычислить сумму квадратов в случае n - a*a , если это не идеальный квадрат. В этом случае его квадратный корень будет содержать дробь, которая будет потеряна, когда мы преобразуем его в целое число. Другими словами, тестирование a*a b*b == n позволяет нам определить, был ли квадратный корень целым числом.

1. Спасибо! Я нарисовал это на белой доске, но вместо того, чтобы использовать древовидный / графический подход, я использовал подход рекурсивного вызова для создания и записи всех возможных вызовов n=13 , и в итоге я усложнил себе жизнь. Позже я нарисовал из этого дерево, для n=7 меня это имело больше смысла, вместе с вашим объяснением, конечно! ценю помощь!