极客笔记C++ 具有给定字符对之和频率的二进制字符串
在计算机科学和数学中，二进制字符串是由0和1组成的序列。相邻字符的和由后续字符对的和表示。例如，要理解下面的主题，在字符串”11010″中连续字符对的总数或数字是1+1=2，1+0=1和0+1=1。目标是根据这些和的频率作为指导，找到满足指定频率的二进制字符串。此问题的应用可以在信息论和编码理论等领域找到。
方法
为了找到具有给定字符对之和频率的二进制字符串，我们可以使用以下方法-
方法1：暴力搜索
方法2：回溯
方法3：动态规划
方法1：暴力搜索
一组被称为暴力搜索方法的算法通过彻底检查每个潜在的解决方案来解决问题，通常不使用优化或启发式方法。暴力搜索策略包括创建每个可能的二进制字符串，然后确定连续字符对之和的频率是否与指定的频率匹配，以获得具有所需字符对之和频率的二进制字符串。
语法
下面是使用暴力搜索方法查找具有给定字符对之和频率的二进制字符串的语法
// Initialize variables
int n = length of binary string
int freq[] = array of frequencies of sums
string result = ""
// Loop through all possible binary strings of length n
for (int i = 0; i < pow(2, n); i++) {
string binary = binary representation of i with padding of zeros to length n
// Check if the binary string satisfies the frequency constraints
int sumFreq[] = array of frequencies of sums for binary
bool valid = true
for (int j = 0; j < n - 1; j++) {
if (sumFreq[j] != freq[j]) {
valid = false
break
}
}
// If the binary string satisfies the frequency constraints, save it as result
if (valid) {
result = binary
break
}
}
// Print the result
print result
步骤：
第一步 − 生成每一个可行的长度为n的二进制字符串。
第二步 − 确定每一个二进制字符串相邻字符对之和。
第三步 − 验证这些和的频率与指定频率是否匹配。
第四步 − 如果发现匹配，则返回相应的二进制字符串。
第五步 − 如果没有发现匹配，则返回”未找到二进制字符串”。
示例1
下面是一个用C++实现的暴力方法的例子，用于找到所有长度为n且具有给定相邻字符对和频率的二进制字符串。 这个实现中的generate_binary_strings函数接受一个向量来保存结果(results)，所需的连续对和的频率(freq)，以及二进制字符串的长度(n)作为输入。它使用一个嵌套循环从0到2n-1的整数来构建所有可能的长度为n的二进制字符串。然后，它检查每个字符串是否符合指定的频率要求以及不能有两个连续的字符为1的限制。如果一个字符串符合这些要求，则将其包含在结果向量中。一个二进制字符串在一个名为main的函数中构建，然后被写入或显示在屏幕上。
#include <iostream>
#include <vector>
using namespace std;
void generate_binary_strings(int n, int freq, vector<string>& results) {
for (int i = 0; i < (1 << n); i++) {
string s(n, '0');
int count = 0;
for (int j = 0; j < n-1; j++) {
if (i & (1 << j)) {
s[j] = '1';
count++;
}
}
if (count == freq) {
bool valid = true;
for (int j = 0; j < n-1; j++) {
if (s[j] == '1' && s[j+1] == '1') {
valid = false;
break;
}
}
if (valid) {
results.push_back(s);
}
}
}
}
int main() {
int n = 4; // length of binary strings
int freq = 2; // desired frequency of sums of consecutive pairs
vector<string> results;
generate_binary_strings(n, freq, results);
cout << "Binary strings of length " << n << " with frequency " << freq << ":" << endl;
for (const auto& s : results) {
cout << s << endl;
}
return 0;
}
输出
Binary strings of length 4 with frequency 2:
1010
1010
方法2：回溯法
解决组合问题时，回溯法是一种常用的强大算法技术。找到一个具有一定频率的连续字符对的二进制字符串是其中之一。在此问题中，提供了表示二进制字符串长度和连续字符对和频率的两个整数n和k。
语法
backtrack(string s, int freq[], int n, int index)
if index == n
return true // base case: solution found
for i = 0 to 1
s[index] = i
if satisfies_constraints(s, freq, index)
if backtrack(s, freq, n, index+1)
return true // solution found
return false // backtrack
satisfies_constraints(string s, int freq[], int index)
// check if s[0:index] satisfies the given constraints
步骤
步骤1 - 从一个长度为n的空字符串开始。
步骤2 - 生成一个包含连续字符对的长度为n的二进制字符串的可行和。
步骤3 - 使用回溯，在确保每个和的频率与指定频率相对应的情况下，创建可能由0和1组成的每个二进制字符串。
步骤4 - 如果发现一个有效的二进制字符串，则返回它。
步骤5 - 如果找不到合适的二进制字符串，则返回“找不到二进制字符串”。
在最坏的情况下，该方法的时间复杂度可以达到O(2n)，取决于需要验证多少个有效的二进制字符串。
示例2
回溯函数接受一个长度为n的向量freq作为输入，表示连续字符对的和的期望频率，并且参考二进制字符串的长度为n，并包含正在构造的二进制字符串，一个表示正在构造的二进制字符串的当前位置的整数pos，以及一个表示前两个字符的和（o）的整数sum。
在示例的主函数中，我们构建一个称为freq的频率向量，并使用它来调用findBinaryStringWithFrequencies。如果发现一个有效的二进制字符串，则会将其报告给控制台。如果没有找到，则会显示一个失败通知。
#include <iostream>
#include <vector>
using namespace std;
bool backtrack(vector<int>& freq, string& binary, int pos, int sum) {
if (pos == binary.length()) {
return true;
}
for (int i = 0; i <= 1; i++) {
int new_sum = sum + (i * (pos > 0 ? binary[pos-1] - '0' : 0));
if (freq[new_sum] > 0) {
freq[new_sum]--;
binary[pos] = '0' + i;
if (backtrack(freq, binary, pos+1, new_sum)) {
return true;
}
freq[new_sum]++;
}
}
return false;
}
string findBinaryStringWithFrequencies(vector<int> freq) {
int n = freq.size();
string binary(n, '0');
if (backtrack(freq, binary, 0, 0)) {
return binary;
} else {
return "";
}
}
int main() {
vector<int> freq = {1, 2, 1, 0, 0, 1};
string binary = findBinaryStringWithFrequencies(freq);
if (binary.empty()) {
cout << "No binary string found." << endl;
} else {
cout << "Binary string: " << binary << endl;
}
return 0;
}
输出结果
No binary string found.
方法3：动态规划
动态规划是计算机科学中用来解决优化问题的一种知名方法，它通过将问题分解为较小问题，然后从这些较小问题的解构建出解决主要问题的解决方案。使用动态规划方法可以创建具有预定连续字符对频率和的二进制字符串。
语法
上述动态规划方法的伪代码如下所示-
Function finds binary string(frequencies):
N = length of binary string
k = maximum sum of consecutive pairs of characters that need to be achieved
YT[N+1] [k+1] = 0
YT [0][0] = 1
for L in interval (1, N+1):
for P in interval(k+1):
for prep in {0, 1}:
if j - prep >= 0:
YT[L][P] += YT[L-1] [P-prep]
answer = 0
for P in interval(k+1):
if frequency[P]!= -1:
answer += YT[N][P] * frequency[P]
return answer.
在上述伪代码中， frequencies 参数是一个大小为k+1的列表，其中第i个元素表示连续一对字符的和的频率等于i。如果没有给出特定和的频率，则对应的频率值将为-1。该函数返回满足给定频率约束的二进制字符串的数量。
步骤
第1步 - 创建一个有n+1个元素的dp数组，并将其初始化为0。
第2步 - 递增dp数组中每个可能的字符和的匹配项。
第3步 - 使用动态规划找到可能包含0和1混合的每个二进制字符串，确保每个和的频率对应于指定的频率。
第4步 - 如果找到一个有效的二进制字符串，则返回它。
第5步 - 如果找不到合适的二进制字符串，则返回”未找到二进制字符串”。
该方法的时间复杂度取决于需要验证的有效二进制字符串的数量，但在某些情况下，它可能比先前的技术更快。
示例3
使用动态规划处理找到具有指定连续一对字符和频率的二进制字符串的问题的示例。
在这个版本中，以长度为i的二进制字符串中包含j对连续的1和k对连续的0的二进制字符串的数量存储在一个名为dp[i][j][k]的三维DP数组中。从i = 1的基本情况开始，我们使用递推关系来计算i = 2到n的DP数组。根据这个关系，长度为i的二进制字符串中包含j对连续的1和k对连续的0的总数等于在前一步中包含j对连续的1和k对连续的0的字符串的总和(dp[i-1][j][k])。
#include<bits/stdc++.h>
using namespace std;
// Function to find the binary string
string binaryStringWithFrequencies(int n, int freq0, int freq1, int freq2) {
string ans = "";
// DP array to store the number of strings
// with a given frequency of sums
vector<vector<vector<int>>>dp(n + 1, vector<vector<int>>(freq1 + 1, vector<int>(freq2 + 1)));
// Initialize DP array for base cases
dp[1][0][0] = 1;
if(freq1 > 0) dp[1][1][0] = 1;
if(freq2 > 0) dp[1][0][1] = 1;
// Compute DP array for remaining cases
for(int i = 2; i <= n; i++) {
for(int j = 0; j <= freq1; j++) {
for(int k = 0; k <= freq2; k++) {
if(j + k > i) break; // No possible string with sum of consecutive pairs > i
dp[i][j][k] = dp[i-1][j][k];
if(j > 0) dp[i][j][k] += dp[i-1][j-1][k];
if(k > 0) dp[i][j][k] += dp[i-1][j][k-1];
}
}
}
// Trace back the DP array to find the binary string
int j = freq1, k = freq2;
for(int i = n; i >= 1; i--) {
if(j > 0 && dp[i-1][j-1][k] > 0) {
ans += '1';
j--;
}
else {
ans += '0';
k--;
}
}
// Reverse the string to get the correct order
reverse(ans.begin(), ans.end());
// Return the binary string
return ans;
}
// Driver code
int main() {
int n = 5;
int freq0 = 2, freq1 = 1, freq2 = 1;
string ans = binaryStringWithFrequencies(n, freq0, freq1, freq2);
cout << ans << endl; // Output: 00110
return 0;
}
输出
00001
结论
最后，需要注意的是，在连续字符对的和具有特定频率的二进制字符串的查找是一个难题，需要考虑到很多因素。通过使用数学方法和线性规划等算法，可以有效地解决这个问题，并生成一个合适的二进制字符串。然而，随着输入量的增加，问题的难度也会增加，可能需要大量的计算能力才能找到最佳答案。然而，可以通过使用适当的方法和工具来妥善处理这个问题，并获取所需的二进制字符串。