정수 N과 K가 주어졌습니다. 길이가 N이고 0과 1만 포함된 이진 문자열이 있습니다. 목표는 K개의 연속적인 1을 갖는 길이가 N인 문자열의 수를 찾는 것입니다. 즉, N=3이고 K=2인 경우 2개의 연속적인 1이 있는 가능한 모든 3자리 이진 문자열을 계산합니다.
예 − 111, 여기에 인접한 1이 두 번 나타납니다( K 번 ).
011과 110에서는 인접한 1이 한 번만 나타났습니다.
이전 값의 결과를 저장하여 이를 해결합니다.
3D 배열 개수[x][y][z]를 사용합니다. 여기서 x는 N, y는 K, z는 문자열의 마지막 숫자(0 또는 1)
- N=1인 경우 문자열은 "0"과 "1"이 됩니다. 인접한 1의 개수=0.
따라서 모든 K에 대해. N=1이면 count=0입니다.
개수[1][K][0] =개수[1][K][1] =0.
- 마지막 숫자가 0일 때, 인접한 1을 K로 간주하기 위해
길이가 N-1인 모든 자릿수(K개의 1 + 마지막 0 포함) → 새 길이 =N
K 인접 1의 개수가 C인 경우 끝에 0을 추가해도 해당 개수는 변경되지 않습니다.
개수[N][K][0] =개수[N-1][K][0] + 개수[N-1][K][1]
- 마지막 숫자가 1일 때, 인접한 1을 K로 간주하기 위해
0으로 끝나는 길이 N-1의 모든 자릿수 K 1 + 마지막 1 → 새 길이 =N,
개수[N-1][K][0]
N-1 길이의 모든 숫자가 1로 끝나는 K-1 1 + 마지막 1 → 새 길이 =N,
개수[N-1][K-1][1]
개수[N][K][1] =개수[N-1][K][0] + 개수[N-1][K-1][1]
총 문자열=count[N][K][0] + count[N][K][1]
입력
N=4, K=2
출력
Count of strings: 2
설명 − 1110, 0111은 인접한 1이 두 번만 나타나는 길이가 4인 유일한 문자열입니다.
1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times
입력
N=3, K=1
출력
Count of strings: 2
설명 − 110, 011.은 인접한 1이 한 번 나타나는 길이가 3인 유일한 문자열입니다.
111에서 인접한 1이 두 번 나타납니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 N과 K는 문자열의 길이와 no를 저장합니다. 인접한 1이 각각 나타나는 횟수입니다.
-
stringcount(int n, int k) 함수는 n과 k를 매개변수로 사용하고 1에 인접한 K번의 문자열 개수를 반환합니다.
-
배열 count[i][j][0/1]은 0 또는 1로 보내는 j가 인접한 1인 길이 i의 문자열 개수를 저장하는 데 사용됩니다.
-
초기 조건은 count[1][0][0] =1입니다. 개수[1][0][1] =1;
-
이제 2개의 길이 문자열(i=2)에서 n개의 길이로 시작합니다. 이러한 각 문자열에 대해 Ktimes 인접한 1의 수를 확인합니다. j=0;j<=k, 이전 카운트에서. 현재 개수[i][j][0] 및 개수[i][j][1]를 업데이트합니다.
-
j-1>=0이면 인접한 1의 개수가 1보다 큽니다. 그런 다음 count[i][j][1] + count[i - 1][j - 1][1로 1로 끝나는 문자열의 개수를 업데이트합니다. ];
-
끝에 count[n][k][0] 및 count[n][k][1]을 추가합니다. 결과적으로 저장하십시오.
- 원하는 개수만큼 결과를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
//count of strings with length=n and adajcent 1's=k
int count[n + 1][k + 1][2]={0};
//count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
//count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
// If n = 1 and k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// number of adjacent 1's can not exceed i-1
for (int j = 0; j <= k; j++) {
count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
count[i][j][1] = count[i - 1][j][0];
if (j - 1 >= 0)
count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1];
}
}
int result=count[n][k][0]+count[n][k][1];
return result;
}
int main(){
int N = 6, K = 3;
cout <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
return 0;
} 출력
Strings of length 6 and 3 adjacent 1's in each :7