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つの方向で正確に2 * nの操作、つまり1つの方向でnの操作が必要になることがわかっているためです。およびnは他の演算であるため、これらの演算の可能なすべての組み合わせ、つまり（2 * n）！/（n！+ n！）が見つかります。指定されたプログラムの全体的な時間計算量はO（1）です。これは、複雑さが指定されたnに依存しないことを意味します。

結論

この記事では、グリッド内のあるポイントから別のポイントに移動する方法の数を見つけるための問題について説明しました。また、この問題のC ++プログラムと、解決した完全なアプローチについても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。