Pemisahan subrentetan binari seimbang maksimum yang mungkin, mengambil paling banyak k

Tatasusunan dalam bahasa pengaturcaraan C mempunyai saiz tetap, yang bermaksud bahawa apabila saiz ditentukan, ia tidak boleh diubah atau dikecilkan.

Seperti yang kita ketahui, tatasusunan ialah satu set elemen daripada jenis data yang sama yang disimpan dalam kawasan memori bersebelahan.

Diberi tatasusunan nilai v[] dan tatasusunan binari a[]. Objektifnya adalah untuk menggunakan seberapa banyak syiling k untuk membahagikan tatasusunan binari sebanyak mungkin sambil memastikan setiap segmen mempunyai jumlah 0s yang sama dan 1s. i dan j ialah indeks jiran bagi segmen pecahan, dan kos setiap pecahan ialah (v[i] - v[j])2.

Pernyataan Masalah

Melaksanakan program yang mencari pemisahan subrentetan binari seimbang terbesar yang mungkin, menelan kos paling banyak k.

Contoh Contoh 1

Let the Input array be: 
a: [1,0,0, 1, 0, 0, 1, 1]
The given values be: 
v: [7, 8, 9, 10, 11, 12,13,14]
K: 1

Output yang diperolehi ialah: 1

Penjelasan

Memandangkan nilai K ialah 1, kita boleh membuat potongan antara indeks pertama dan kedua.

Dalam kes ini, [0, 1] dan [0, 0, 1, 1] ialah subrentetan binari seimbang hasil akhir.

Membuat potongan ini memerlukan kos (8 - 9)^2 = 1, dan 1 = 1.

Contoh Contoh 2

Let the Input array be: 
a: [1,0 1, 0, 1, 1, 0,0]
The given values be: 
v: [2, 4, 7, 10, 11, 12, 13, 14]
K: 14

Output obtained is: 2

Penjelasan

Potongan pertama akan dibuat antara indeks pertama dan kedua iaitu 4 dan 7, menelan kos (4 - 7)^2 = 9 dan pemotongan kedua akan dibuat antara indeks ketiga dan keempat iaitu 7 dan 10, dengan kos us (7 - 10)^ 2 = 9. Tiada lagi pemotongan boleh dilakukan pada masa ini Subrentetan binari seimbang dalam kes ini yang akan timbul ialah [1, 0], [1, 0], dan [1, 1, 0. , 0].

Pendekatan

Untuk mencari pemisahan subrentetan binari seimbang maksimum yang mungkin dengan kos paling banyak k, kami mengambil metodologi berikut.

Di sini kami mengambil pendekatan atas ke bawah untuk menyelesaikan masalah ini dan untuk mencari pemisahan subrentetan binari seimbang maksimum yang mungkin dengan kos paling banyak k.

Gunakan pendekatan atas ke bawah, atau lebih dikenali sebagai pengaturcaraan dinamik. Kelebihan utama pengaturcaraan dinamik adalah peningkatan kecekapan rekursi mudah. Pengaturcaraan dinamik boleh digunakan untuk mengoptimumkan sebarang penyelesaian rekursif yang melibatkan panggilan berulang ke input yang sama. Untuk mengelakkan pengiraan semula hasil submasalah kemudian, ideanya adalah untuk menyimpannya. Dengan pengoptimuman mudah ini, kerumitan masa dikurangkan daripada polinomial kepada eksponen.

Algoritma

Algoritma untuk mencari pemisahan subrentetan binari seimbang maksimum yang mungkin dengan paling banyak kos K diberikan di bawah.

• Langkah - Mulakan

• Langkah 2 - Takrifkan matriks dua dimensi m

• Langkah 3 - Tentukan fungsi untuk mencari pemisahan subrentetan binari seimbang maksimum yang mungkin.

• Langkah 4 − Takrifkan pembolehubah integer sifarKira untuk mengira bilangan sifar dan satuKira untuk mengira bilangan satu masing-masing

• Langkah 5 − Tentukan pembolehubah integer cntSplits untuk mengira bilangan pecahan

• Langkah 6 - Ulangi tatasusunan yang diberikan a

• Langkah 7 − semak sama ada bilangan sifar sama dengan nombor satu, kemudian simpan satu maksimum yang boleh dilaksanakan

• Langkah 8 - Anggap indeks berada pada kedudukan 0, kemudian ketahui sama ada 1 atau 0, kemudian naikkan kiraan

• Langkah 9 − tetapkan cntSplits kepada sifar, jika kiraan satu dan kiraan sifar adalah tidak sama.

• Langkah 10 - Simpan nilai yang terhasil dalam matriks

• Langkah 11 − Cetak hasil yang diinginkan diperoleh

• Langkah 12 − Berhenti

Contoh: program C

Ini ialah pelaksanaan program C bagi algoritma di atas untuk mencari pemisahan subrentetan binari seimbang maksimum yang mungkin, dengan kos paling banyak k.

#include <stdio.h>
#include <limits.h>
#include <string.h>
//Define a two-dimensional matrix m
int m[1001][1001];

//Define a function to find maximum possible //balanced binary substring splits
int maxSplits(int a[], int v[], int k, int s) {
   if (k < 0) {
      return INT_MIN;
   }
   if (m[k][s] != -1) {
      return m[k][s];
   }
   
   //Define integer variables to count the number of zeros and ones 
   // Define an integer variable to count the //number of splits
   int zeroCount = 0, oneCount = 0;
   int cntSplits = 0;
   int i;
   
   //Iterating through the given array a
   for (i = s - 1; i > 0; i--) {
      a[i] == 0 ? zeroCount++ : oneCount++;
      
   // check whether the number of zeros is equal to the number of ones, then store the maximum feasible one
      if (zeroCount == oneCount) {
         cntSplits = cntSplits > (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i)) ? cntSplits : (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i));
      }
   }
   
   //Suppose the index is at the position 0, then find whether it is a one or a zero. then increment the count
   if (i == 0) {
      a[0] == 0 ? zeroCount++ : oneCount++;
      
   // set the cntSplits to zero , if count of one and count of zero is unequal.
      if (zeroCount != oneCount) {
         cntSplits = 0;
      }
   }
   
   // store the resultant value in the matrix
   return m[k][s] = cntSplits;
}
int main() {
   int a[] = { 1, 0, 0, 1, 0, 0, 1, 1 };
   int v[] = { 7, 8, 9, 10, 11, 12, 13, 14 };
   int k = 1;
   int s = sizeof(a) / sizeof(a[0]);
   
   //To assign a specific value to a block of memory, we use the memset() function.
   memset(m, -1, sizeof(m));
   printf("%d\n", maxSplits(a, v, k, s));
   return 0;
}

Output

1

Kesimpulan

Begitu juga, kita boleh mencari kemungkinan pemisahan subrentetan binari seimbang yang menelan kos paling banyak K.

Dalam kertas kerja ini, cabaran untuk mendapatkan program untuk mencari pemisahan subrentetan binari seimbang terbesar yang mungkin pada kebanyakan kos K ditangani.

Kod pengaturcaraan C disediakan di sini bersama-sama dengan algoritma untuk mencari pemisahan subrentetan binari seimbang terbesar yang mungkin, dengan kos paling banyak K.

Atas ialah kandungan terperinci Pemisahan subrentetan binari seimbang maksimum yang mungkin, mengambil paling banyak k. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!