数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C/C++程序：统计没有连续1的二进制字符串数量？
二进制数只包含0和1。每个二进制数都是一串二进制位，我们将其视为二进制字符串。对于此字符串，我们需要找到长度为N位且不包含连续1的二进制字符串的数量。
例如，对于N=5，满足给定约束条件的二进制字符串为：00000、00001、00010、00100、00101、01000、01001、01010、10000、10001、10010、10100、10101
一种方法是生成所有N位字符串，并只打印满足给定约束条件的字符串。但是，这种方法在实际应用中效率不高。
另一种方法是使用递归。在递归的每个点，我们将0和1附加到部分形成的数字，并使用少一位的数字进行递归。这里的技巧是，只有当部分形成的数字的最后一位是0时，我们才附加1并进行递归。这样，输出字符串中将永远不会出现连续的1。
Input: n = 5 Output: Number of 5-digit binary strings without any consecutive 1's are 13
示例
#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
if (n == 0)
return 0;
if (n == 1) {
if (last_digit)
return 1;
else
return 2;
}
if (last_digit == 0)
return countStrings(n - 1, 0) + countStrings(n - 1, 1);
else
return countStrings(n - 1, 0);
}
int main() {
int n = 5;
cout << "Number of " << n << "-digit binary strings without any "
"consecutive 1's are " << countStrings(n, 0);
return 0;
}
更新于：2019年8月19日
浏览量：226
广告