Учитывая число N, может ли N выражаться как сумма двух или более последовательных совершенных квадратов?

Question

На недавнем соревновании по компьютерному программированию, на котором я был, возникла проблема, когда вам нужно определить, является ли число N для 1 < = N < = 1000, является палиндромным квадратом. Палиндромный квадрат - это число, которое можно читать одинаково вперед и назад и может быть выражено как сумма двух или более последовательных совершенных квадратов. Например, 595 является палиндром и может быть выражен как 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.

Я понимаю, как определить, является ли число палиндром, но у меня возникают проблемы с попыткой выяснить, может ли он быть выражен как сумма двух или более последовательных квадратов.

Вот алгоритм, который я попробовал:

public static boolean isSumOfSquares(int num) { 
 
     int sum = 0; 
 
     int lowerBound = 1; 
 

 
     //largest square root that is less than num 
 
     int upperBound = (int)Math.floor(Math.sqrt(num)); 
 
      
 
     while(lowerBound != upperBound) { 
 
      for(int x=lowerBound; x<upperBound; x++) { 
 
       sum += x*x; 
 
      } 
 
       
 
      if(sum != num) { 
 
       lowerBound++; 
 
      } 
 
      else { 
 
       return true; 
 
      } 
 
      sum=0; 
 
               
 
     } 
 
      
 
     return false; 
 
    }

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

Answer 1

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

