Menggunakan aksara yang diberikan, kira bilangan rentetan panjang 3 yang mengandungi sekurang-kurangnya 2 aksara berbeza

Beri kami tiga integer "a", "b" dan "c", mewakili tiga aksara berbeza "A", "B" dan "C" kekerapan kejadian . Kita perlu mencari bilangan rentetan berbeza yang boleh dibentuk menggunakan aksara ini, dan sekurang-kurangnya dua aksara berbeza mesti ada dalam rentetan yang terbentuk. Kita akan melihat dua cara untuk menyelesaikan masalah ini, satu adalah naif dan satu lagi adalah matematik.

Contoh

Input 1: a = 3, b = 2, c = 4 

Output:  3 

Penerangan

Kita boleh mencipta tiga rentetan "ABC", "ABC" dan "ACC". Kami menggunakan 'A' 3 kali, 'B' 2 kali dan 'C' 4 kali dalam rentetan ini, iaitu kekerapan yang sama atau kurang daripada yang diberikan dan semua rentetan mengandungi sekurang-kurangnya 2 aksara berbeza . p>

Input 2: a = 1, b = 3, c = 10

Output: 4

Penerangan

Kita boleh mencipta rentetan "ACC", "BCC", "BCC" dan "BCC". Kami telah menggunakan semua aksara yang diberikan kecuali dua "C", kerana tiada aksara lain untuk mencipta rentetan baharu. Jika kami telah mencuba kombinasi lain, bilangan akhir rentetan akan menjadi kurang.

kaedah tidak bersalah

Cara paling mudah ialah mencari semua kemungkinan gabungan frekuensi tertentu, tetapi masalahnya ialah ini mengambil banyak kerumitan masa dan sangat tidak cekap.

Kami perlu menjana semua subrentetan yang mungkin, dan jika bilangan kami besar, ia akan mengambil banyak masa dan ruang yang tidak dapat dikendalikan oleh komputer.

KAEDAH MATEMATIK

IDEA

Idea di sebalik pendekatan ini ialah kita memerlukan sekurang-kurangnya dua aksara yang berbeza dalam rentetan, jadi kami akan sentiasa cuba memfokus pada watak yang paling kerap.

Bilangan maksimum rentetan yang boleh kita buat ialah (a+b+c)/3, dan nombor yang mungkin hanya bergantung pada kekerapan kejadian sekurang-kurangnya dua.

Andaikan, jika sekurang-kurangnya dua frekuensi ialah x dan y, maka jumlahnya lebih besar daripada atau sama dengan (a+b+c)/3 maka kita boleh mencetak nilai ini sebagai jawapan, jika tidak, jumlah x dan y adalah Jawapan.

pelaksanaan

Kami telah melihat contoh dan idea untuk mencari penyelesaian, sekarang mari kita mula melaksanakan kod -

• Pertama, kami akan mencipta fungsi yang menerima tiga integer dan mengembalikan integer.

• Dalam fungsi, kami mula-mula menyimpan semua integer dalam vektor dan kemudian mengisih vektor untuk mendapatkan integer kekerapan minimum.

• Kami akan mendapat jumlah semua elemen yang diberikan dan kemudian bahagikan dengan 3 untuk mendapatkan bilangan maksimum rentetan yang boleh kami buat.

• Kemudian, kita akan membandingkan nilai rentetan terbesar dengan nilai jumlah terkecil dua frekuensi. Jika jumlahnya lebih kecil, maka kami mengemas kini rentetan maksimum menjadi jumlah sekurang-kurangnya dua elemen frekuensi.

• Akhir sekali, kami akan mengembalikan nilai rentetan terbesar yang mungkin dan mencetaknya dalam fungsi utama.

Contoh

#include <bits/stdc++.h>
using namespace std;
int count(int a, int b, int c){
   // storing the values in the vector 
   vector<int>temp(3);
   temp[0] = a;
   temp[1] = b;
   temp[2] = c; 
   
   // sorting the vector to get the minimum two elements 
   sort(temp.begin(), temp.end());
   
   // counting the sum of all the elements 
   int maxStrings = (a+b+c)/3;    
   if(temp[0] + temp[1] < maxStrings){
      maxStrings = temp[0] + temp[1];
   }    
   return maxStrings; // returning the final answer
}
int main(){

   // given numbers 
   int a = 3;
   int b = 2;
   int c = 4;
   cout<<"The count of 3 length strings using given characters containing at least 2 different characters is "<<count(a,b,c)<<endl;   
   return 0;
}

Output

The count of 3 length strings using given characters containing at least 2 different characters is 3

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(1) atau malar kerana kami tidak menggunakan sebarang gelung atau panggilan rekursif untuk mendapatkan hasilnya.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan ruang tambahan di sini.

KESIMPULAN

Dalam tutorial ini, kami telah melaksanakan program untuk mencari 3 rentetan panjang dengan kiraan 3 menggunakan aksara tertentu yang mengandungi sekurang-kurangnya 2 aksara berbeza. Kami membincangkan kaedah mudah dan melaksanakan kaedah matematik dengan kerumitan masa dan ruang yang tetap iaitu O(1).

Atas ialah kandungan terperinci Menggunakan aksara yang diberikan, kira bilangan rentetan panjang 3 yang mengandungi sekurang-kurangnya 2 aksara berbeza. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!