Kira bilangan jujukan kurungan normal yang berbeza yang bukan tempoh N

Dalam artikel ini, kita akan menyelidiki masalah menarik dari bidang gabungan dan pemprosesan rentetan: "Mengira jujukan kurungan biasa yang berbeza yang bukan N berkala menapis urutan yang bersifat N-berkala Kami akan membincangkan masalah itu, menyediakan pelaksanaan kod C++ bagi pendekatan kekerasan dan menerangkan kes ujian.

Memahami Pernyataan Masalah

Diberi integer N, tugasnya ialah mengira bilangan jujukan kurungan biasa yang berbeza dengan panjang 2N yang bukan titik N. Jika urutan boleh diwakili sebagai rentetan S berulang M kali, di mana panjang S ialah N dan M > 1, maka jujukan adalah N-berkala.

Jujukan kurungan biasa ialah rentetan yang boleh diubah menjadi ungkapan aritmetik yang betul dengan memasukkan aksara '1' dan '+' antara aksara asal Contohnya, jujukan "(())" adalah tetap, manakala ")(. " dan "(()" bukan.

Kaedah

Disebabkan kerumitan masalah, penyelesaian matematik secara langsung mungkin tidak dapat dilaksanakan. Sebaliknya, kita perlu menggunakan pendekatan terprogram untuk menjana jujukan kurungan dan mengira bilangan jujukan kurungan yang sepadan dengan kriteria kami.

Kami akan menggunakan fungsi rekursif untuk menjana semua kemungkinan urutan kurungan sepanjang 2N Semasa menjana jujukan, kami akan menjejaki dua parameter penting: baki kurungan (bilangan kurungan terbuka tidak boleh kurang daripada nombor. kurungan tertutup) dan bilangan kurungan terbuka (tidak boleh melebihi N).

Untuk menapis urutan N-tempoh, kami akan menyemak setiap jujukan yang dijana. Jika jujukan itu adalah ulangan bagi jujukan yang lebih kecil dengan panjang N, kami mengecualikannya daripada kiraan.

Pelaksanaan C++

Ini ialah cara brute force untuk menyelesaikan masalah dalam C++. Kaedah ini menjana semua jujukan kurungan yang mungkin dan menyemak sama ada setiap jujukan N-berkala dan menambah kiraan jika tidak. Penyelesaian ini sesuai untuk saiz input yang kecil kerana ia mempunyai kerumitan masa eksponen dan tidak berskala dengan baik untuk input yang lebih besar.

Contoh

#include <bits/stdc++.h>
using namespace std;

// Function to check if string is N periodic
bool isPeriodic(string s, int N) {
   string sub = s.substr(0, N);
   for (int i = N; i < s.size(); i += N) {
      if (sub != s.substr(i, N)) return false;
   }
   return true;
}

// Function to generate all bracket sequences
void generateBrackets(string s, int open, int close, int N, int &count) {
   // If sequence is complete
   if (s.size() == 2*N) {
      if (!isPeriodic(s, N)) count++;
      return;
   }
   
   // Add an open bracket if we have some left
   if (open < N) generateBrackets(s + "(", open + 1, close, N, count);
   
   // Add a close bracket if it doesn't make the sequence invalid
   if (close < open) generateBrackets(s + ")", open, close + 1, N, count);
}

int main() {
   int N = 3;
   int count = 0;
   generateBrackets("", 0, 0, N, count);
   cout << "Count of sequences: " << count;
   return 0;
}

Output

Count of sequences: 5

Kes Ujian

Mari kita pertimbangkan kes ujian dengan N = 3. Kod ini akan menjana kesemua 5 jujukan kurungan biasa yang berbeza dengan panjang 6 yang bukan 3-berkala: ((())), (()()), (())( ), ()(()), ()()().

Kesimpulan

Artikel ini memperkenalkan kaedah untuk menyelesaikan masalah mengira urutan kurungan biasa yang berbeza dengan noktah bukan N. Walaupun pendekatan ini boleh mengendalikan input berskala kecil, adalah penting untuk ambil perhatian bahawa masalah itu mempunyai kerumitan eksponen kerana keperluan untuk menjana dan menyemak semua jujukan kurungan yang mungkin, dan oleh itu tidak sesuai untuk input berskala besar.

Atas ialah kandungan terperinci Kira bilangan jujukan kurungan normal yang berbeza yang bukan tempoh N. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!