資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學長度為 N 的二進位制字串中，由子串重複連線構成的字串數量
本文旨在實現一個程式，用於計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量。
目標是確定，給定一個正整數 N，有多少個長度為 N 的二進位制字串可以透過重複連線給定文字的單個子串來建立。
問題陳述
實現一個程式，用於計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量。
示例 1
Let us take the Input, N = 3
Output: 2
解釋
以下是長度 N=3 的可行二進位制字串，它們是由子串重複連線構成的。
"000":The substring "0" is repeatedly concatenated to form this string. "111":The substring "1" is repeatedly concatenated to form this string.
因此，當我們計算所有這些字串的總數時，得到的結果是 2。因此，輸出為 2。
示例 2
Let us take the Input, N = 8
Output: 16
解釋
以下是長度 N=8 的可行二進位制字串，它們是由子串重複連線構成的。
“00000000”: The substring "0" is repeatedly concatenated to form this string. “11111111”: The substring "1" is repeatedly concatenated to form this string. “01010101”: The substring "01" is repeatedly concatenated to form this string. “10101010”: The substring "10" is repeatedly concatenated to form this string. "00110011”: The substring "0011" is repeatedly concatenated to form this string. "11001100”: The substring "1100" is repeatedly concatenated to form this string. "11011101”: The substring "1101" is repeatedly concatenated to form this string. "00100010”: The substring "0010" is repeatedly concatenated to form this string. "10111011”: The substring "1011" is repeatedly concatenated to form this string. "01000100”: The substring "0100" is repeatedly concatenated to form this string. "10001000”: The substring "1000" is repeatedly concatenated to form this string. "00010001”: The substring "0001" is repeatedly concatenated to form this string. "11101110”: The substring "1110" is repeatedly concatenated to form this string. "01110111”: The substring "0111" is repeatedly concatenated to form this string. "01100110”: The substring "0110" is repeatedly concatenated to form this string. "10011001”: The substring "1001" is repeatedly concatenated to form this string.
因此，當我們計算所有這些字串的總數時，得到的結果是 16。因此，輸出為 16。
方法
為了計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量，我們採用以下方法。
解決這個問題並計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量的方法。
上述問題可以基於這樣一個事實來解決：每個可行字串都包含一個重複的子串，假設重複 C 次。因此，提供的字串長度 N 需要能夠被 C 整除，才能生成所有後續的字串。
因此，找到 N 的所有約數，然後對於每個可能的約數 C，找到可以透過連線它們建立的所有可能字串的總數；這個數字可以使用 2C 來確定。為了確定每個遞迴呼叫的總數，對約數 C 應用同樣的方法，然後從 2C 中減去它。這也會考慮到它們之間重複字串的數量。
演算法
以下是計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量的演算法。
步驟 1 − 開始
步驟 2 − 定義一個函式來計算長度為 N 的字串的數量，該字串是其子串的連線。
步驟 3 − 檢查狀態是否已經被計算過。
步驟 4 − 儲存當前遞迴呼叫的結果或計數的值。
步驟 5 − 遍歷所有約數。
步驟 6 − 返回獲得的結果。
步驟 7 − 結束
示例：C++程式
以下是上述演算法的 C++ 程式實現，用於計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量。
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Storing all the states of recurring recursive
map<int, int> dp;
// Function for counting the number of strings of length n wherein thatstring is a concatenation of its substrings
int countTheStrings(int n){
//the single character cannot be repeated
if (n == 1)
return 0;
// Checking whether the state is calculated already or not
if (dp.find(n) != dp.end())
return dp[n];
// Storing those value of the result or the count for the present recursive call
int res = 0;
// Iterate through all of the divisors
for(int d= 1; d <= sqrt(n); d++){
if (n % d== 0){
res += (1 << d) - countTheStrings(d);
int div1 = n/d;
if (div1 != d and d!= 1)
// Non-Rep = Total - Rep
res += (1 << div1) - countTheStrings(div1);
}
}
// Storing the result of the above calculations
dp[n] = res;
// Returning the obtained result
return res;
}
int main(){
int n = 8;
cout<< "Count of 8-length binary strings that are repeated concatenation of a substring: "<< endl;
cout << countTheStrings(n) << endl;
}
輸出
Count of 8-length binary strings that are repeated concatenation of a substring − 16
結論
同樣，我們可以計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量。
本文解決了獲取長度為 N 的二進位制字串中，由子串重複連線構成的字串數量的挑戰。
這裡提供了 C++ 程式設計程式碼以及計算長度為 N 的二進位制字串中，由子串重複連線構成的字串數量的演算法。
94 次瀏覽
