Tentukan langkah minimum untuk urutan dengan paling banyak 1 berdasarkan syarat yang diberikan

Tujuan artikel ini adalah untuk melaksanakan program untuk mencari langkah minimum untuk menentukan urutan maksimum 1 saat berdasarkan syarat yang diberikan.

Seperti yang kita semua tahu, tatasusunan satu dimensi yang mengandungi aksara yang ditamatkan nol boleh digunakan untuk menentukan rentetan.

Memandangkan rentetan Str dengan panjang K, di mana K sentiasa nombor genap dan mengandungi aksara "0", "1" dan "?" Pisahkan rentetan kepada dua rentetan berasingan, kami akan memanggilnya Str1 dan Str2, setiap rentetan akan mengandungi aksara pada nilai genap Str dan aksara pada nilai ganjil Str. Matlamatnya adalah untuk menentukan bilangan langkah minimum yang diperlukan untuk meramalkan bilangan 1 tertinggi dalam dua rentetan (Str1 atau Str2). Memilih aksara untuk Str1 atau Str2 dalam satu langkah. Memilih "0" jika aksara adalah sifar, "1" jika aksara itu satu, dan "?" jika ia adalah 1 atau 0 aksara.

Pernyataan Masalah

Melaksanakan program untuk mencari langkah minimum untuk menentukan urutan maksimum 1 saat berdasarkan syarat yang diberikan

Contoh 1

Input: Str = “?10?0?”

Output: 4

Arahan

• Langkah 1 - Di sini Str[0] ialah "?"

So select "0" as the character for Str1.
Which implies Str1=”0″, Str2=”″.

• Langkah 2 - Di sini Str[1] ialah "1"

Select "1" as the character for Str2.
Which implies Str1=”0″, Str2=”1″.

• Langkah 3 - Di sini Str[2] ialah "0"

Select "0" as the character for Str1.
Which implies Str1=”00″, Str2=”1″.

• Langkah 4 - Di sini Str[3] ialah "?"

Select "1" as the character for Str2.
Which implies Str1=”00″, Str2=”11″.

Tidak kira nombor apa yang dipilih oleh indeks yang tinggal, Str2 akan mempunyai lebih 1 selepas langkah 4.

Contoh 2

Input: Str = “1?0??0110”

Output: 4

Arahan

• Langkah 1 - Di sini Str[0] ialah "1"

So select "1" as the character for Str1.
Which implies Str1=”1″, Str2=”″.

• Langkah 2 - Di sini Str[1] ialah "?"

Select "1" as the character for Str2.
Which implies Str1=”1″, Str2=”1″.

• Langkah 3 - Di sini Str[2] ialah "0"

Select "0" as the character for Str1.
Which implies Str1=”10″, Str2=”1″.

• Langkah 4 - Di sini Str[3] ialah "?"

Select "1" as the character for Str2.
Which implies Str1=”10″, Str2=”11″.

• Langkah 5 - Di sini Str[4] ialah "?"

Select "0" as the character for Str1.
Which implies Str1=”100″, Str2=”11″.

• Langkah 6 - Di sini Str[5] ialah "0"

Select "0" as the character for Str2.
Which implies Str1=”100″, Str2=”111″.

• Langkah 7 - Di sini Str[6] ialah "1"

Select "1" as the character for Str1.
Which implies Str1=”1001″, Str2=”111″.

Tidak kira nombor apa yang dipilih oleh baki indeks, Str2 akan mempunyai lebih 1 selepas langkah 7.

Penyelesaian

Untuk mencari langkah minimum untuk menentukan urutan maksimum 1 saat berdasarkan syarat yang diberikan, kami menggunakan pendekatan berikut.

Diberikan di bawah adalah kaedah untuk menyelesaikan masalah ini dan mencari langkah minimum untuk menentukan urutan maksimum 1 saat berdasarkan syarat yang diberikan.

Matlamatnya adalah untuk menyelesaikan masalah secara rekursif dan mencapai penyelesaian selepas mempertimbangkan setiap alternatif.

Istilah "rekursi" tidak lain adalah proses sesuatu fungsi memanggil dirinya, sama ada secara langsung (iaitu tanpa perantara) atau tidak langsung. Fungsi setara ini dikatakan sebagai fungsi rekursif. Selain itu, algoritma rekursif boleh digunakan untuk menyelesaikan pelbagai masalah dengan relatif mudah.

Algoritma

Cari algoritma untuk menentukan langkah minimum untuk menentukan urutan maksimum 1 saat berdasarkan syarat yang diberikan di bawah

• Langkah 1 - Mulakan

• Langkah 2 - Tentukan fungsi rekursif.

