Блог

Для некоторого n мы должны определить количество разных строк, состоящих только из ‘0’ и ‘1’, в которых нет двух смежных ‘1’. (Размер строки равен n) Извините за мой плохой английский. Это моя попытка:

 long Num(int n){
    if(n==0)
        return 0;
    else if(n==1)
        return 2;
    else if(n==2)
        return 3;
    else if(n==3)
        return 5;
    else
        return 2*Num(n-2)   Num(n-3);
};
  

Проблема :

Чтобы узнать количество возможных двоичных строк длиной n, не имеющих последовательных единиц.

Ввод / вывод :

Ввод: N = 2 Вывод: 3 // 3 строки — 00, 01, 10

Ввод: N = 3 Вывод: 5 // 5 строк — 000, 001, 010, 100, 101

Подход :

Пусть a[i] — количество двоичных строк длины i, которые не содержат никаких двух последовательных единиц и которые заканчиваются на 0. Аналогично, пусть b [i] — количество таких строк, которые заканчиваются на 1. Мы можем добавить 0 или 1 к строке, оканчивающейся на 0, но мы можем добавить 0 только к строке, оканчивающейся на 1. Это дает рекуррентное отношение:

 a[i] = a[i - 1]   b[i - 1]
b[i] = a[i - 1] 
  

Базовыми случаями приведенного выше повторения являются a [1] = b [1] = 1. Общее количество строк длины i равно просто a[i] b[i] . При использовании массива i (длина строки) будет на 1 меньше, для нулевой позиции массива.

Решение :

 int countStrings(int n)
{
    int a[] = new int [n];
    int b[] = new int [n];
    a[0] = b[0] = 1;
    for (int i = 1; i < n; i  )
    {
        a[i] = a[i-1]   b[i-1];
        b[i] = a[i-1];
    }
    return a[n-1]   b[n-1];
}
  

Для получения более подробной информации см. http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s /