数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时装研究
法律研究用 C/C++ 计算不含连续 1 的二进制字符串数量的程序？
这里我们将看到一个有趣的问题。假设给定一个 n 的值。我们必须找到所有长度为 n 的字符串，这些字符串中没有连续的 1。如果 n = 2，则数字为 {00, 01, 10}，所以输出为 3。
我们可以使用动态规划来解决它。假设我们有表“a”和“b”。其中 arr[i] 存储长度为 i 的二进制字符串的数量，其中没有连续的 1 且以 0 结尾。类似地，b 持有相同的内容，但数字以 1 结尾。当最后一个为 0 时，我们可以在它后面附加 0 或 1，但如果最后一个为 1，则只能附加 0。
让我们了解一下获取此想法的算法。
算法
noConsecutiveOnes(n) −
Begin define array a and b of size n a[0] := 1 b[0] := 1 for i in range 1 to n, do a[i] := a[i-1] + b[i - 1] b[i] := a[i - 1] done return a[n-1] + b[n-1] End
示例
#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
int a[n], b[n];
a[0] = 1;
b[0] = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
}
return a[n-1] + b[n-1];
}
int main() {
cout << noConsecutiveOnes(4) << endl;
}输出
8
更新于: 20-Aug-2019
116 次浏览
广告