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의 조합 공식을 얻습니다.

Example

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

Output

252

위 코드 설명

이 코드에서는 A 지점에서 B 지점까지 정확히 두 방향이 필요하다는 것을 알고 있기 때문에 2*n에서 n까지의 결합식을 계산합니다. 2 에 대한 *n 연산, 즉 한 방향으로 n 연산이 있고 다른 방향으로 n 연산이 있으므로 이러한 연산의 가능한 모든 조합, 즉 (2*n)!/ (n! + n! )을 찾습니다. . 주어진 프로그램의 전체 시간 복잡도는 O(1)입니다. 이는 복잡성이 주어진 n에 의존하지 않는다는 것을 의미합니다.

결론

이 기사에서는 그리드의 한 지점에서 다른 지점까지의 경로 수를 찾는 문제에 대해 논의했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 접근 방식을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++ 프로그래밍, 그리드의 한 지점에서 다른 지점으로의 경로 수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!