C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で配列を削除するために必要な最小限の操作


説明

Nの配列が与えられた Nが偶数である整数。アレイで許可される操作には2種類あります。

  • 配列の任意の要素の値を1増やします。
  • 配列内の2つの隣接する要素が連続する素数である場合は、両方の要素を削除します。

タスクは、配列のすべての要素を削除するために必要な操作の最小数を見つけることです。

配列が{10、13}の場合、最低2つの操作が必要です

  • インクリメント1 st 配列の要素を1ずつ増やします。したがって、新しい配列は{11、13}になります
  • 1番目の st を削除します および2 nd 両方とも連続する素数であるため、要素

アルゴリズム

1. To remove numbers, we must transform two numbers to two consecutive primes.
2. Let us suppose a and b are the consecutive prime numbers then we use sieve of Eratosthenes to precompute prime numbers and then find the first prime p not greater than a and the first greater than p using array
3. Once this computation is done use dynamic programming to solve the problem

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
   string start = "";
   string destination = "", t, r;
   for (int i = 0; i < n; i++) {
      start += to_string(a[i]);
   }
   sort(a, a + n);
   for (int i = 0; i < n; i++) {
      destination += to_string(a[i]);
   }
   queue<pair<string, int> > qu;
   pair<string, int> p;
   qu.push(make_pair(start, 0));
   if (start == destination) {
      return 0;
   }
   while (!qu.empty()) {
      p = qu.front();
      t = p.first;
      qu.pop();
      for (int j = 2; j <= n; j++) {
         r = t;
         reverse(r.begin(), r.begin() + j);
         if (r == destination) {
            return p.second + 1;
         }
         qu.push(make_pair(r, p.second + 1));
      }
   }
}
int main() {
   int a[] = { 1, 2, 4, 3 };
   int n = sizeof(a) / sizeof(a[0]);
   cout << "Minimum reversal: " <<
   minimumPrefixReversals(a, n) << endl;
   return 0;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します:

出力

Minimum reversal: 3

  1. C++で互いに素な配列を作成するための最小限の挿入

    このセクションでは、別の興味深い問題が発生します。 N個の要素の配列があるとします。この配列を互いに素な配列にするためには、交点の最小数を見つける必要があります。互いに素な配列では、2つの連続する要素ごとのgcdは1です。配列も印刷する必要があります。 {5、10、20}のような要素があるとします。これは互いに素な配列ではありません。ここで、5、10、10、20の間に1を挿入すると、互いに素な配列になります。したがって、配列は{5、1、10、1、20}のようになります。 アルゴリズム makeCoPrime(arr, n): begin    count := 0 &nb

  2. C++で配列のすべての要素を同じにするための最小限の削除操作。

    問題の説明 要素が繰り返されるようなn個の要素の配列が与えられます。配列から任意の数の要素を削除できます。タスクは、配列から削除する要素の最小数を見つけて、配列を等しくすることです。 arr[] = {10, 8, 10, 7, 10, -1, -4, 12} すべての配列要素を同じにするには、強調表示された5つの要素を削除する必要があります。 アルゴリズム 1. Count frequency of each element 2. Find maximum frequecy among the frequencies. Let us call this as maxFrequncy 3.