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

위 코드 설명

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

결론

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