1. Начать с нижней границей и верхней границей 1. Текущая сумма квадратов 1.

   public static boolean isSumOfSquares(int num) { 
       int sum = 1; 
       int lowerBound = 1; 
       int upperBound = 1; 
   

2. Максимально возможная верхняя граница это максимальное число, квадрат которого меньше или равно числу для тестирования.

   int max = (int) Math.floor(Math.sqrt(num)); 
   

3. В то время как цикл. Если сумма квадратов слишком мала, добавьте следующий квадрат, увеличивая upperBound. Если сумма квадратов слишком высока, то вычтите первый квадрат, увеличивая lowerBound. Выйдите, если номер найден. Если он не может быть выражен в виде суммы квадратов последовательных номеров, то в конечном итоге upperBound будет превышать max, и возвращается false.

   while(sum != num) 
   { 
       if (sum < num) 
       { 
        upperBound++; 
        sum += upperBound * upperBound; 
       } 
       else if (sum > num) 
       { 
        sum -= lowerBound * lowerBound; 
        lowerBound++; 
       } 
       if (upperBound > max) 
        return false; 
   } 
   
   return true; 
   

Тесты для 5, 11, 13, 54, 181 и 595. Да, некоторые из них не являются палиндромами, но я просто проверяю сумму квадратов последовательных чисел.

1: true 
2: false 
3: false 
4: true 
5: true 
11: false 
13: true 
54: true 
180: false 
181: true 
595: true 
596: false 

Answer 2

public static boolean isSumOfSquares(int num) { 
     int sum = 0; 
     int lowerBound = 1; 

     //largest square root that is less than num 
     int upperBound = (int)Math.floor(Math.sqrt(num)); 

     while(lowerBound != upperBound) { 
      sum = 0 
      for(int x=lowerBound; x<upperBound; x++) { 
       sum += x * x; 
      } 

      if(sum != num) { 
       lowerBound++; 
      } 
      else { 
       return true; 
      } 
     } 

     return false; 
    } 

Answer 3

Один из методов (вероятно, не эффективен) я могу думать с верхней части моей головы является,

Пусть N 90.
Х = 9 (целое значение SQRT 90)

1. Создайте массив всех целых степеней меньше x [1,4,9,16,25,36,49,64,81]
2. Создайте все возможные комбинации элементов в массиве, используя рекурсия. [1,4], [1,9], [1,16], .... [4,1], [4,9], .... [1,4,9] ....
3. Для каждой комбинации (по мере генерации) - проверьте, равна ли сумма сумм до N

** Чтобы сэкономить пространство памяти, при генерации каждого экземпляра вы можете проверить, суммируется ли оно до N. Если нет, , отбросьте его и перейдите к следующему.

Один из экземпляров будет [9,81], где 9 + 81 = [90]

Answer 4

1. , так как есть только несколько целочисленных силы, вы можете создать массив полномочий.
2. Тогда вы можете указать первый и последний включенные индексы. Первоначально они равны 1.
3. в то время как сумма меньше вашего номера, увеличивайте последний включенный индекс. Обновить сумму
4. в то время как сумма выше, увеличение 1-й включенный индекс. Обновление сумма

Или без какого-либо массива, как в ответ rgettman в

Answer 5

Возможно, мне не хватает точки, но с учетом N, для 1 < = N < = 1000 наиболее эффективным способом было бы решить проблему каким-то образом (возможно перебор) и хранить решения в коммутаторе ,

switch(n){ 
    case 5: 
    case 13: 
    ... 
     return true; 
    default: 
     return false; 
} 

Answer 6

public static boolean validNumber(int num) { 
    if (!isPalindrome(num)) 
     return false; 
    int i = 1, j = 2, sum = 1*1 + 2*2; 
    while (i < j) 
     if (sum > num) { 
      sum = sum - i*i; i = i + 1; 
     } else if (sum < num) { 
      j = j + 1; sum = sum + j*j; 
     } else { 
      return true; 
     } 
    return false; 
} 

Однако Там Есть только одиннадцать "Хорошие номера" {5, 55, 77, 181, 313, 434, 505, 545, 595, 636, 818}. И это очень сильно растет, для N = 10^6, только 59.

Answer 7

Начните с массива первых совершенных квадратов. Предположим, что ваши цифры равны 13 и 17, тогда ваш массив будет содержать: 1, 4 , 9, и 16

ли этот вид проверки:

---

13 минус 1 (0^2) равно 12. 1 представляет собой идеальный квадрат, 12 не является.

13 минус 2 (1^2) - 11. 2 - идеальный квадрат, 11 - нет.

13 минус 4 (2^2) 9. 4 представляет собой идеальный квадрат, 9 представляет собой идеальный квадрат, так что 13 является суммой двух совершенных

17 минус 1 равно 16. 1 и 16 - идеальные квадраты. Исключить выбор.

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

Answer 8

Просто для игры, я создал функцию Javascript, который получает все палиндромных квадратов между минимальным и максимальным значениями: http://jsfiddle.net/n5uby1wd/2/

HTML

<button text="click me" onclick="findPalindromicSquares()">Click Me</button> 
<div id="test"></div> 

JS

function isPalindrome(val) { 
    return ((val+"") == (val+"").split("").reverse().join("")); 
} 

function findPalindromicSquares() { 
    var max = 1000; 
    var min = 1; 
    var list = []; 
    var done = false, 
     first = true, 
     sum = 0, 
     maxsqrt = Math.floor(Math.sqrt(max)), 
     sumlist = []; 

    for(var i = min; i <= max; i++) { 
     if (isPalindrome(i)) { 
      done = false; 

      //Start walking up the number list 
      for (var j = 1; j <= maxsqrt; j++) { 
       first = true; 
       sum = 0; 
       sumlist = []; 

       for(var k = j; k <= maxsqrt; k++) { 
        sumlist.push(k); 
        sum = sum + (k * k); 

        if (!first && sum == i) { 
         list.push({"Value":i,"Sums":sumlist}); 
         done = true; 
        } 
        else if (!first && sum > i) { 
         break; 
        } 

        first = false; 
        if (done) break; 
       } 

       if (done) break; 
      } 
     } 
    } 

    //write the list 
    var html = ""; 
    for(var l = 0; l < list.length; l++) { 
     html += JSON.stringify(list[l]) + "<br>"; 
    } 
    document.getElementById("test").innerHTML = html; 
} 

Где мин = 1 и max = 1000, возвращается:

{"Value":5,"Sums":[1,2]} 
{"Value":55,"Sums":[1,2,3,4,5]} 
{"Value":77,"Sums":[4,5,6]} 
{"Value":181,"Sums":[9,10]} 
{"Value":313,"Sums":[12,13]} 
{"Value":434,"Sums":[11,12,13]} 
{"Value":505,"Sums":[2,3,4,5,6,7,8,9,10,11]} 
{"Value":545,"Sums":[16,17]} 
{"Value":595,"Sums":[6,7,8,9,10,11,12]} 
{"Value":636,"Sums":[4,5,6,7,8,9,10,11,12]} 
{"Value":818,"Sums":[2,3,4,5,6,7,8,9,10,11,12,13]} 

Обновленная версия, которая позволяет тестировать отдельные значения: http://jsfiddle.net/n5uby1wd/3/ Чтобы найти их между 1 и 1 000 000, потребовалось всего несколько секунд.

Answer 9

Вы ищете S (n, k) = n^2 + (n + 1)^2 + (n + 2)^2 + ... (n + (k - 1))^2, который суммируется до заданной суммы m, т. е. S (n, k) = m. (Я предполагаю, что вы проверите отдельно палиндромы.) S (n, k) - m является квадратичным по n. Вы можете легко выработать явное выражение для S (n, k) - m, поэтому решите его, используя квадратичную формулу. Если S (n, k) - m имеет положительный целочисленный корень, сохраните этот корень; он дает решение вашей проблемы.

Я предполагаю, что вы можете легко проверить, имеет ли квадрат положительный целочисленный корень. Трудная часть, вероятно, определяет, имеет ли дискриминант целочисленный квадратный корень; Я предполагаю, что вы можете понять это.

Вам нужно будет найти k = 2, 3, 4, .... Вы можете остановиться, когда 1 + 4 + 9 + ... + k^2> m. Вы можете, вероятно, разработать явное выражение для этого.

Answer 10

Я думаю, вы можете определить, является ли число суммой последовательных квадратов быстро следующим образом, что значительно уменьшает количество арифметики, которая должна быть выполнена. Во-первых, предвычисления все суммы квадратов и поместить их в массив:

0, 0+1=1, 1+4=5, 5+9=14, 14+16=30, 30+25=55, 55+36=91, ... 

Теперь, если число является суммой двух или более последовательных квадратов, мы можем завершить его, добавив несколько из выше последовательности получить другое число в приведенной выше последовательности. Например, 77 = 16 + 25 + 36, и мы можем завершить его, добавив указанное число 14 = 0 + 1 + 4 + 9, чтобы получить указанное число 91 = 14 + 77 = (0 + 1 + 4 + 9) + (16 + 25 + 36). Обратное имеет место и при условии, что два перечисленных числа не менее двух позиций в списке.

Как долго должен храниться наш список? Мы можем остановиться, когда добавим первый квадрат n, который удовлетворяет (n-1)^2+n^2 > max, где max в этом случае составляет 1000. Упрощая, мы можем остановиться, когда 2(n-1)^2 > max или n > sqrt(max/2) + 1. Итак, для max=1000 мы можем остановиться, когда n=24.

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

Вот мое предложение в Java:

import java.util.HashMap; 

public class SumOfConsecutiveSquares { 

    // UPPER_BOUND is the largest N we are testing; 
    static final int UPPER_BOUND = 1000; 
    // UPPER_BOUND/2, sqrt, then round up, then add 1 give MAX_INDEX 
    static final int MAX_INDEX = (int)(Math.sqrt(UPPER_BOUND/2.0)) + 1 + 1; 

    static int[] sumsOfSquares = new int[MAX_INDEX+1]; 
    static HashMap<Integer,Integer> sumsOfSquaresHash 
    = new HashMap<Integer,Integer>(); 

    // pre-compute our list 
    static { 
    sumsOfSquares[0] = 0; 
    sumsOfSquaresHash.put(0,0); 
    for (int i = 1; i <= MAX_INDEX; ++i) { 
     sumsOfSquares[i] = sumsOfSquares[i-1] + i*i; 
     sumsOfSquaresHash.put(sumsOfSquares[i],i); 
    } 
    } 

    public static boolean isSumOfConsecutiveSquares(int N) { 
    for (int i=0; i <= MAX_INDEX; ++i) { 
     int candidate = sumsOfSquares[i] + N; 
     if (sumsOfSquaresHash.containsKey(candidate) 
      && sumsOfSquaresHash.get(candidate) - i >= 2) { 
     return true; 
     } 
    } 
    return false; 
    } 

    public static void main(String[] args) { 
    for (int i=0; i < 1000; ++i) { 
     if (isSumOfConsecutiveSquares(i)) { 
     System.out.println(i); 
     } 
    } 
    } 

} 

Каждый запуск функции выполняет не более 25 сложений и 25 используют хэш-таблицы. Нет умножений.

Чтобы эффективно использовать эту проблему, постройте 1, 2 и 3-значные палиндромы (1-значная цифра проста: 1, 2, ..., 9; 2-значная цифра умножением на 11: 11, 22, 33, ..., 99; 3-значный по формуле i * 101 + j * 10. Затем проверьте палиндромы с приведенной выше функцией и распечатайте, если оно вернет true.