再帰的な文字列連結

Question

文字列を再帰的に連結する必要があり、問題が発生しました。

質問は、s(0) = 0, s(1) = 1, s(n) = s(n-1)s(n-2) for n >= 2です。ここで、s(n)は、前の2つの文字列の連結された文字列です。 (n, k)一対の多くのインスタンスが最初の整数として入力されるか

入力非負整数 n (0 <= n <= 60)正の整数kを含む各ライン、続いて表示されます。

出力は、連結された文字列s(n)のk番目の文字を出力することになっています。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)); 
     } 
    } 
} 

これは私がこれまで持っている、それが与えられたためにどのような作品ですサンプルのテストケース。これは、ほとんどの場合のために動作しますが、nが大きくなると一度起こって、私のコードに問題があるということですなぜ、私はこのエラー

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

を取得しますか？

ありがとうございました！

Answer 1

これはJavaで行い、テールコールの最適化を行うFP言語ではないため、再帰と文字列の連結という2つのことが間違っています。 Javaでは、反復と文字列のビルダーが変更可能です。

具体的には、再帰関数は、完全な文字列の途中で生成したすべての中間文字列を保持します。それはO（n ）のメモリ使用量です。

Answer 2

あなたのアプローチの問題は、あまりにも多くのスローアウェイ文字列を作成することです。あなたが書くたびに

return str1 + str2; 

新しいオブジェクトStringが作成されます。そのようなスローアウェイオブジェクトの数は、nで直線的に増加し、その全長はO（n ）として増加します。

• は、あなたのプログラムの線形を維持し、トップレベルでStringBuilderを渡す：

  あなたはこの問題には2つのソリューションを持っています。各再帰呼び出しは、連結のために演算子+を使用するのではなく、appendを呼び出します。

• Memoizationを使用する - 計算する必要がある文字列の数が少ないため、これまで計算した文字列を保存して再利用することで問題を解決できます。問題の制限付き

もっと大きな問題は、その出力がStringに収まることができないということである：60のためのあなたのコードの出力は、かなり長い間、Javaは、長さが最大2 の文字列を可能に - つまり、1,548,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

私は非常にキャッシュをお勧めします各メソッドの呼び出しの結果、すべてを何度も再計算する必要はありません。小さなヒープを犠牲にしてパフォーマンスを大幅に向上させます。このようなもの？ 2Gヒープ上、generateStringは単にによる結果の文字列の長さに、私のマシン上でI = 40を通って上に動作することを

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; 
    } 
} 

注意。文字列の長さは2*fib(i)バイトになるので、それらのインデックスにヒットすると、メモリ要件はかなり急速に爆発するでしょう。

Answer 5

マップの回答と同じアイデア（中間の文字列を格納する、再計算しないでください）が、代わりに配列を使用します。

これは、すべての行を読み取り、最大値を見つけてnの値を見つけて、それによって1つの配列だけを保存し、(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)); 
     } 

    } 
} 

サンプル実行

（期待通りに同じ入力および出力）