資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究計算非N週期性的不同正則括號序列的個數
在本文中，我們將深入探討組合數學和字串處理領域一個有趣的問題：“計算非N週期性的不同正則括號序列的個數”。這個問題涉及生成不同的有效括號序列，然後過濾掉N週期性的序列。我們將討論這個問題，提供一個暴力方法的C++程式碼實現，並解釋一個測試用例。
理解問題陳述
給定一個整數N，任務是計算長度為2N的不同正則括號序列的個數，這些序列不是N週期性的。如果一個序列可以表示為字串S重複M次，其中S的長度為N且M > 1，則該序列為N週期性的。
正則括號序列是一個字串，可以透過在原始字元之間插入字元'1'和'+'將其轉換為正確的算術表示式。例如，序列"()"是正則的，而")"和"(()"則不是。
方法
由於問題的複雜性，直接的數學解法可能不可行。相反，我們需要使用程式設計方法來生成括號序列並計算滿足我們條件的序列。
我們將使用遞迴函式生成所有可能的長度為2N的括號序列。在生成序列時，我們將跟蹤兩個重要引數：括號的平衡性（左括號的數量永遠不能少於右括號的數量）和左括號的數量（不能超過N）。
為了過濾掉N週期性的序列，我們將檢查每個生成的序列。如果該序列是長度為N的較小序列的重複，我們將將其從計數中排除。
C++實現
這是一個用C++解決問題的暴力方法。這種方法生成所有可能的括號序列，並檢查每個序列是否為N週期性的，如果不是，則遞增計數。此解決方案適用於小型輸入，因為它具有指數時間複雜度，並且不適用於大型輸入。
示例
以下是實現上述演算法的程式：
#include <stdio.h>
#include <string.h>
// Function to check if string is N periodic
int isPeriodic(char *s, int N) {
char sub[N + 1];
strncpy(sub, s, N);
sub[N] = '\0';
for (int i = N; i < strlen(s); i += N) {
if (strncmp(sub, s + i, N) != 0) return 0;
}
return 1;
}
// Function to generate all bracket sequences
void generateBrackets(char *s, int open, int close, int N, int *count) {
// If sequence is complete
if (strlen(s) == 2 * N) {
if (!isPeriodic(s, N)) (*count)++;
return;
}
// Add an open bracket if we have some left
if (open < N) {
char newS[2 * N + 1];
strcpy(newS, s);
strcat(newS, "(");
generateBrackets(newS, open + 1, close, N, count);
}
// Add a close bracket if it doesn't make the sequence invalid
if (close < open) {
char newS[2 * N + 1];
strcpy(newS, s);
strcat(newS, ")");
generateBrackets(newS, open, close + 1, N, count);
}
}
int main() {
int N = 3;
int count = 0;
generateBrackets("", 0, 0, N, &count);
printf("Count of sequences: %d\n", count);
return 0;
}
輸出
Count of sequences: 5
#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;
}
輸出
Count of sequences: 5
public class Main {
// Function to check if a string is N periodic
static boolean isPeriodic(String s, int N) {
String sub = s.substring(0, N);
for (int i = N; i < s.length(); i += N) {
if (!sub.equals(s.substring(i, i + N))) {
return false;
}
}
return true;
}
// Function to generate all bracket sequences
static void generateBrackets(String s, int open, int close, int N, int[] count) {
// If the sequence is complete
if (s.length() == 2 * N) {
if (!isPeriodic(s, N)) {
count[0]++;
}
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);
}
}
public static void main(String[] args) {
int N = 3;
int[] count = {0}; // Using an array to simulate a mutable integer in Java
generateBrackets("", 0, 0, N, count);
System.out.println("Count of sequences: " + count[0]);
}
}
輸出
Count of sequences: 5
# Function to check if string is N periodic
def isPeriodic(s, N):
sub = s[:N]
for i in range(N, len(s), N):
if sub != s[i:i+N]:
return False
return True
# Function to generate all bracket sequences
def generateBrackets(s, open, close, N, count):
# If sequence is complete
if len(s) == 2 * N:
if not isPeriodic(s, N):
count[0] += 1
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)
N = 3
count = [0]
generateBrackets("", 0, 0, N, count)
print("Count of sequences:", count[0])
輸出
Count of sequences: 5
測試用例
讓我們考慮一個N = 3的測試用例。此程式碼將生成所有5個長度為6的不同正則括號序列，這些序列不是3週期性的：((())), (()()), (())(), ()(()), ()()()。
結論
本文提出了一種暴力方法來解決計算非N週期性的不同正則括號序列個數的問題。雖然這種方法可以處理小型輸入，但需要注意的是，由於需要生成和檢查所有可能的括號序列，因此該問題具有指數複雜度，這使得它不適用於大型輸入。
更新於：2023年10月16日
260 次瀏覽
廣告