資料結構
網路
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
廣告