Nombor terkecil yang boleh diperoleh dengan menggunakan operasi "+" dan "*" pada elemen tatasusunan

Pernyataan Masalah

Kami diberi tatasusunan panjang "N" yang mengandungi beberapa integer positif. Selain itu, kami diberi rentetan panjang "N-1", mengandungi hanya aksara "*" dan "+", dengan "*" ialah pengendali pendaraban dan "+" ialah pengendali penambahan. Kami diminta untuk melakukan operasi aritmetik pada elemen tatasusunan untuk mendapatkan nilai integer positif terkecil.

Contoh

Masuk

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

Output

5

Arahan

Ia adalah nilai hasil ((1*2) + 3).

Masuk

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

Output

15

Arahan

Ia melakukan tatasusunan[0]*susunan[1], yang bersamaan dengan 9, dan mewakili hasil 1. Selepas itu, ia menambah result1 kepada tatasusunan[2], bersamaan dengan 12, dan mewakilinya sebagai result2. Seterusnya, ia menambah result2 pada tatasusunan [3], bersamaan dengan 15.

Masuk

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

Output

21

Arahan

Ia ialah nilai hasil ((1*3*5) + 6).

Kaedah 1

Kami akan menggunakan bit masking untuk menyelesaikan masalah dalam kaedah ini.

Setiap kali kita mempunyai dua pilihan, kita boleh menggunakan topeng bit. Di sini kami meminta untuk menggunakan operasi aritmetik dalam sebarang susunan tetapi kami perlu memilih antara operasi pendaraban dan aritmetik untuk rentetan tertentu

Oleh itu, topeng bit membolehkan kami memperoleh semua cara yang mungkin untuk mengatur dua operator aritmetik. Selepas itu, kita boleh melakukan operasi aritmetik pada setiap cara dan menyemak sama ada hasilnya adalah nilai minimum.

Mari kita jelaskan logik di atas dengan input contoh. Dalam contoh di bawah, tatasusunan = [1, 5, 6], rentetan = "*++".

Di sini, panjang tali ialah 3. Oleh itu, kita boleh mempunyai sejumlah 8 (2^3) bit mask, iaitu 000, 001, 010, 100, 110, 101, 011, 111.

Sekarang, jika kita menganggap "1" ialah "*" dan "0" ialah operator "+", kita boleh mendapatkan semua pilih atur pengendali aritmetik yang diberikan dalam rentetan.

Walau bagaimanapun, kita harus menggunakan sebarang pilihatur hanya jika jumlah bilangan "1" adalah sama dengan bilangan operator "*", dan bilangan "0" adalah sama dengan bilangan operator "+".

Algoritma

Pengguna harus mengikut algoritma berikut untuk melaksanakan kaedah di atas.

• Langkah 1 - Takrifkan pembolehubah "totalMul" dan mulakannya kepada sifar untuk menyimpan jumlah bilangan operator aritmetik darab dalam rentetan.

• Langkah 2 - Ulangi rentetan yang diberikan menggunakan gelung for. Jika aksara semasa bersamaan dengan "*", nilai pembolehubah "totalMul" dinaikkan sebanyak 1.

• Langkah 3 - Gunakan gelung for untuk mendapatkan semua bitmasks yang mungkin apabila X sama dengan panjang rentetan. Di sini, 'len' ialah panjang tatasusunan dan 'len - 1' ialah panjang rentetan.

• Langkah 4 - Tentukan pembolehubah "setBitCount" untuk menyimpan bilangan bit yang ditetapkan dalam topeng semasa. Selain itu, senarai "tertib" ditakrifkan untuk menyimpan susunan semasa operasi aritmetik.

• Langkah 5 - Dalam gelung for, gunakan gelung for yang lain untuk mendapatkan jumlah bilangan bit set (‘1’) dalam topeng semasa. Alihkan j ke kiri sebanyak 1 bit, lakukan & operasi dengan I, dan tentukan sama ada bit ke-j ditetapkan.

• Langkah 6 - Jika bit semasa ialah bit set, tingkatkan nilai pembolehubah "setBitCount" dan tolak "*" ke dalam vektor jujukan, jika tidak, tolak "+" ke dalam vektor jujukan.

• Langkah 7 - Jika nilai setBitCount adalah sama dengan nilai totalMul, ini bermakna kita boleh menjadualkan operasi aritmetik menggunakan topeng semasa jika tidak, kita akan beralih ke lelaran seterusnya.

• Langkah 8 - Dalam pernyataan if, takrifkan "currentQueue" menggunakan struktur data "deque" untuk menyimpan elemen tatasusunan.

• Langkah 9 - Ulang melalui senarai 'pesanan'. Jika aksara semasa ialah '*', pop elemen terakhir dalam baris gilir dan darabkannya dengan elemen pada indeks tatasusunan semasa.

• Langkah 10 - Jika aksara semasa dalam senarai "pesanan" ialah "+", tolak elemen tatasusunan semasa ke dalam "currentQueue".

• Langkah 11 - Gunakan gelung sementara untuk mengeluarkan semua elemen daripada "currentQueue" dan jumlah semua elemen.

• Langkah 12 - Dapatkan nilai minimum daripada pembolehubah "minimum" dan "jumlah" menggunakan fungsi min().

Contoh

#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;
}

Output

Minimum number value can be achieved is : 14

• Kerumitan masa - O(2N-1*N), dengan N ialah panjang tatasusunan. Apabila kita mengulangi semua topeng bit, di mana kita menggunakan gelung for untuk mengira jumlah bilangan bit yang ditetapkan dalam topeng semasa, ia adalah O(2N-1*N).

• Kerumitan ruang − O(N) kerana kami menggunakan senarai untuk menyimpan susunan pengendali aritmetik.

Atas ialah kandungan terperinci Nombor terkecil yang boleh diperoleh dengan menggunakan operasi "+" dan "*" pada elemen tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!