1

決勝に向けて勉強しているCSの新入生。一般的に再帰メソッドが何回呼び出されるかを把握しようとしています。例としてコードを追加しました。abcdとefghを入力した場合、文字列のサイズに基づいて何回呼び出しますか？nが任意のデータサイズである場合、呼び出しの数は任意の再帰メソッドでn（？）です。

public static String interweave(String s1, String s2)
{ 
   if (s1.equals("") ) return s2;
   else if (s2.equals("")) return s1;
   else return "" + interweave(s1.substring(0,s1.length()-1), s2.substring(0,s2.length()-1))
       +s1.charAt(s1.length()-1)+s2.charAt(s2.length()-1);
}
4

2 に答える 2

0

質問では、再帰的な各ステップで、両方の文字列のいずれかが長さゼロになるまで、両方の文字列のサイズを1つ減らします（再帰の基本ケース）。再帰呼び出しの数がであることが簡単にわかりますmin(m, n) + 1。ここmで、はの初期の長さでs1ありn、はの初期の長さですs2。

たとえば、s1 = "abc"トラバースs2 = "de"するために2回の再帰呼び出しs2（最小長の文字列）に加えて、ベースケースで終了するための1回の追加呼び出しが必要な場合min(s1.length(), s2.length()) + 1 == 3。次のようにプログラムでテストできます。

static int counter;

public static String interweave(String s1, String s2) {
    counter++;
    if (s1.equals(""))
        return s2;
    else if (s2.equals(""))
        return s1;
    else
        return interweave(s1.substring(0, s1.length()-1), s2.substring(0, s2.length()-1))
        + s1.charAt(s1.length()-1)+s2.charAt(s2.length()-1);
}

public static int count(String s1, String s2) {
    counter = 0;
    interweave(s1, s2);
    return counter;
}

次のステートメントを実行すると、数式は期待どおりに機能します。

// s1.length() == s2.length()
System.out.println(count("abcde", "fghij"));
> 6

// s1.length() > s2.length()
System.out.println(count("abcde", "fg"));
> 3

// s1.length() < s2.length()
System.out.println(count("ab", "cdefg"));
> 3
于 2012-04-28T13:12:45.667 に答える
0

文字は長さだけを意味するものではありません。次のように、これを数値の問題に変換できます。

public static String interweave(int s1, int s2)
{ 
   if (s1 == 0) return s2;
   else if (s2 == 0) return s1;
   else return interweave(s1-1, s2-1)+2;
}
于 2012-04-28T02:06:57.317 に答える