ในโจทย์นี้ เราได้รับจำนวนเต็ม n ซึ่งเป็นจำนวนองค์ประกอบ งานของเราคือสร้างโปรแกรมนับจำนวนวิธีในการคูณ n องค์ประกอบด้วยการดำเนินการแบบ associative
การดำเนินการแบบ Associative (Associative operations) ให้ผลลัพธ์เดียวกันไม่ว่าจะจัดเรียงตัวเลขอย่างไร
ตัวอย่าง
อินพุต
3
เอาต์พุต
12
คำอธิบาย
(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).
เพื่อแก้ปัญหานี้ เราจะพยายามหาว่ามีความสัมพันธ์หรืออนุกรมประเภทไหนที่สามารถสร้างได้ เพื่อให้เราสามารถทำให้ผลลัพธ์เป็นทั่วไปได้ ลองดูจำนวนการดำเนินการ associative ตามจำนวนตัวดำเนินการ:
1 => 1 2 => 2 3 => 12
ตอนนี้ ลองทำให้จำนวนเป็นทั่วไป สมมติ เราสร้างการดำเนินการ associative สำหรับ n องค์ประกอบ แล้วเราสามารถวางตัวดำเนินการคูณ n-1 ตัว และวงเล็บ n-1 คู่
ที่นี่ เราจะจัดเรียงพวกเขา 2 วิธี:
พิจารณาวิธีการคูณจนถึง (n-1) แล้วเราสามารถแทรกองค์ประกอบสุดท้ายไว้ที่ปลายใดก็ได้ของการเชื่อมโยง สำหรับ n-1 ตัวเลข จะได้ 2*2*(n-2) การเชื่อมโยงสำหรับ n ตัวดำเนินการ
จากนั้นพิจารณาการคูณของ (a1, a2, ... a(n-1)) และคูณ an ไปทางซ้ายหรือขวา ซึ่งให้วิธีเพิ่มเติม 2 วิธีในการสร้างการเชื่อมโยง
มาบวกและหาจำนวนการเชื่อมโยงทั้งหมดสำหรับ 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))
ความสัมพันธ์นี้เหมือนกับ Pseudo Catalan Number ซึ่งมีสูตรและค่าเริ่มต้นเหมือนกัน
ดังนั้น เราสามารถใช้สูตรทั่วไปสำหรับ Pseudo Catalan Number ได้:
ass(n) = (2*n-2)! / (n-1)!
ลองดูการทำงานของสูตรสำหรับ n = 5:
ass(5) = (2*5 - 2)! / (5-1)! ass(5) = 8! / 4! = 40320 / 24 = 1680
โปรแกรมหาจำนวนวิธีคูณ n องค์ประกอบด้วยการดำเนินการแบบ associative
// โปรแกรมหาจำนวนวิธีคูณ n องค์ประกอบด้วยการดำเนินการแบบ associative
ตัวอย่าง
#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;
}
ผลลัพธ์
The ways to multiply 7 elements with an associative operation: 665280
