0

在java中-如果我有一张索引卡，一侧写有字母C，另一侧写有S。我如何编写一个递归方法来打印每个用 C 和 S 丢弃卡片的 sessoin。例如：如果我放下它 4 次，所有可能的放下它的方法如下：

SCSC SCSS SSCC SSCS SSSC SSSS

4

2 回答 2

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”字符，递归基本情况是前缀长度是指定的长度（在您的情况下为 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 回答
0

所以这个问题实际上要简单得多，如果你意识到翻牌实际上只是在二进制中向上计数。

考虑到这一点，您可以只跟踪X位长的数字（其中X是您要跟踪的卡片数量），然后通过查看 1 ( S) 或 0 ( C)的位置来打印卡片.

完成此操作后，检查所有位置是否都有 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 回答