Trong bài toán này, chúng ta được cho một số nguyên n là số lượng phần tử. Nhiệm vụ là tạo một chương trình đếm số cách nhân n phần tử với phép toán kết hợp.
Phép toán kết hợp trả về cùng một kết quả bất kể cách sắp xếp các số.
Hãy xem ví dụ để hiểu bài toán,
Đầu vào
3
Đầu ra
12
Giải thích
(x*(y*z)), (x*(z*y)), (y*(x*z)), (y*(z*x)), (z*(x*y)), (z*(y*x)), ((x*y)*z), ((y*x)*z), ((x*z)*y), ((z*x)*y), ((z*y)*x), ((y*z)*x).
Để giải bài toán này, chúng ta sẽ thử tìm xem có mối quan hệ hay chuỗi nào có thể tạo ra để khái quát hóa kết quả. Hãy xem số phép toán kết hợp dựa trên số toán tử:
1 => 1 2 => 2 3 => 12
Bây giờ, hãy thử khái quát hóa số lượng. Giả sử, chúng ta đang tạo các phép toán kết hợp cho n phần tử thì, chúng ta có thể đặt n-1 toán tử nhân và n-1 ngoặc đơn.
Ở đây, chúng ta sẽ sắp xếp chúng theo hai cách:
Xét các cách nhân cho đến (n-1). Sau đó chúng ta có thể chèn phần tử cuối cùng ở bất kỳ đầu nào của phép kết hợp. Điều này cho n-1 số sẽ tạo ra 2*2*(n-2) phép kết hợp cho n toán tử.
Sau đó chúng ta sẽ xét phép nhân của (a1, a2, ... a(n-1)) và nhân an vào trái hoặc phải cho thêm hai cách tạo phép kết hợp.
Hãy cộng và lấy tổng phép kết hợp cho n toán tử sử dụng các trường hợp trên.
ass(n) = ((2*2*(n-2))(ass(n-1))) + 2*(ass(n-1)) ass(n) = (4n-8)(ass(n-1)) + 2*(ass(n-1)) ass(n) = (4n-6)(ass(n-1))
Mối quan hệ này giống với Số Catalan giả, có cùng công thức và cùng giá trị ban đầu.
Vì vậy, chúng ta có thể áp dụng công thức chung cho Số Catalan giả ở đây,
ass(n) = (2*n-2)!/(n-1)!
Hãy xem hoạt động của công thức cho n = 5.
ass(10) = (2*5 - 2)!/ (5-1)! ass(10) = 8!/4! = 40320/24 = 1680
Chương trình tìm số cách nhân n phần tử với phép toán kết hợp
// Chương trình tìm số cách nhân n phần tử với phép toán kết hợp
Ví dụ
#include<iostream> using namespace std; long int calcFactorial(int n){ if (n == 0 || n == 1) return 1 ; return n*calcFactorial(n-1); } long int calcWays ( int n ){ int N = 2*n - 2 ; int R = n - 1 ; return (calcFactorial((2*n)-2)/calcFactorial(n-1)); } int main(){ int n = 7; cout<<"Số cách nhân "<<n<<" phần tử với phép toán kết hợp : "<<calcWays(n); return 0 ; }Đầu ra
Số cách nhân 7 phần tử với phép toán kết hợp : 665280