Как мне написать программу, чтобы найти количество двоичных строк длины n, содержащих ровно три единицы, все подряд

Question

Здесь я использовал динамический c подход к программированию.

dp (i, x): обозначает количество строк длины i с x последовательными 1 с в позиции i + 1 до i + x.

n здесь - длина строки битов, взятой в качестве ввода от пользователя

Однако, я думаю, что я, возможно, считаю строки, которые имеют более 3 последовательных строк?

РЕДАКТИРОВАТЬ : просто чтобы уточнить

• Я ищу строки с ровно 3 1 с. Например, 111000 является допустимой строкой, а 1110101111 и 10101000 - нет.

#include<stdio.h>
#include<stdlib.h>

int solve(int i,int x,int **arr)
{
    if(i<0) 
        return x==3;
    if(arr[i][x]!=-1)
        return arr[i][x];

    arr[i][x] = solve(i-1,0,arr);
    arr[i][x]+=solve(i-1,x+1,arr);

    return arr[i][x];
}

int main()
{

    int n;
    scanf("%d",&n);

    int **arr = (int**)malloc(n*sizeof(int*));
    for(int i=0;i<n;i++)
        arr[i] = (int*)malloc(4*sizeof(int));

    for(int i=0;i<n;i++)
        for(int j=0;j<4;j++)
            arr[i][j]=-1;

    for(int i=0;i<n;i++)
        arr[i][3] = (1<<(i+1));

    printf("%d",solve(n-1,0,arr));
    return 0;
}

Answer 1

Я не уверен, хорошо ли я понял ваш вопрос:

Вопрос не в следующем: «Что представляют собой двоичные числа, содержащие ровно три последовательных числа?» , но просто: «Каково число двоичных чисел, содержащих ровно три последовательных?» .

Если вас просто интересует число, вы можете просто вычислить его наизусть:

1110xxxxx (total length : N) : amount of such numbers : 2^(N-4) [(N-4) digits with 2 possibilities)]
xx01110xx (total length : N) : amount of such numbers : 2^(N-5)*(N-5)
                                                                [(N-5) digits with 2 possibilities]
                                                                [(N-5) places to put the '01110']
xxxxx0111 (total length : N) : amount of such numbers : 2^(N-4) [(N-4) digits with 2 possibilities]

Решение: 2*2^(N-4) + 2^(N-5)*(N-5)

(я не проверил полностью, простите меня, если есть ошибки)

Если вы не уверены, что вам действительно нужно сгенерируйте их все, тогда вычисление может оказаться лучшим (и гораздо более быстрым) решением.

Answer 2

Ваше состояние DP [i][x] означает - количество двоичных строк длиной i, которые имеют x бит в конце, поэтому вы также учитываете строки типа 11110111.

. принять во внимание группы из 3, которые не являются суффиксами, для этого вы можете обновить состояние dp следующим образом: [i][x][y] - количество двоичных строк длиной i, которые имеют x бит в конце и максимум y последовательных бит .

Модификация кода весьма минимальна:

int solve(int i,int x, int y, int ***arr)
{
    if(y > 3) return 0;
    if(i<0) return y==3;
    if(arr[i][x][y]!=-1) return arr[i][x][y];

    arr[i][x][y] = solve(i-1,0,y,arr);
    arr[i][x][y]+=solve(i-1,x+1,max(x+1,y),arr);

    return arr[i][x][y];
}