Рекурсивная строка Конкатенация

Question

Я работал над вопросом, который требует конкатенации строк рекурсивно и сталкивался с проблемой.

Вопрос гласит, что s(0) = 0, s(1) = 1, s(n) = s(n-1)s(n-2) for n >= 2, где s(n) - это объединенная строка из двух предыдущих строк.

ввода будет указано, как много примеров (n, k) пары будут введены в качестве первого целого числа, после чего каждой строки, содержащей неотрицательное целое число n (0 <= n <= 60) и положительное целое число k.

Выход должен быть распечатав -ю характер сцепленной строки s(n), где k меньше или равно количеству символов в строке s(n). вход

s(0) = 0 
s(1) = 1 
s(2) = 10 
s(3) = 101 
s(4) = 10110 
s(5) = 10110101 
and so on. 

Пример:

3 
5 2 
0 1 
4 3 

Выход:

0 
0 
1 

Мой код:

import java.util.*; 

public class recursivestring { 

    public static String recursive(int n, int i, String str1, String str2){ 

     if (i == n - 1) 
      return str1 + str2; 

     return recursive(n, i + 1 , str1 + str2, str1); 

    } 
    public static void main(String[] args) { 

     int lines, i, n, k; 
     String result; 
     Scanner input = new Scanner(System.in); 

     lines = input.nextInt(); 

     for (i = 0; i < lines; i++) { 
      n = input.nextInt(); 
      k = input.nextInt(); 
      if (n == 0) { 
       result = "0"; 
      } else if (n == 1) { 
       result = "1"; 
      } else if (n == 2) { 
       result = "10"; 
      } else { 
       result = recursive(n, 2, "10", "1"); 
      } 
      System.out.println(result.charAt(k-1)); 
     } 
    } 
} 

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

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Почему это происходит, и там что-то случилось с моим кодом?

Спасибо!

Answer 1

Поскольку вы делаете это на Java, а не на языке FP с оптимизацией хвостового вызова, две вещи неверны: рекурсия и конкатенация строк. В Java вы должны выполнить итерацию и строку здание с изменчивым строителем.

В частности, ваша рекурсивная функция сохраняет всю промежуточную строку, которую вы производите на своем пути, до полной строки. Это O (n) использование памяти.

Answer 2

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

return str1 + str2; 

новый объект String создается. Количество таких отбрасываемых объектов растет линейно с n, а их общая длина растет как O (n).

У вас есть два решения этой проблемы:

• Держите вашу линейную программу, и передавать StringBuilder на верхнем уровне. Каждый рекурсивный вызов вызывал бы append, вместо использования оператора + для конкатенации.
• Используйте Memoization - так как количество строк, которые вам нужно вычислить, невелико, чтобы сохранить те, которые вы вычислили до сих пор, и повторное использование их должно устранить проблему.

большая проблема с пределами проблема заключается в том, что его выход не может поместиться в String: Java позволяет строки до 2 в длину, в то время как выход кода для 60 совсем немного дольше - а именно 1548 008 755 920 символов. Хотя вы должны сохранить этот вывод в файле, нет возможности сохранить его как String с записью или без нее.

Answer 3

Ну, честно говоря, это выглядит как Фибоначчи мне так меня подход выглядит немного, как ...

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

private static String stringbonacci(int i) { 
if (i == 0) { 
    return "0"; 
} 
if (i == 1) { 
    return "1"; 
} else { 
    return stringbonacci(i - 1) + stringbonacci(i - 2); 
} 
} 

и результат выглядит следующим образом:

0

1

10

101

10110

10110101

Answer 4

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

public class RecursiveString { 
    private static final Map<Integer, String> cache = new HashMap<>(); 
    static { 
     cache.put(0, "0"); 
     cache.put(1, "1"); 
    } 

    public static String generateString(Integer i) { 
     if (i < 0) return generateString(0); // or something... avoid negatives. 

     if (cache.get(i) != null) return cache.get(i); // cache hit. 

     String generated = String.format("%s%s", 
      generateString(i-1), generateString(i-2)); 
     cache.put(i, generated); 

     return generated; 
    } 
} 

Обратите внимание, что на куче 2G, generateString работает через I = 40 на моей машине, просто из-за длины полученной строки. Длина строки будет 2*fib(i) байт, поэтому ваше требование к памяти скоро взорвется, как только вы начнете ударять по этим индексам.

Answer 5

Та же идея, что и ответ с картой (сохраните промежуточную строку, не перекомпонуйте), но вместо этого используйте массив.

Это может быть оптимизировано немного больше, читая все строки, а затем найдя максимальное значение n, тем самым сохраняя только один массив, а затем перебираем пары (n, k).

import java.util.Scanner; 

public class BinaryConcat { 
    private String[] dict; 

    public BinaryConcat(int n) { 
     if (n < 0) throw new IllegalArgumentException(); 
     dict = new String[2 + n]; // Have 2 base cases 

     dict[0] = "0"; 
     dict[1] = "1"; 
    } 

    public String getValue(int n) { 
     if (n < 0) throw new IllegalArgumentException(); 
     if (n <= 1) return dict[n]; 
     if (dict[n] == null || dict[n].isEmpty()) { 
      dict[n] = String.format("%s%s", getValue(n - 1), getValue(n - 2)); 
     } 

     return dict[n]; 
    } 

    public static void main(String[] args) { 

     Scanner input = new Scanner(System.in); 

     int lines = input.nextInt(); 
     input.nextLine(); // consume linefeed 

     for (int i = 0; i < lines; i++) { 
      String line = input.nextLine(); 
      String[] nk = line.split(" "); 
      int n = Integer.parseInt(nk[0]); 
      int k = Integer.parseInt(nk[1]); 

      String value = new BinaryConcat(n).getValue(n); 
      System.out.println(value.charAt(k - 1)); 
     } 

    } 
} 

Пример запуска

(тот же вход и выход, как и ожидалось)