Rumah > pembangunan bahagian belakang > C++ > Pengaturcaraan dalam C++, cari bilangan subarray dengan nombor ganjil m

Pengaturcaraan dalam C++, cari bilangan subarray dengan nombor ganjil m

WBOY
Lepaskan: 2023-09-11 08:09:03
ke hadapan
791 orang telah melayarinya

Pengaturcaraan dalam C++, cari bilangan subarray dengan nombor ganjil m

Jika anda pernah menggunakan C++, anda mesti tahu apa itu subarray dan betapa bergunanya ia. Seperti yang kita semua tahu bahawa dalam C++ kita boleh menyelesaikan pelbagai masalah matematik dengan mudah. Jadi, dalam artikel ini, kami akan menerangkan cara untuk mencari maklumat lengkap nombor ganjil M dengan bantuan subarray ini dalam C++.

Dalam masalah ini, kita perlu mencari beberapa subarray dan integer m yang terdiri daripada tatasusunan yang diberikan, di mana setiap subarray mengandungi tepat m nombor ganjil. Berikut ialah contoh mudah pendekatan ini -

Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }

Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }
Salin selepas log masuk

Pendekatan pertama

Dalam pendekatan ini semua sub-tatasusunan yang mungkin dijana daripada tatasusunan yang diberikan, Dan semak sama ada setiap subarray mempunyai betul-betul m nombor ganjil. Ini ialah kaedah penjanaan dan carian mudah dengan kerumitan masa O(n2).

Contoh

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // n is size of array, m numbers to be find in subarrays,
                              // count is number of subarray with m odd numbers
    for (int i = 0; i < n; i++){ // outer loop to process each element.
        int odd = 0;
        for (int j = i; j < n; j++) {// inner loop to find subarray with m number
            if (a[j] % 2)
                odd++;
            if (odd == m) // if odd numbers become equals to m.
                count++;
        }
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}
Salin selepas log masuk

Output

Number of subarrays with n numbers are: 6
Salin selepas log masuk
Salin selepas log masuk

Penerangan kod di atas

#🎜 kod ini🎜#Bersisipkan kod ini cari subarrays ganjil, gelung luar digunakan untuk menambah "i", yang akan digunakan untuk memproses setiap elemen dalam tatasusunan.

Gelung dalam digunakan untuk mencari subarray dan memproses elemen sehingga pembilang ganjil mencapai m, menambah kiraan pembilang hasil untuk setiap subarray yang ditemui, dan akhirnya mencetak hasil yang disimpan dalam kiraan #🎜🎜 ##🎜 🎜#Kaedah kedua

Kaedah lain ialah mencipta tatasusunan untuk menyimpan bilangan awalan ganjil "i", memproses setiap elemen dan menambah bilangan nombor ganjil setiap kali nombor ganjil dijumpai.

Apabila bilangan nombor ganjil melebihi atau sama dengan m, tambahkan nombor pada kedudukan (ganjil - m) dalam tatasusunan awalan kepadanya.

Apabila nombor ganjil menjadi lebih besar daripada atau sama dengan m, kita mengira bilangan sub-tatasusunan yang terbentuk sehingga indeks dan nombor "ganjil - m" ditambahkan pada pembolehubah kiraan. Selepas setiap elemen diproses, hasilnya disimpan dalam pembolehubah kiraan.

Contoh

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // outer loop to process every element of array
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1;    // implementing value at odd index in prefix_array[ ]
        // if array element is odd then increment odd variable
        if (array[i] % 2 == 0)
            odd++;
        // if Number of odd element becomes equal or greater than m
        //  then find the number of possible subarrays that can be formed till the index.
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}
Salin selepas log masuk

Output

Number of subarrays with n numbers are: 6
Salin selepas log masuk
Salin selepas log masuk

Penerangan kod di atas

#🎜🎜🎜 nilai permulaan # dan initis🎜 -# 🎜🎜#
int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };
Salin selepas log masuk

Di sini, kita mulakan pembolehubah n dengan saiz tatasusunan, mulakan pembolehubah m dengan bilangan nombor ganjil yang kita ingin cari, mulakan kiraan dengan 0 untuk mengekalkan kiraan yang mungkin subarrays, mulakan nombor ganjil dengan 0, dan A prefix_array saiz n + 1 memulakan pembolehubah n 0.

Memahami gelung

for (i = 0; i < n; i++){
   prefix_array[odd] = prefix_array[odd] + 1;
   if (array[i] % 2 == 0)
      odd++;
      if (odd >= m)
         count += prefix_array[odd - m];
}
Salin selepas log masuk
Dalam gelung ini, kami melaksanakan nilai ​​pada indeks ganjil dalam prefix_array[ ], maka Jika nombor ganjil ditemui maka naikkan pembolehubah ganjil. Kami mendapati bahawa apabila pembolehubah ganjil sama dengan atau lebih besar daripada m, bilangan subarray boleh dibentuk, sehingga indeks.

Akhir sekali, kami mencetak nombor subbaris ganjil yang disimpan dalam pembolehubah kiraan dan mendapatkan output.

Kesimpulan

Dalam artikel ini, kami belajar tentang kaedah mencari bilangan subarray m ganjil melalui dua kaedah -

#🎜🎜 #

Hasilkan setiap subarray dan semak sama ada terdapat nombor ganjil di dalamnya, dan tambahkan kiraan setiap subarray yang ditemui. Kerumitan masa kod ini ialah O(n2).

    Kaedah yang cekap, lelaran melalui setiap elemen tatasusunan dan cipta tatasusunan awalan, kemudian gunakan bantuan tatasusunan awalan. Kerumitan masa kod ini ialah O(n).
  • Saya harap artikel ini membantu anda memahami masalah dan penyelesaiannya.

Atas ialah kandungan terperinci Pengaturcaraan dalam C++, cari bilangan subarray dengan nombor ganjil m. 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