6

次の Java のコードは、再帰を使用して、文字列から可能なすべての部分文字列を作成します。これをコーディングするより良い方法があるのだろうか？再帰を使いたい。

public class main {

    public static void main(String[] args) {
        generate("hello");
    }

    public static void generate(String word) {
        if (word.length() == 1) {
            System.out.println(word);
            return;
        }else{
            System.out.println(word);
            generate(word.substring(0, word.length()-1)); 
            generate(word.substring(1, word.length())); 
        }

    }

}

FAQ Q - 再帰を使用してこれを行いたいのはなぜですか? A - StackOverflow の CEO が再帰が重要だと言っているため http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

4

10 に答える 10

15

この問題にはサブ問題が重複しているため、トップダウンの再帰はあまり効果的ではありません。複数の部分文字列を複数回評価しています。

実際、それは恐ろしく効果がありません (O(2^n) だと思います)。少し長い文字列で実行してみてください。

generate("OverlappingSubproblems");

これを解決するより良い方法に興味がある場合は、次のようなことを試すことができます。

public static void generate2(String word) {
    for (int from = 0; from < word.length(); from++) {
        for (int to = from + 1; to <= word.length(); to++) {
            System.out.println(word.substring(from, to));
        }
    }
}

再帰を使用したい場合は、演習として再帰を使用して for ループを書き直すことができます ;)

于 2013-08-16T19:32:56.773 に答える
8

以下が最良の解決策であることが判明しました。

public class recursive {

    static String in = "1234";

    public static void main(String[] args) {
        substrings(0,1);
    }

    static void substrings(int start, int end){
        if(start == in.length() && end == in.length()){
            return;
        }else{
            if(end == in.length()+1){
                substrings(start+1,start+1);
            }else{
                System.out.println(in.substring(start, end));
                substrings(start, end+1);
            }
        }
    }

}

最初に基本ケースをチェックします: start と end の両方が in.length() と等しい場合。そうである場合、これ以上部分文字列が見つからないことを意味し、プログラムは終了します。

start=0 と end=1 から始めましょう。それらは明らかに in.length() と等しくなく、end は間違いなく in.length()+1 と等しくありません。したがって、substring(0,1) が出力されます。これは 1 です。部分文字列の次の繰り返しは substrings(0,2) になり、in.substring(0,2) が出力されます。これは 12 です。 end == in.length()+1 まで続行します。これは、プログラムが部分文字列 (0,4) を終了し、部分文字列 (0,5) に移動しようとしたときに発生します。5 == in.length()+1 なので、それが起こると、プログラムは substrings(start+1,start+1) を実行します。これは substrings(1,1) です。このプロセスは、プログラムが部分文字列 (2,2) を実行する (1,5) まで、部分文字列 (1,2) および (1,3) で続行されます。

これはすべて substrings(4,4) まで続き、その時点でプログラムは停止します。

結果は次のようになります。

1 12 123 1234

2 23 234

3 34

4

于 2013-08-17T04:42:38.563 に答える
1

Honza の答えから学ぶべきことがたくさんあります。それを再帰アルゴリズムとして書き直してみてください。

再帰的なアプローチと同様に、それを自己参照サブ問題に分割します。

1. substrings(X) = substrings_starting_at_first_character(X) + substrings(X minus first char).
2. substrings_starting_at_first_character(X) = X + substrings_starting_at_first_character(X minus last char).

次に、非自己参照ベース ケースを見つけます。

1. substrings("") = empty set.
2. substrings_starting_at_first_character("") = empty set.

そして、そこから行きます。

于 2013-08-16T19:39:21.353 に答える
0

別のクリーンなアプローチ - ループと再帰の両方を使用 (重複の問題はありません)

public static void printCombinations(String initial, String combined) {
    System.out.print(combined + " ");
    for (int i = 0; i < initial.length(); i++) {
        printCombinations(initial.substring(i + 1),
                combined + initial.charAt(i));

    }
}


public static void main(String[] args) {
        printCombinations("12345", "");
    }

出力は - 1 12 123 1234 12345 1235 124 1245 125 13 134 1345 135 14 145 15 2 23 234 2345 235 24 245 25 3 34 345 35 4 45 5

于 2014-09-22T04:05:39.073 に答える
0

再帰を使用した別のアプローチ

    public static void main(String[] args) 
    {
        subStrings("ABCDE");        
    }
    
    static void subStrings(String str) 
    {
        if(str.length()==0)
        {
            return;
        }
        subString(str);
        subStrings(str.substring(1,str.length()));
        
    }
    
    private static void subString(String str)
    {
        if(str.length()==1)
        {
            System.out.print(str+" ");
            return;
        }
        
        System.out.print(str+" ");
        subString(str.substring(0,str.length()-1));
        
    }
于 2021-01-30T08:52:52.637 に答える