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

Pythonで3xnボックスを2x1ドミノで埋めることができる方法の数を数えるプログラム

数nがあるとすると、（3 x n）ブロックを1x2ドミノで埋めることができる方法の数を見つける必要があります。必要に応じてドミノを回転させることができます。答えが非常に大きい場合は、このmod 10 ^ 9+7を返します。

したがって、入力がn =4の場合、出力は11になります。

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

  • m =10 ^ 9 + 7
  • nが奇数の場合、
    • 0を返す
  • cs：=1、os：=0
  • 2からnの範囲のiの場合、2ずつ増やします。
    • cs：=3 * cs + os
    • os：=2 * cs + os
  • return cs mod m

例（Python）

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

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n % 2 == 1:
         return 0
      cs = 1
      os = 0
      for i in range(2, n + 1, 2):
         cs, os = (3 * cs + os, 2 * cs + os,)
      return cs % m
ob = Solution()
n = 4
print(ob.solve(n))

入力

4

出力

11

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

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

  2. 一意の二分探索木の数をカウントするプログラムは、Pythonで0からnの値で形成できます

    1つの数nがあるとすると、[0、n）からの数で生成できる一意のBSTの数を見つける必要があります。答えが非常に大きい場合、結果は10 ^ 9 + 7になります。 したがって、入力がn =3の場合、出力は5になります これを解決するには、次の手順に従います- 数値：=1 denom：=n + 1 1からnの範囲のiについては、 numer：=numer * n + i numer：=numer mod m denom：=denom * i denom：=denom mod m numer：=numer *（denom ^（m-2））mod m ret