计算在C ++中出现在相邻两个设置位上的k次二进制字符串
我们给定整数N和K。我们有长度为N的二进制字符串，仅包含0和1。目标是找到具有K个连续1的长度为N的此类字符串的数量。即，如果N=3，而K=2，则计算所有可能具有2个连续1的3位二进制字符串。
示例-111，此处相邻的1出现两次（K次）。
在011和110中，相邻的1仅出现一次。
我们将通过存储先前值的结果来解决此问题。
取3D数组count[x][y][z]。其中x为N，y为K，z为字符串的最后一位（0或1）
对于N=1，字符串将为“0”和“1”。相邻1的计数=0。
因此对于任何K。如果N=1，则count=0。
count[1][K][0]=count[1][K][1]=0。
当最后一位数字为0时，将相邻1的计数计为K
长度为N-1的所有数字加上K个+最后0→新长度=N
如果与1相邻的K个计数为C，则最后加0不会更改该计数。
count[N][K][0]=count[N-1][K][0]+count[N-1][K][1]
当最后一位为1时，将相邻的1计数为K
长度为N-1的所有数字都以0结尾且K个+最后1个→新的长度=N，
计数[N-1][K][0]
长度为N-1的所有数字都以1结尾，K-1个数字+最后1→新的长度=N，
计数[N-1][K-1][1]
count[N][K][1]=count[N-1][K][0]+count[N-1][K-1][1]
这样的字符串总数=count[N][K][0]+count[N][K][1]
输入项
N=4, K=2
输出结果
Count of strings: 2
解释-1110、0111是唯一长度为4的字符串，其中相邻的1仅出现两次。
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.是唯一长度为3的字符串，其中相邻的1出现一次。
在111中，相邻的1出现两次。
以下程序中使用的方法如下
整数N和K存储字符串的长度，否。每个中出现相邻1的时间。
函数stringcount（intn，intk）将n和k作为参数，并返回与K相邻的1的字符串数。
数组count[i][j][0/1]用于存储长度为i的字符串的计数，其中j相邻于1，以0或1结尾。
初始条件为count[1][0][0]=1；count[1][0][1]=1;
现在从2个长度的字符串（i=2）到n个长度开始。对于每个这样的字符串，请检查相邻1的K次计数。j=0;j<=k，来自先前的计数。更新当前计数[i][j][0]和计数[i][j][1]。
如果j-1>=0，则相邻1的计数大于1。然后更新以1结尾的字符串的计数为count[i][j][1]+count[i-1][j-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