C++ 使每个字符的频率为素数所需的最小字符添加/删除

优化字符频率以使其成为素数是计算机科学中的一项具有挑战性的任务，它涉及确定每个字符串中每个字符的频率所需的最小字符添加或删除。密码学、数据压缩和自然语言处理仅是此问题的一些应用。本教程将使用C++方法优化字符串中字符的素数性。我们将首先详细介绍问题描述，然后提出一种高效的解决方案。

方法

动态规划方法
minOperations函数方法

方法1：动态规划方法

为了解决优化字符频率以使其成为素数的问题，我们必须确定在提供的字符串中使每个字符的频率成为素数所需的最短字符添加或删除的数量。

一种解决方法：

找出每个字符在提供的字符串中出现的次数。
检查每个字符的频率是否为素数。如果数字不是素数，则找到最接近当前频率的大于或等于当前频率的素数。如果当前字符频率已经是素数，则继续处理。
估计每个字符需要达到素数位置的调整次数。这可以通过将最接近的素数减去原始频率（或者相反，取决于原始频率是高于还是低于最近的素数）来实现。
将所有字符的添加和删除操作相加以获得结果。

语法

为了确定在给定字符串中需要添加或删除多少个字符，使得每个字符的频率成为素数，以下是一个不包含实际代码的C++语法示例：

步骤1 - 计算每个字符串字符的频率。

// Function to determine the minimum number of character additions/removals
// required to make the frequency of each character in a string a prime number
int optimizeCharacterFrequency(string s) {
   map<char, int> freq;
   for (char c : s) {
      freq[c]++;
}

步骤2 - 确定需要增添/删除的最低限度。

// to make each frequency a prime number
int minAdditionsOrRemovals = 0;
for (auto [c, f] : freq) {
   // Check if the frequency is already a prime number
   if (isPrime(f)) {
      continue;
   }

   // Find the nearest prime number to the frequency
   int nearestPrime = findNearestPrime(f);

   // Determine the number of additions or removals required
   minAdditionsOrRemovals += abs(f - nearestPrime);
}

步骤3 - 返回所需的最低限度的添加/删除。

return minAdditionsOrRemovals;
}

请注意，这只是一个示例语法，并不是一个全面或可行的解决方案。实际实现需要定义isPrime和findNearestPrime方法，并适当处理边缘情况。

步骤

一种用于查找使给定字符串中每个字符的频率成为素数所需的最小添加或删除次数的算法-

第1步 -创建一个映射以跟踪给定字符串中每个字符的频率。
第2步 -检查映射中每个字符的频率是否为素数。如果不是素数，则找到最接近的素数并从当前频率中减去。
第3步 -将步骤2中找到的差异添加到映射中的所有字符，以获取使每个字符的频率成为素数所需的最小添加或删除次数。

示例1

提供的代码包含两个函数，第一个函数名为”is prime”，确定给定的输入整数是否为素数。第二个函数名为”min change”，接受一个字符串，并输出使字符串中每个字符频率成为素数所需的最小字符添加或删除次数。

当分析”min change”函数时，可以看到有一个称为”freq”的向量，它跟踪给定输入字符串中每个字符的频率。所有这些i值的总和是所需更改的最小次数。

在 main 函数中，我们对示例输入字符串测试 min changes 函数，并将结果打印到控制台。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

bool is_prime(int n) {
   if (n <= 1) {
      return false;
   }
   for (int i = 2; i <= sqrt(n); ++i) {
      if (n % i == 0) {
         return false;
      }
   }
   return true;
}

int min_changes(string s) {
   vector<int> freq(26, 0);
   for (char c : s) {
      ++freq[c - 'a'];
   }

   int sum = 0;
   for (int f : freq) {
      if (is_prime(f)) {
         continue;
   }
   int i = 1;
   while (!is_prime(f + i)) {
      ++i;
   }
   sum += i;
   }

   return sum;
   }

int main() {
   string s = "abbcccddddeeeeeffffff";
   cout << "Minimum changes required: " << min_changes(s) << endl;
   return 0;
}

输出

Minimum changes required: 43

方法2：minOperations函数方法

在这个示例中，通过使用minOperations函数确定的最少的加法和减法运算，字符串s中的每个字符将具有素数频率。该函数通过使用一个整数向量来计算s中每个字符的频率。然后，通过重复遍历频率，确定使得每个频率成为素数所需的最少的加法和减法。这个素数函数用于确定给定的数字是否是素数。然后，通过反复迭代所有大于该频率的整数，找到最接近给定频率的素数。

minOperations函数用于检查使每个字符成为素数所需的最少的加法和减法，它从主函数接收一个示例字符串s并使用它来计算必须执行的操作数。随后输出的控制台打印结果。

示例2

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// Function to check if a number is prime
bool isPrime(int n) {
   if (n <= 1)
   return false;
   for (int i = 2; i <= sqrt(n); i++) {
      if (n % i == 0)
      return false;
   }
   return true;
}

int minOperations(string s) {
   // Calculate the frequency of each character in the string
   vector<int> freq(26, 0);
   for (char c : s)
   freq[c - 'a']++;

   // Find the minimum number of additions and removals required
   int add = 0, remove = 0;
   for (int f : freq) {
      if (isPrime(f))
         continue;
      if (f < 2) {
         add++;
         continue;
      }
      // Find the nearest prime number to f
      int nextPrime = f + 1;
      while (!isPrime(nextPrime))
         nextPrime++;
      add += nextPrime - f;
      remove += f - 2;
   }
   return min(add, remove);
}

int main() {
   string s = "abbcccdddd";
   cout <<"Minimum number of add/removals are:"<< minOperations(s) << endl;   // Output: 2 (add 'e' twice)
   return 0;
}