Алгоритм нахождения количества палиндромов в интервале - PullRequest
Новая
       36

Алгоритм нахождения количества палиндромов в интервале

1 голос
/ 28 октября 2019

В настоящее время мне поручено написать программу, которая рассчитывает количество палиндромов в любой базе с интервалом <2;36>. Проблема в том, что мое решение имеет временную сложность O(n^2) в лучшем случае, и, если честно, очень медленно.

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

Это то, что я получил до сих пор: 

int isTrue = 1;
int arr[64];

while(n > 0)
{
   arr[counter] = n % base;
   n = n / base;
   counter++;
}

for(int i = 0; i < counter; i ++)
{
   if(arr[i] != arr[counter - i - 1])
   {
      isTrue = 0;
      break;
   }
}

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

Под гораздо большими числами я подразумеваю интервалы, охватывающие миллиарды чисел, например, одним из входных данных является: 

c 15 62103360044 155888062462
Result : 123502

Где c - это задача, которую должна выполнить программа (тамбыла опция l, которая перечисляла все палиндромы, которые не встречаются в бонусных тестах), 15 является базовым, а два других числа являются пределами интервала.

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

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

1 Ответ

0 голосов
/ 28 октября 2019

  • Быстрая проверка палиндрома - это оптимизация minor . Первоначально я бы даже использовал преобразование числа java в строку.

  • Вам нужно пошагово пересечь интервал.

  • Вы можетеиспользуйте рекурсию для упрощения в начальной версии вашего алгоритма.

Давайте посмотрим на базу 10: 

 62_103_360_044
155_888_062_462

 6 ...        6 (recursion on the middle part)
 7 ...        7
 8 ...        8
 9 ...        9
1 ...         1

Вам нужно:

  • Количество цифр (ваша counter)
  • Первая наиболее значимая цифра
  • Параметры начало и конец

Для этого шага вам нужно увеличить только одну цифру,что даже можно сделать как char.

Также обратите внимание, что рекурсивный вызов on ... дает тот же результат для 7, 8 и 9 с началом 000..000 и концом 999..999.

Это будет очень быстро. Удачное кодирование.

Использование рекурсии: Я не даю четкого ответа, так как это бы победило задачу задания. 

public BigInteger palindromesInInterval(int base, BigInteger from, BigInteger to) {
    return palindromesRec(base, from.toString(base), to.toString(base));
}

private BigInteger palindromesRec(int base, String from, String to) {
    // Do the simple work:
    if (from.length() > to.length()) {
        return BigInteger.ZERO;
    }
    if (from.length() == to.length() && from.compareTo(to) > 0) {
        return BigInteger.ZERO;
    }
    if (from.length() == 1) {
        ...
    }
    // Do a step:
    int highDigit = Integer.parseInt(from.substring(0, 1), base);
    int lowDigit = Integer.parseInt(from.substring(from.length() - 1), base);

    BigInteger sum = BigInteger.ZERO;
    int digit = Math.max(highDigit, lowDigit);
    String from2 = from.substring(1, from.length() - 2); // Can start with 0
    String to2 = "1000...000" -1; // Niners so to say.
    while (digit < base) {
         ...
         sum = sum.add(palidromesRec(base, from2, to2)); // RECURSION
         from2 = "000...000";
    }
    ...
    return sum;
}

Рекурсия, вызывающая себя, здесь только один раз, без дополнительных параметров, которые часто используются. Например, гораздо проще разделить работу на: 

from  6 2_103_360_04 4
  to  9 9 ..       9 9

from 1 00 ..       0 1
  to 1 55_888_062_46 2

и рассчитать для каждого X 

from X 000 X   (n zeroes)
  to X 999 X   (n time (base-1))

как основание (n + 1) / 2 .

Для этого вам нужен уровень абстракции / упрощения. Keep-это просто.

...