Tìm số cách để đi từ điểm này đến điểm khác trong lưới bằng cách sử dụng C ++

Trong bài viết này, chúng tôi đưa ra một câu hỏi trong đó chúng tôi cần tìm tổng số cách từ điểm A đến B trong đó A và B là các điểm cố định, tức là, A là điểm trên cùng bên trái trong lưới và B là điểm cuối. điểm bên phải trong lưới chẳng hạn -

Input : N = 5
Output : 252

Input : N = 4
Output : 70

Input : N = 3
Output : 20

Trong bài toán đã cho, chúng ta có thể chính thức hóa câu trả lời bằng những quan sát đơn giản và nhận được kết quả của chúng ta.

Phương pháp tiếp cận để tìm ra giải pháp

Trong cách tiếp cận này, chúng tôi tạo ra một công thức cho bài toán đã cho bằng các quan sát rằng để di chuyển qua lưới từ A đến B, chúng tôi cần phải di chuyển n lần theo hướng sang phải và n lần theo hướng xuống, vì vậy điều đó có nghĩa là chúng ta cần tìm tất cả các khả năng kết hợp của các đường dẫn này, để cho chúng ta công thức kết hợp của (n + n) và n.

Ví dụ

#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";
}

Đầu ra

252

Giải thích về đoạn mã trên

Trong đoạn mã này, chúng tôi tính toán công thức kết hợp 2 * n đến n vì chúng tôi biết rằng để đi từ điểm A đến điểm B, chúng tôi sẽ yêu cầu chính xác 2 * n hoạt động theo hai hướng, tức là n hoạt động theo một hướng. và n trong phép toán khác và do đó chúng tôi tìm thấy tất cả các kết hợp có thể có của các phép toán này, tức là (2 * n)! / (n! + n!). Độ phức tạp về thời gian tổng thể của chương trình đã cho là O (1) có nghĩa là độ phức tạp của chúng ta không phụ thuộc vào n đã cho.

Kết luận

Trong bài này, chúng ta đã thảo luận về một vấn đề để tìm số cách đi từ điểm này đến điểm khác trong một lưới. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh mà chúng tôi đã giải quyết. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.