資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告