数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 C++ 查找长度为 N 的至少包含 3 个连续 1 的二进制字符串的数量
假设我们有一个整数 N，我们需要找到长度为 N 的所有可能的不同二进制字符串的数量，这些字符串至少包含三个连续的 1。例如，如果 n = 4，则这些数字将是 0111、1110、1111，因此输出将是 3。
为了解决这个问题，我们可以使用动态规划方法。因此，DP(i, x) 表示长度为 i 的字符串的数量，在位置 i + 1 到 i + x 处有 x 个连续的 1。
DP(i, x) = DP(i – 1, 0) + DP(i – 1, x + 1)。
该递推关系基于这样一个事实：第 i 个位置可以是 0 或 1。
- 如果第 i 位是 0，则对于第 (i – 1) 位，x 的值为 0。
- 如果第 i 位是 1，则对于第 (i – 1) 位，x 的值为 1 加上第 i 位 x 的值。
示例
#include<iostream>
using namespace std;
int n;
int numberCount(int i, int x, int table[][4]) {
if (i < 0)
return x == 3;
if (table[i][x] != -1)
return table[i][x];
table[i][x] = numberCount(i - 1, 0, table);
table[i][x] += numberCount(i - 1, x + 1, table);
return table[i][x];
}
int main() {
n = 4;
int table[n][4];
for (int i = 0; i < n; i++)
for (int j = 0; j < 4; j++)
table[i][j] = -1;
for (int i = 0; i < n; i++) {
table[i][3] = (1 << (i + 1));
}
cout << "The number of binary strings with at least 3 consecutive 1s: " << numberCount(n - 1, 0, table);
}输出
The number of binary strings with at least 3 consecutive 1s: 3
更新于：2019-12-19
299 次浏览
广告