Le plus petit nombre pouvant être obtenu en appliquant les opérations '+' et '*' aux éléments du tableau

Énoncé du problème

On nous donne un tableau de longueur "N" contenant des entiers positifs. De plus, nous recevons une chaîne de longueur "N-1", contenant uniquement les caractères "*" et "+", où "*" est l'opérateur de multiplication et "+" est l'opérateur d'addition. On nous demande d'effectuer une opération arithmétique sur les éléments du tableau pour obtenir la plus petite valeur entière positive.

Exemple

Entrez

array = [1,2,3], str = “*+”

Sortie

5

Instructions

C'est la valeur du résultat de ((1*2) + 3).

Entrez

array = [3, 3, 3, 3], str = ‘*++’

Sortie

15

Instructions

Il fait array[0]*array[1], qui est égal à 9, et représente le résultat 1. Après cela, il ajoute result1 au tableau[2], égal à 12, et le représente comme result2. Ensuite, il ajoute result2 au tableau [3], égal à 15.

Entrez

array =  [1, 3, 5, 6], str = “**+”

Sortie

21

Instructions

C'est la valeur du résultat de ((1*3*5) + 6).

Méthode 1

Nous utiliserons le masquage de bits pour résoudre le problème dans cette méthode.

Chaque fois que nous avons deux choix, nous pouvons utiliser des masques. Ici, nous demandons d'appliquer des opérations arithmétiques dans n'importe quel ordre mais nous devons choisir entre des opérations de multiplication et des opérations arithmétiques pour une chaîne donnée

Ainsi, les masques de bits nous permettent d'obtenir toutes les manières possibles d'arranger deux opérateurs arithmétiques. Ensuite, nous pouvons effectuer des opérations arithmétiques dans chaque sens et vérifier si le résultat est la valeur minimale.

Explicitons la logique ci-dessus avec un exemple de saisie. Dans l'exemple ci-dessous, array = [1. 3, 5, 6], string = "*++".

Ici, la longueur de la chaîne est de 3. Par conséquent, nous pouvons avoir un total de 8 (2 ^ 3) masques de bits, à savoir 000, 001, 010, 100, 110, 101, 011, 111.

Maintenant, si nous supposons que "1" est "*" et "0" est l'opérateur "+", nous pouvons obtenir toutes les permutations des opérateurs arithmétiques données dans la chaîne.

Cependant, nous ne devons utiliser aucune permutation uniquement si le nombre total de « 1 » est égal au nombre d’opérateurs « * » et que le nombre de « 0 » est égal au nombre d’opérateurs « + ».

Algorithme

Les utilisateurs doivent suivre l'algorithme suivant pour implémenter la méthode ci-dessus.

• Étape 1 - Définissez la variable "totalMul" et initialisez-la à zéro pour stocker le nombre total d'opérateurs arithmétiques multiplicatifs dans la chaîne.

• Étape 2 - Parcourez la chaîne donnée à l'aide d'une boucle for. Si le caractère courant est égal à "*", la valeur de la variable "totalMul" est augmentée de 1.

• Étape 3 - Utilisez une boucle for pour obtenir tous les masques de bits possibles lorsque X est égal à la longueur de la chaîne. Ici, « len » est la longueur du tableau et « len - 1 » est la longueur de la chaîne.

• Étape 4 - Définissez la variable "setBitCount" pour stocker le nombre de bits définis dans le masque actuel. De plus, définissez une liste « ordre » pour stocker l'ordre actuel des opérations arithmétiques.

• Étape 5 - Dans la boucle for, utilisez une autre boucle for pour obtenir le nombre total de bits définis (« 1 ») dans le masque actuel. Décalez j vers la gauche de 1 bit, effectuez & opération avec I pour déterminer si le j-ième bit est défini.

• Étape 6 - Si le bit actuel est un bit défini, augmentez la valeur de la variable "setBitCount" et poussez "*" dans le vecteur de séquence ; sinon, poussez "+" dans le vecteur de séquence.

• Étape 7 - Si la valeur de setBitCount est égale à la valeur de totalMul, cela signifie que nous pouvons planifier l'opération arithmétique en utilisant le masque actuel, sinon nous passerons à l'itération suivante ;

• Étape 8 - Dans l'instruction if, définissez un "currentQueue" en utilisant la structure de données "deque" pour stocker les éléments du tableau.

• Étape 9 - Parcourez la liste « commande ». Si le caractère actuel est '*', insérez le dernier élément de la file d'attente et multipliez-le par l'élément à l'index actuel du tableau.

• Étape 10 - Si le caractère actuel dans la liste « commandes » est « + », poussez l'élément actuel du tableau dans la « file d'attente actuelle ».

• Étape 11 - Utilisez une boucle while pour extraire tous les éléments de "currentQueue" et additionner tous les éléments.

• Étape 12 - Obtenez la valeur minimale des variables "minimum" et "somme" à l'aide de la fonction min().

Exemple

#include <bits/stdc++.h>
using namespace std;

// Function to get the minimum number by applying mathematical operations in any order.
int getMinimumSum(int array[], int len, string str){
   // to store a total number of multiplication operators in the string.
   int totalMul = 0;
   for (int i = 0; i < (int)str.size(); i++){
      // increment totalMul if the current character is '*'
      if (str[i] == '*')
         totalMul += 1;
      }
   // store maximum number value in the result.
   int minimum = 1000000;
   // Iterate over all the possible masks and find the minimum value by applying arithmetic operations.
   for (int i = 0; i < (1 << (len - 1)); i++){
      // to store the number of bits set in the mask.
      int setBitCount = 0;
      // to store the order of the operators.
      vector<char> order;
      // finding a total number of mask bits in the current mask 'i'. If the current bit is set to bit, push '*' in the order vector; else, push '+'.
      for (int j = 0; j < len - 1; j++){
         if ((1 << j) & (i)){
            setBitCount += 1;
            order.push_back('*');
         } else {
            order.push_back('+');
         }
      }
      // if the set bit count is equal to the total number of multiplication operators, then only apply the operations.
      if (setBitCount == totalMul){
         // queue to store the current elements.
         deque<int> currentQueue;
         // push the first element in the queue.
         currentQueue.push_back(array[0]);
         for (int j = 0; j < len - 1; j++) {
            // get the current operator from the order vector.
            if (order[j] == '*'){
               // if the current operator is '*', multiply the last element in the queue with the next element in the array.
               int temp = currentQueue.back();
               currentQueue.pop_back();
               temp = temp * array[j + 1];
               // push a new value
               currentQueue.push_back(temp);
            } else {
               // if current operator is '+', then push the next element in the array in the queue.
               currentQueue.push_back(array[j + 1]);
            }
         }
         int sum = 0;
         // Add all the elements in the queue.
         while (currentQueue.size() > 0){
            int temp = currentQueue.front();
            sum += temp;
            currentQueue.pop_front();
         }
         // get the minimum value.
         minimum = min(minimum, sum);
      }
   }
   return minimum;
}

int main(){
   int array[] = {1, 3, 5, 6};
   string str = "*++";
   int len = sizeof(array) / sizeof(array[0]);
   cout << "Minimum number value can be achieved is : " << getMinimumSum(array, len, str);
   return 0;
}

Sortie

Minimum number value can be achieved is : 14

• Complexité temporelle - O(2N-1*N), où N est la longueur du tableau. Lorsque nous parcourons tous les masques de bits, où nous utilisons une boucle for pour compter le nombre total de bits définis dans le masque actuel, c'est O(2N-1*N).

• Complexité spatiale − O(N) car nous utilisons une liste pour stocker l'ordre des opérateurs arithmétiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!