本文的目的是實作一個程序,用於計算由一個子字串重複連接而成的長度為N的二進位字串的數量。
目標是確定透過重複連接給定文字的單一子字串,可以建立多少長度為N的二進位字串,其中N是一個正整數。
實作一個程序,用於計算重複連接子字串的長度為N的二進位字串的數量。
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。
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的二進位字串的演算法。
第一步 − 開始
第二步 − 定義一個函數來計算長度為N的字串的數量,使其是其子字串的連接。
第三步 - 檢查狀態是否已計算
第4步 - 儲存目前遞歸呼叫的結果或計數的值
步驟 5 - 迭代所有除數
第6步 - 傳回所得的結果
第7步 − 停止
這是上述演算法的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長度二進位字串的演算法。
以上是計算長度為N的二進位字串,它們是子字串的重複拼接的詳細內容。更多資訊請關注PHP中文網其他相關文章!