0

Javaで - 側面にCが書かれ、反対側にSが書かれたインデックスカードがあるとします。C と S のカードをドロップする各セッションを出力する再帰メソッドを作成するにはどうすればよいですか。例: 4 回ドロップした場合、この特定の順序で次のようにドロップするすべての可能な方法:

SCSC SCSS SSCC SSCS SSSC SSSS

4

2 に答える 2

0

したがって、カードをめくることは実際には 2 進数で 1 ずつカウントアップするだけであることに気がつくと、この問題は実際にはずっと単純になります。

それを念頭に置いて、Xビット長の数字（Xは追跡したいカードの数）を追跡し、1（S）または0 （ C）がある場所を確認してカードを印刷できます。 .

その後、すべての位置に 1 があるかどうかを確認します。そうであれば、再帰を終了します。そうでない場合は、数値に 1 を追加して、関数を再度実行します。

編集

数値のビット数が事前にわかっている場合 (計算するのに十分簡単なもの)、ビットシフトを使用できます (>>ここでは最適です)。したがって、たとえば、数値を調べて各位置を確認する簡単な for ループを作成できます。

int cardTracker = 0b0110; //this is 6 in decimal
char[] toPrint = new char[4];

//The 4 here is the length of the binary number
for(int i = 0; i < 4; i++)
{
    //This if statement checks if the last number is 0 or 1
    if((cardTracker >> ((4 - 1) - i) % 2  == 0)
    {
        toPrint[i] = 'C';
    }
    else
    {
        toPrint[i] = 'S';
    }
}

の内容を印刷すると、上記は次のように印刷されますtoPrint。

CSSC

上記を使用して、再帰問題のコードに適用できることを願っています。

于 2013-11-05T14:11:59.493 に答える
0

それは実際にはかなり単純です：

public void flip(List<String> items, int length, String prefix)
{
    if (prefix.length() == length) {
        items.add(prefix);
        return;
    }
    increments(items, length, prefix + 'C');
    increments(items, length, prefix + 'S');
}

ご覧のとおり、「C」文字用と「S」文字用の 2 つの再帰呼び出しがあり、再帰の基本ケースは、プレフィックスの長さが指定された長さ (この場合は 4) の場合です。

次のように呼び出します。

List<String> inc = new LinkedList<>();
increments(inc, 4, "");
for (String s : inc)
    System.out.println(s);

どの出力:

CCCC
CCCS
CCSC
CCSS
CSCC
CSCS
CSSC
CSSS
SCCC
SCCS
SCSC
SCSS
SSCC
SSCS
SSSC
SSSS

このメソッドは、任意の文字配列に対して簡単に一般化できます。

public void increments(List<String> items, int length, 
                       String prefix, char[] chars)
{
    if (prefix.length() == length) {
        items.add(prefix);
        return;
    }
    for (char c : chars)
        increments(items, length, prefix + c, chars);
}

List<String> inc = new LinkedList<>();
increments(inc, 4, "", new char[] {'C', 'S'});
for (String s : inc)
    System.out.println(s);

これにより、同じ出力が得られます。

注: このメソッドは非常に複雑で、O(pow(chars.length, length)) であるため、大きな入力サイズで実行しようとすると、完了するまでに (非常に) 長い時間がかかります。

Integer.toBinaryString(int)アプローチ

リクエストに応じて:

public void increments_ibs(List<String> items, int n, int i)
{
    if (i >= Math.pow(2, n))
        return;

    String bs = Integer.toBinaryString(i);
    while (bs.length() < n)
         bs = "0" + bs;
    items.add(bs.replaceAll("0", "C").replaceAll("1", "S"));

    increments_ibs(items, n, i+1);
}

これは本質的に、再帰的に記述された反復アルゴリズムです。

于 2013-11-05T14:27:10.430 に答える