ในบทความนี้ เรามีคำถามที่ต้องค้นหาจำนวนวิธีทั้งหมดจากจุด A ถึง B โดยที่ A และ B เป็นจุดตายตัว กล่าวคือ A เป็นจุดซ้ายบนของตาราง และ B คือจุดล่างสุด จุดขวาในตารางเช่น −
Input : N = 5 Output : 252 Input : N = 4 Output : 70 Input : N = 3 Output : 20
ในปัญหาที่กำหนด เราสามารถกำหนดคำตอบให้เป็นทางการได้ด้วยการสังเกตง่ายๆ และได้ผลลัพธ์
แนวทางในการหาทางออก
ในวิธีนี้ เราสร้างสูตรสำหรับปัญหาที่กำหนดโดยสังเกตว่าสำหรับการเดินทางผ่านตารางจาก A ไปยัง B เราจำเป็นต้องเดินทาง n ครั้งในทิศทางที่ถูกต้องและ n ครั้งในทิศทางลง ซึ่งหมายความว่าเราจำเป็นต้อง หาความเป็นไปได้ทั้งหมดของการรวมกันของเส้นทางเหล่านี้ เพื่อให้เราได้สูตรของการรวมกันของ (n+n) และ n
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int fact(int n){ // factorial function
if(n <= 1)
return 1;
return n * fact(n-1);
}
int main() {
int n = 5; // given n
int answer = 0; // our answer
answer = fact(n+n); // finding factorial of 2*n
answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! + n!)
cout << answer << "\n";
} ผลลัพธ์
252
คำอธิบายของโค้ดด้านบน
ในรหัสนี้ เราคำนวณสูตรของการรวมกันของ 2*n ถึง n เนื่องจากเรารู้ว่าสำหรับการเดินทางจากจุด A ไปยัง B เราจะกำหนดให้มีการดำเนินการ 2*n ในสองทิศทาง นั่นคือ n การดำเนินการในทิศทางเดียว และการดำเนินการ n ในอีกรูปแบบหนึ่ง เราจึงพบการรวมกันที่เป็นไปได้ทั้งหมดของการดำเนินการเหล่านี้ นั่นคือ (2*n)!/ (n! + n!) ความซับซ้อนของเวลาโดยรวมของโปรแกรมที่กำหนดคือ O(1) ซึ่งหมายความว่าความซับซ้อนของเราไม่ได้ขึ้นอยู่กับ n ที่กำหนด
บทสรุป
ในบทความนี้ เราได้พูดถึงปัญหาในการหาจำนวนวิธีที่จะไปจากจุดหนึ่งไปยังอีกจุดหนึ่งในตาราง นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางทั้งหมดที่เราแก้ไข เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
