Rumah > pembangunan bahagian belakang > C++ > Cari subrentetan pariti ganjil terpanjang

Cari subrentetan pariti ganjil terpanjang

WBOY
Lepaskan: 2023-09-07 16:13:02
ke hadapan
601 orang telah melayarinya

Cari subrentetan pariti ganjil terpanjang

Pengenalan

Dalam tutorial ini, kami membangunkan kaedah untuk mencari subrentetan pariti ganjil panjang maksimum. Pariti ganjil dalam subrentetan bermakna 1 diulang beberapa kali ganjil dalam rentetan. Pariti dalam C++ mentakrifkan nombor set bit dan 1 dalam nombor. Terdapat dua jenis pariti: pariti genap dan pariti ganjil.

Apabila jumlah bilangan "1" dalam perwakilan binari adalah ganjil, ia dipanggil rentetan pariti ganjil. Dalam tutorial ini, kami menggunakan konsep pengaturcaraan C++ untuk mencari subrentetan pariti ganjil panjang maksimum.

Pelaksanaan 1

String = 101100
Salin selepas log masuk
Output = 6
Salin selepas log masuk
Salin selepas log masuk

Dalam contoh di atas, panjang subrentetan pariti ganjil maksimum ialah 6, dan subrentetan boleh 011100. Jumlah bilangan 1 dalam subrentetan ini ialah 3, iaitu nombor ganjil. Jadikannya subrentetan pariti ganjil.

Pelaksanaan 2

String = 1011010
Salin selepas log masuk
Output = 6
Salin selepas log masuk
Salin selepas log masuk

Dalam contoh di atas, panjang maksimum subrentetan pariti ganjil dalam rentetan yang diberikan ialah 6. Subrentetan yang mungkin boleh jadi 011010 kerana ia mengandungi sejumlah 3 "1", menjadikannya subrentetan pariti ganjil.

Algoritma

  • Buat pembolehubah pembilang ct untuk mengira 1 dalam rentetan input.

  • Jika ct = 0, subrentetan pariti ganjil tidak boleh dibentuk kerana rentetan input hanya mengandungi 0.

  • Jika jumlah bilangan 1 dalam rentetan input adalah ganjil, panjang subrentetan adalah sama dengan panjang rentetan itu.

  • Apabila nilai pembolehubah ct ialah nombor genap, subrentetan boleh terdiri daripada dua kemungkinan.

  • Cari subrentetan pariti ganjil terpanjang.

  • Panjang cetakan.

Contoh

Kami melaksanakan contoh 2 dalam C++ dan menggunakan fungsi length() kelas rentetan untuk mencari panjang rentetan input dan subrentetan yang terhasil.

#include <bits/stdc++.h>
using namespace std;
 
// user defined function for calculating the index value of string
int indexOfString(string st, char ch, int j){
   for(; j < st.length(); j++)
      if(st[j] == ch)
      return j;      
      return -1;
}
//finding the lsat index value of the string
int lastIndexOfString(string st,char ch,int j){
   for(; j >= 0; j--)
      if(st[j] == ch)
   return j;
   return -1;
}
 
//user defined function to find the length of the longest odd parity substring
int maxSubstring(string s, int l){

   //variable for counting 1s
   int ct = 0;
   for (int j = 0; j < l; j++)
      if (s[j] == '1')
         ct++;

   //different counter variable conditions
   if (ct == 0)
      return 0;
       
   if (ct % 2 == 1)
      return l;
       
   int firstTime = indexOfString(s,'1',0);
   int secondTime = indexOfString(s,'1', firstTime + 1);

   int lastTime = lastIndexOfString(s,'1',s.length()-1);
   int secondLastTime = lastIndexOfString(s,'1', lastTime - 1);

   return max(lastTime, l - firstTime - 1);
}

// Controller
int main(){
   string s = "1011010";
   int l = s.length();
   cout<<"The maximum length of the odd parity substring is:" <<(maxSubstring(s, l));
}
Salin selepas log masuk

Output

The maximum length of the odd parity substring is: 6
Salin selepas log masuk

Kesimpulan

Dalam tutorial ini, kami membangunkan kaedah untuk mencari panjang subrentetan ganjil-genap terpanjang daripada rentetan input yang diberikan. Panjang subrentetan pariti ganjil dikira menggunakan pembolehubah pembilang dan menentukan berbeza jika syarat untuknya.

Kami menggunakan fungsi length() kelas rentetan untuk membantu mencari panjang subrentetan dan nilai indeks rentetan input. Nilai indeks menjana subrentetan.

Atas ialah kandungan terperinci Cari subrentetan pariti ganjil terpanjang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan