資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學用 C++ 計數具有 k 次出現相鄰兩個設定位的二進位制字串
給定整數 N 和 K。我們有長度為 N 的二進位制字串，只包含 0 和 1。目標是找到長度為 N 的此類字串的數量，這些字串具有 K 個連續的 1。例如，如果 N=3，K=2，則計算所有可能的具有 2 個連續 1 的 3 位二進位制字串。
示例 - 111，這裡相鄰的 1 出現了兩次（K 次）。
在 011 和 110 中，相鄰的 1 只出現一次。
我們將透過儲存先前值的結果來解決這個問題。
使用 3D 陣列 count[x][y][z]。其中 x 是 N，y 是 K，z 是字串的最後一位數字（0 或 1）
- 對於 N=1，字串將是“0”和“1”。相鄰 1 的計數 = 0。
因此，對於任何 K，如果 N=1，計數 = 0。
count[1][K][0] = count[1][K][1] = 0。
- 當最後一位數字為 0 時，使相鄰 1 的計數為 K
所有長度為 N-1 且具有 K 個 1 的數字 + 最後一位 0 → 新長度 = N
如果 K 個相鄰 1 的計數為 C，則在末尾新增 0 不會改變該計數。
count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]
- 當最後一位數字為 1 時，使相鄰 1 的計數為 K
所有長度為 N-1 且以 0 結尾且具有 K 個 1 的數字 + 最後一位 1 → 新長度 = N，
count[N-1][K][0]
所有長度為 N-1 且以 1 結尾且具有 K-1 個 1 的數字 + 最後一位 1 → 新長度 = N，
count[N-1][K-1][1]
count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1]
此類字串的總數 = count[N][K][0] + count[N][K][1]
輸入
N=4, K=2
輸出
Count of strings: 2
解釋 - 1110、0111 是長度為 4 的唯一字串，其中相鄰的 1 只出現兩次。
1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times
輸入
N=3, K=1
輸出
Count of strings: 2
解釋 - 110、011 是長度為 3 的唯一字串，其中相鄰的 1 出現一次。
在 111 中，相鄰的 1 出現兩次。
下面程式中使用的方案如下
整數 N 和 K 儲存字串的長度和每個字串中相鄰 1 出現的次數。
函式 stringcount(int n, int k) 以 n 和 k 為引數，並返回具有 K 次相鄰 1 的字串的計數。
陣列 count[i][j][0/1] 用於儲存長度為 i、具有 j 個相鄰 1 並以 0 或 1 結尾的字串的計數。
初始條件是 count[1][0][0] = 1；count[1][0][1] = 1；
現在從長度為 2 的字串 (i=2) 開始到長度為 n 的字串。對於每個這樣的字串，檢查 K 次相鄰 1 的計數。j=0；j<=k，從之前的計數中。更新當前 count[i][j][0] 和 count[i][j][1]。
如果 j-1>=0，則相鄰 1 的計數大於 1。然後更新以 1 結尾的字串的計數為 count[i][j][1] + count[i - 1][j - 1][1]；
最後，新增 count[n][k][0] 和 count[n][k][1]。將其儲存為結果。
- 將結果作為所需計數返回。
示例
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
//count of strings with length=n and adajcent 1's=k
int count[n + 1][k + 1][2]={0};
//count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
//count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
// If n = 1 and k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// number of adjacent 1's can not exceed i-1
for (int j = 0; j <= k; j++) {
count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
count[i][j][1] = count[i - 1][j][0];
if (j - 1 >= 0)
count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1];
}
}
int result=count[n][k][0]+count[n][k][1];
return result;
}
int main(){
int N = 6, K = 3;
cout <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
return 0;
}輸出
Strings of length 6 and 3 adjacent 1's in each :7
361 次瀏覽
