Найти количество возможных комбинаций

Есть две буквы "X"и " Y". Строка длины N должна быть сформирована с использованием этих двух букв.

Сколько комбинаций, которые могут быть возможны там, где N должно начинаться с "Y "и не будет двух или более последовательных" X"?

Рассмотрим N = 7:

Я подошел к решению следующим образом:

Мое Решение :

[- нет. комбинаций, которые начинаются с буквы "Y"] - [нет: комбинаций, содержащих два последовательных X (n-1 возможностей) + нет: комбинаций, содержащих 3 последовательных X(n-1 возможностей)+.....] 

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

Проблема заключается в части, которую я вычитаю. Где я пропускаю элементы, которые содержат два последовательных " X " и всего 3 Xs в строке. Аналогично 2 последовательных и всего 4 Xs. Я хочу найти общую формулу для нахождения ни одной из строк, которые возможны там, где не будет "R" или более последовательных "X".

Пожалуйста, помогите мне найти решение для этого.
1 2
combinations permutation

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];
}
1