資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 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 個操作，因此我們找到所有這些操作的可能組合，即 (2*n)!/ (n! + n!)。給定程式的總體時間複雜度為 O(1)，這意味著我們的複雜度不依賴於給定的 n。
結論
在本文中，我們討論了一個問題，即查詢網格中從一點到另一點的路徑數。我們還學習了此問題的 C++ 程式以及我們解決的完整方法。我們可以在其他語言（如 C、Java、Python 等）中編寫相同的程式。我們希望本文對您有所幫助。
更新於： 2021年11月26日
194 次檢視
廣告