• Langkah 3 - Tentukan rentetan Str, integer i, integer count1 dan count2, yang digunakan untuk menyimpan nombor hingga i dalam Str1 dan Str2 masing-masing.

• Langkah 4 - Tentukan integer n1 dan n2 untuk menyimpan kedudukan yang tersedia dalam Str1 dan Str2

• Langkah 5 - Jika i sama dengan m, maka kedua-dua Str1 dan Str2 terisi sepenuhnya dan jawapannya kini boleh dijangka dengan pasti. Jadi sila balas 0.

• Langkah 6 - Jika count1 melebihi hasil darab n2 dan count2, kembalikan 0 kerana Str1 kini akan mempunyai lebih banyak nilai berbanding Str2 walaupun selepas memilih semua nilai dalam Str2. < /p>

Disebabkan perkara di atas, jika kiraan2 melebihi hasil darab n1 dan kiraan1, 0 dikembalikan.

• Langkah 7 - Sahkan sama ada i sama dengan nombor genap atau ganjil selepas menguji tika asas. Jika saya genap, Str1 akan memilih indeks ini, jika tidak, Str2.

Memandangkan bilangan kedudukan yang boleh diakses dalam rentetan akan dikurangkan sebanyak satu kedudukan selepas pelapik, ia dikurangkan sebanyak n1 atau n2 bergantung pada rentetan empuk pada masa ini.

• Langkah 8 - Andaikan watak semasa ialah '?', iaitu s[i] = '? Kemudian lakukan dua panggilan rekursif untuk memilih "1" dan "0", gabungkan 1 ke dalam kedua-duanya dan kembalikan Yang terkecil daripada keduanya.

Jika tidak, buat panggilan dan tambah panggilan untuk mendapatkan jawapan.

Maklum balas kepada pertanyaan ini akan diberikan oleh panggilan rekursif terakhir.

• Langkah 8 - Berhenti

Contoh: program C++

Ini ialah pelaksanaan program C bagi algoritma yang ditulis di atas untuk mencari langkah minimum untuk menentukan urutan maksimum 1 saat berdasarkan syarat yang diberikan

// the C++ program of the above written algorithm
#include <bits/stdc++.h>
using namespace std;

// the function in order find the minimum number of the steps recursively  needed by combining both the 2 strings
int minimumSteps(string& Str, int cnt1, int cnt2,int n1, int n2, int m,int i){

   // check whetherthe current pointer reach //the end
   if (i == m) {
      return 0;
   }
    
   // the Condition which indicates here that one string does more ones than the other regardless of which number is opted  for theindexes which is remaining
   if (cnt1 > (n2 + cnt2)
         || cnt2 > (n1 + cnt1)) {
      return 0;
   }
   int ch1 = 0;
   int ch2 = 0;
    
   // on condition that i is found to be even, then choose the character for Str
   if (i % 2 == 0) {
      if (Str[i] == '?') {
         return min( 1 + minimumSteps(Str, i + 1,  cnt1 + 1, cnt2, n1 - 1, n2, m), 1 + minimumSteps( Str, i + 1, cnt1, cnt2, n1 - 1, n2, m));
      } else if (Str[i] == '1') {
         ch1 = 1 + minimumSteps(Str, i + 1, cnt1 + 1, cnt2, n1 - 1, n2, m);
         return ch1;
      } else {
         ch2 = 1 + minimumSteps(Str, i + 1, cnt1, cnt2, n1 - 1, n2, m);
         return ch2;
      }
   }
   else {
      if (Str[i] == '?') {
         return min(1 + minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m),1 + minimumSteps(Str, i + 1,cnt1, cnt2, n1, n2 - 1, m));
      } else if (Str[i] == '1') {
         ch1 = 1+ minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m);
         return ch1;
      } else {
         ch2 = 1+ minimumSteps( Str, i + 1, cnt1, cnt2, n1, n2 - 1, m);
         return ch2;
      }
   }
}
int main(){
   string str = "?10?0?01";
   int M = str.size();
   cout << minimumSteps(str, 0, 0, 0, M / 2, M / 2, M);
   return 0;
}

Output

1

Kesimpulan

Begitu juga, kita boleh mencari bilangan langkah minimum untuk menentukan urutan dengan maksimum 1s mengikut syarat yang diberikan

Kertas kerja ini menangani cabaran untuk mendapatkan bilangan langkah minimum untuk menentukan urutan maksimum 1 saat yang diberi syarat.

Kod pengaturcaraan C++ disediakan di sini bersama-sama dengan algoritma untuk mencari langkah minimum yang menentukan urutan maksimum 1 saat berdasarkan syarat yang diberikan.

Atas ialah kandungan terperinci Tentukan langkah minimum untuk urutan dengan paling banyak 1 berdasarkan syarat yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!