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 回の操作が必要であることがわかっています。つまり、一方向に n 回の操作があり、もう一方の方向に n 回の操作があるため、これらの操作のすべての可能性を求めます。その組み合わせは次のとおりです。 (2*n)!/(n!n!)。指定されたプログラムの全体的な時間計算量は O(1) です。これは、計算量が指定された n に依存しないことを意味します。

結論

この記事では、グリッド内のある点から別の点へのルートの数を見つける問題について説明しました。また、この問題に対する C プログラムと、それを解決するための完全なアプローチも学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ でのプログラミング、グリッド内のある点から別の点へのパスの数を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。