数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学用 C++ 计数具有 k 次出现相邻两个设置位的二进制字符串
给定整数 N 和 K。我们有长度为 N 的二进制字符串，只包含 0 和 1。目标是找到长度为 N 的此类字符串的数量，这些字符串具有 K 个连续的 1。例如，如果 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，计数 = 0。
count[1][K][0] = count[1][K][1] = 0。
- 当最后一位数字为 0 时，使相邻 1 的计数为 K
所有长度为 N-1 且具有 K 个 1 的数字 + 最后一位 0 → 新长度 = N
如果 K 个相邻 1 的计数为 C，则在末尾添加 0 不会改变该计数。
count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]
- 当最后一位数字为 1 时，使相邻 1 的计数为 K
所有长度为 N-1 且以 0 结尾且具有 K 个 1 的数字 + 最后一位 1 → 新长度 = N，
count[N-1][K][0]
所有长度为 N-1 且以 1 结尾且具有 K-1 个 1 的数字 + 最后一位 1 → 新长度 = N，
count[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(int n, int k) 以 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 的字符串。对于每个这样的字符串，检查 K 次相邻 1 的计数。j=0；j<=k，从之前的计数中。更新当前 count[i][j][0] 和 count[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
361 次浏览
