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

水平ブリックパターンの数を数えるプログラムは、Pythonのブリックのセットから作成できます

れんがと呼ばれる数値のリストと、幅と高さの他の2つの値があるとします。ブリック[i]の各要素は、長さがブリック[i]単位、幅が1単位のブリックを表します。与えられた幅と高さのレンガの完全なレイアウトが得られるように、レンガを配置する方法の数を見つける必要があります。レンガは再利用できますが、水平にしか置くことができません。

したがって、入力がブリック=[2、1]幅=3高さ=2の場合、-

であるため、出力は9になります。

水平ブリックパターンの数を数えるプログラムは、Pythonのブリックのセットから作成できます

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

  • w：=幅と同じサイズのリストで、最初の位置に1を挿入し、残りは0です
  • 0から幅の範囲のiについては、
    • w [i]がゼロ以外の場合、
      • ブリック内のxごとに、
        • i + x <=幅の場合、
          • w [i + x]：=w [i + x] + w [i]
  • return w [width] ^ height

例

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

def solve(bricks, width, height):
   w = [1] + [0] * width
   for i in range(width):
      if w[i]:
         for x in bricks:
            if i + x <= width:
               w[i + x] += w[i]
   return w[width] ** height

bricks = [2, 1]
width = 3
height = 2
print(solve(bricks, width, height))

入力

[2, 1], 3, 2

出力

9

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

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

  2. Pythonで色付きの頂点正多角形から二等辺三角形の数を数えるプログラム

    サイズnのバイナリ文字列として表されるn個の辺を持つ1つの正多角形があるとします。頂点は、青（0）または赤（1）のいずれかで色付けできます。時計回りに色付けされています。頂点が正多角形の頂点であり、色が同じである二等辺三角形の数を数える必要があります。 したがって、入力がpolygon =111010のような場合、出力は2になります。 ACEとAFEの2つの三角形があります。 これを解決するには、次の手順に従います- 関数all（）を定義します。これにはnがかかります n mod 2が1と同じ場合、no：=n *（n-1）/ 2 それ以外の場合、いいえ：=n *（n / 2-