Pythonを使用してn番目のバイナリ文字列のK番目のビットを見つけるプログラム

2つの正の値nとkがあるとすると、次のルールを使用してバイナリ文字列S_nを作成できます-

• S_1 =0

• S_i =S_i-1 concatenate "1" concatenate reverse（invert（S_i-1））for i> 1

ここで、reverse（x）は反転された文字列xを返し、invert（x）はxのすべてのビットを反転します。

これらは、そのような4つの文字列の例です

• S_1 ="0"

• S_2 ="011"

• S_3 ="0111001"

• S_4 ="011100110110001"

S_nでk番目のビットを見つける必要があります。

したがって、入力がn =4 k =10の場合、S_4 ="011100110110001"であるため、出力は1になり、10番目のビットは1になります（最初のビットは位置1にあります）。

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

• kが1と同じ場合、

  • 文字列として0を返す

• それ以外の場合

  • arr：=単一要素0の配列

  • arr2：=単一要素1の配列

  • k> arrのサイズで、実行

    • templast：=arrのコピー

    • temp2last：=arr2のコピー

    • arr：=templast concatenate 1 concatenate temp2last

    • arr2：=templast concatenate 0 concatenate temp2last

• arrからk-1番目の要素を返す

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

例

def solve(n, k):
   if k == 1:
      return(str(0))
   else:
      arr = [0]
      arr2 = [1]
      while k > len(arr):
         templast = arr.copy()
         temp2last = arr2.copy()
         arr = templast + [1] + temp2last
         arr2 = templast + [0] + temp2last
      return(str(arr[k-1]))
n = 4
k = 10
print(solve(n, k))

入力

4, 10

出力

1