Trong bài toán này, chúng ta được cung cấp một số nguyên n là số phần tử. Nhiệm vụ của chúng tôi 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 liên kết.
Hoạt động liên kết trả về cùng một kết quả bất kể cách các số được sắp xếp.
Hãy lấy một ví dụ để hiểu vấ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 quyết vấn đề này, chúng tôi sẽ cố gắng tìm xem có bất kỳ mối quan hệ nào hoặc bất kỳ loại chuỗi nào có thể được tạo ra để chúng tôi có thể tổng quát hóa kết quả của mình hay không. Hãy xem số lượng hoạt động kết hợp dựa trên số lượng toán tử -
1 => 1 2 => 2 3 => 12
Bây giờ, hãy cố gắng tổng 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ử, chúng ta có thể đặt n-1 toán tử nhân và n-1 dấu ngoặc đơn.
Ở đây, chúng tôi sẽ sắp xếp chúng theo hai cách -
-
Đang xem xét các cách để nhân lên đến ( n-1 ). Và sau đó chúng ta có thể chèn phần tử cuối cùng là an vào bất kỳ phần cuối nào của liên kết. Điều này có thể cho n-1 số sẽ từ kết hợp 2 * 2 * (n-2) cho n toán tử.
-
Sau đó, chúng tôi sẽ xem xét phép nhân (a1, a2,… a (n-1)) và bội số an sang trái hoặc phải để tạo ra hai cách bổ sung để tạo liên kết.
Hãy thêm và lấy tổng số liên kết cho n toán tử bằng cách sử dụng 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ác giá trị viết tắt giống nhau.
Vì vậy, chúng ta có thể áp dụng công thức chung cho Số Catalan giả tại đây,
ass(n) = (2*n-2)!/(n-1)!
Hãy xem hoạt động của công thức của chúng tôi cho các giá trị n =5.
ass(10) = (2*5 - 2)!/ (5-1)! ass(10) = 8!/4! = 40320/24 = 1680
Chương trình tìm các cách nhân n phần tử với một phép toán kết hợp
// Chương trình tìm cách nhân n phần tử với một 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<<"The ways to multiply "<<n<<" elements with an associative operation : "<<calcWays(n);
return 0 ;
} Đầu ra
The ways to multiply 7 elements with an associative operation : 665280