การหาจำนวนวิธีไปจากจุดหนึ่งไปอีกจุดในกริด โดยใช้ C++

ในบทความนี้ เราได้รับคำถามที่เราต้องหาจำนวนวิธีทั้งหมดจากจุด 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 ครั้งในทิศทางลง ดังนั้นหมายความว่าเราต้องหาความเป็นไปได้ทั้งหมดของการรวมเส้นทางเหล่านี้ ซึ่งให้เราสูตรของ combination ของ (n+n) และ n

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;

int fact(int n){ // ฟังก์ตอเรียล
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}

int main() {
    int n = 5; // n ที่กำหนด
    int answer = 0; // คำตอบของเรา
    answer = fact(n+n); // หา factorial ของ 2*n
    answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! * n!)
    cout << answer << "\n";
}

ผลลัพธ์

252

คำอธิบายโค้ด

ในโค้ดนี้ เราคำนวณสูตร combination ของ 2*n เลือก n เนื่องจากเรารู้ว่าสำหรับการเดินทางจากจุด A ไป B เราจะต้องใช้การดำเนินการ 2*n ครั้งพอดีในสองทิศทาง คือ n ครั้งในทิศทางหนึ่ง และ n ครั้งในอีกทิศทางหนึ่ง และดังนั้นเราหาความเป็นไปได้ทั้งหมดของการดำเนินการเหล่านี้ คือ (2*n)! / (n! * n!) ความซับซ้อนด้านเวลาทั้งหมดของโปรแกรมที่กำหนดคือ O(1) ซึ่งหมายความว่าความซับซ้อนของเราไม่ขึ้นกับ n ที่กำหนด

สรุป

ในบทความนี้ เราอภิปรายปัญหาการหาจำนวนวิธีไปจากจุดหนึ่งไปอีกจุดในกริด เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบที่เราใช้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์