使用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次，這意味著我們需要找到所有可能的路徑組合，因此我們得到了(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等語言來寫同樣的程式。我們希望這篇文章對您有幫助。

以上是使用C++編程，找到在網格中從一個點到另一個點的路徑數的詳細內容。更多資訊請關注PHP中文網其他相關文章！