查找可能的组合数

Question

有两个字母"X"和"Y"。需要使用这两个字母组成一个长度为 N 的字符串。

如果 N 应该以 "Y" 开头并且不会出现两个或更多个连续的 "X"，那么有多少种可能的组合？

考虑 N = 7:

我通过以下方式解决了这个问题：

我的解决方案：

[没有。以字母 "Y"] 开头的组合数 -[No:包含两个连续 X(n-1 种可能性)的组合 + No: 包含 3 个连续 X(n-1 种可能性)+.....]

=Math.pow(2,N-1)-[(N-2)(N-1)/2];

问题出在我要减去的部分。我遗漏了字符串中包含两个连续 "X" 和总共 3 个 X 的元素。类似地连续 2 个，总共 4 个 X。我想找到一个通用公式，用于查找可能不会出现 'R' 或更多连续 "X" 的字符串。

请帮我找到解决办法。

Answer 1

对于R = 1，类似于斐波那契。

F(0) = F(1) = 1
F(N) = F(N-1) + F(N-2)

Java 中的最佳解决方案。

static int func(int n) {
    if (n < 1) return 0;   // as you required, F(0) = 0
    int n1 = 1, n2 = 1;    // however, for F(2..) we must have F(0) = 1
    for (int i = 2; i <= n; i++) {
        int n0 = n1 + n2;
        n2 = n1;
        n1 = n0;
    }
    return n1;
}

要将 R 的解决方案归纳为允许的连续 'X' 个字符数，您只需将序列中的 R + 1 个前面的元素相加即可。正如我们所见，对于 R = 1，公式是 F(N) = F(N-1) + F(N-2)；现在 R = 2 的公式是 F(N) = F(N-1) + F(N-2) + F(N-3).

因此我们推导出一个函数，它接受任何 N 和 R。

static int func(int n, int r) {
    if (n < 1) return 0;   // as you required, F(0) = 0
    if (n == 1 || r < 1) return 1;
    int[] a = new int[r + 1];
    a[r] = a[r-1] = 1;     // however, for F(2..) we must have F(0) = 1
    for (int i = 2; i <= n; i++) {
        int x = a[0];
        for (int j = 1; j <= r; j++) {
            x += a[j];
            a[j-1] = a[j];
        }
        a[r] = x;
    }
    return a[r];
}

查找可能的组合数

Find Number of combinations possible

java

math

combinations

permutation