วิธีคูณ n องค์ประกอบด้วยการดำเนินการเชื่อมโยงใน C++

ในปัญหานี้ เราได้รับจำนวนเต็ม n ซึ่งเป็นจำนวนองค์ประกอบ งานของเราคือสร้างโปรแกรมที่นับจำนวนวิธีในการคูณองค์ประกอบ n ด้วยการดำเนินการเชื่อมโยง

ปฏิบัติการร่วม ส่งคืนผลลัพธ์เดียวกันโดยไม่คำนึงถึงวิธีการจัดเรียงตัวเลข

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

3

ผลลัพธ์

12

คำอธิบาย

เพื่อแก้ปัญหานี้ เราจะพยายามค้นหาว่ามีความสัมพันธ์หรืออนุกรมประเภทใดที่สามารถสร้างได้ เพื่อให้เราสามารถสรุปผลลัพธ์ได้ มาดูจำนวนการดำเนินการเชื่อมโยงตามจำนวนตัวดำเนินการ -

1 => 12 => 23 => 12

ทีนี้ มาลองสรุปการนับกัน สมมติว่าเรากำลังสร้างการดำเนินการเชื่อมโยงสำหรับองค์ประกอบ n ตัว เราสามารถวางตัวดำเนินการคูณ n-1 และวงเล็บ n-1 ได้

ในที่นี้เราจะจัดสองวิธี -

• พิจารณาวิธีคูณจนถึง (n-1 ). จากนั้นเราสามารถแทรกองค์ประกอบสุดท้าย a ที่ส่วนท้ายสุดของการเชื่อมโยง ค่านี้สำหรับตัวเลข n-1 จะมาจากการเชื่อมโยง 2*2*(n-2) สำหรับตัวดำเนินการ n ตัว

• จากนั้นเราจะพิจารณาการคูณของ (a1, a2, … a(n-1)) และคูณ an ไปทางซ้ายหรือขวา ซึ่งให้วิธีเพิ่มเติมสองวิธีในการสร้างการเชื่อมโยง

มาบวกและรับการเชื่อมโยงทั้งหมดสำหรับตัวดำเนินการ n ตัวโดยใช้กรณีข้างต้น

ตูด(n) =((2*2*(n-2))(ตูด(n-1))) + 2*(ตูด(n-1))ตูด(n) =(4n-8) (ตูด(n-1)) + 2*(ตูด(n-1))ตูด(n) =(4n-6)(ตูด(n-1))

ความสัมพันธ์นี้เหมือนกับเลขคาตาลันหลอกซึ่งมีสูตรเหมือนกันและมีค่าอักษรย่อเหมือนกัน

ดังนั้นเราจึงสามารถใช้สูตรทั่วไปสำหรับ pseudo Catalan Number ได้ที่นี่

ตูด(n) =(2*n-2)!/(n-1)!

มาดูการทำงานของสูตรสำหรับค่า n =5.

ตูด(10) =(2*5 - 2)!/ (5-1)!ตูด(10) =8!/4! =40320/24 =1680

โปรแกรมค้นหาวิธีคูณ n องค์ประกอบด้วยการดำเนินการเชื่อมโยง

// โปรแกรมค้นหาวิธีการคูณ n องค์ประกอบด้วยการดำเนินการเชื่อมโยง −

ตัวอย่าง

#includeusing namespace std;long int calcFactorial(int n){ if (n ==0 || n ==1) return 1; คืนค่า n*calcFactorial(n-1);}ยาว int calcWays ( int n ){ int N =2*n - 2; int R =n - 1; ผลตอบแทน (calcFactorial((2*n)-2)/calcFactorial(n-1));}int main(){ int n =7; cout<<"วิธีคูณองค์ประกอบ "< 
ผลลัพธ์
 
วิธีคูณ 7 องค์ประกอบด้วยการดำเนินการเชื่อมโยง :665280