Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで最大k個の連続したゲームに勝つ方法の数を数えるプログラム

nとkの2つの数があるとします。ここで、nはプレイするゲームの数を表します。 k以下のゲームを連続して勝つことができる方法をいくつ見つける必要があります。答えが大きすぎる場合は、結果を10 ^ 9+7で変更します。

したがって、入力がn =3 k =2の場合、出力は7になります。これは、2回以下の連続で勝つことができる方法として、["LLL"、 "WLL"、 "LWL"、 「LLW」、「WWL」、「LWW」、「WLW」]

これを解決するには、次の手順に従います-

  • m：=1 ^ 9 + 7
  • 関数dp（）を定義します。これにはi、Kが必要です
  • i> =nまたはK>kの場合、
    • K <=kの場合はtrueを返し、それ以外の場合はfalseを返します
  • return dp（i + 1、0）mod m + dp（i + 1、K + 1）mod m
  • メインの方法から、次の手順を実行します-
  • return dp（0、0）mod m

例

理解を深めるために、次の実装を見てみましょう-

def solve(n, k):
   m = 1**9 + 7

   def dp(i, K):
      if i >= n or K > k:
         return K <= k
      return dp(i + 1, 0) % m + dp(i + 1, K + 1) % m

   return dp(0, 0) % m

n = 4
k = 2
print(solve(n, k))

入力

4, 2

出力

5

  1. PythonでnノードのBSTの数をカウントするプログラム

    n個の異なるノードがあるとします。すべてが異なります。二分探索木を形成するためにそれらを配置できる方法の数を見つける必要があります。二分探索木で知っているように、左側のサブツリーは常に小さい値を保持し、右側のサブツリーは大きい値を保持します。 これを解決するために、カタラン数を見つけます。カタラン数C（n）は、n個の異なるキーを持つ二分探索木を表します。式は次のようになります $$ C（n）=\ frac {（2n）！} {（n + 1）！\ times n！} $$ したがって、入力がn =3の場合、出力は5になります。 これを解決するには、次の手順に従います- 関数ncr

  2. 連続する1’のないバイナリ文字列の数をカウントするPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −正の整数Nが与えられているので、文字列に連続する1が存在しないように、長さNで使用可能なすべての可能な個別のバイナリ文字列をカウントする必要があります。 次に、以下の実装のソリューションを見てみましょう- 例 # count the number of strings def countStrings(n):    a=[0 for i in range(n)]    b=[0 for i in range(n)]    a[0] = b[0]