矩陣乘法加括號問題

給定一個長度的字符串，很明顯是可以加括號(矩陣乘法的結合律)
所以，一共有多少種加括號的方式呢?

給出了計算總共有多少這樣組合
例如：
下面這個串，輸入的長度為4。

ABCD

所有的加括號的可能就是

A(B(CD)) A((BC)D) (AB)(CD) (A(BC))D ((AB)C)D

所以說，輸出的結果是5.

遞歸版本

#include <iostream> using namespace std; int f(int len); int main() {int n;while (cin >> n && n) {cout << f(n) << endl;} }int f(int len) {if (len == 1) return 1;int sum = 0;for (int i = 1; i < len; ++i) {sum += f(i) * f(len - i);}return sum; }

輸出結果：
在計算到21的時候就會出現問題了,不過估計是因為int整數型不夠放的原因。

1 1 2 1 3 2 4 5 6 42 7 132 8 429 9 1430 10 4862 11 16796 12 58786 13 208012 14 742900 15 2674440 16 9694845 17 35357670 18 129644790 19 477638700 20 1767263190 21 -2025814172

進行遞歸轉遞推的修改。速度提高了非常多倍。

#include <iostream> using namespace std; int *f; const int MAXSIZE = 1000; void cal(int begin, int end); int main() {int n, everN_MAX=0;f = new int[MAXSIZE];while (cin >> n && n) {if (n > everN_MAX) { cal(everN_MAX, n); }cout << f[n] << endl;}delete[] f; }void cal(int begin, int end) {int i, j;for (i = begin; i <= end; i++) {if (i == 1) f[i] = 1;else {f[i] = 0;for (j = 1; j < i; ++j) f[i] += f[j] * f[i - j];}} }

這個就簡單多了，輸出的結果試了試。

1 1 2 1 3 2 4 5 5 14 6 42 7 132 8 429 9 1430 10 4862 11 16796 12 58786 13 208012 14 742900 15 2674440 16 9694845 17 35357670 18 129644790 19 477638700 20 1767263190 21 -2025814172

總結

以上是生活随笔為你收集整理的字符串加括号问题（矩阵乘法组合问题）C++的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。