使用Python找到第n个二进制字符串中的第k位的程序

假设我们有两个正数n和k，现在我们可以通过以下规则创建一个二进制字符串S_n-

S_1 = 0
对于i>1，S_i = S_i-1 concatenate “1” concatenate reverse(invert(S_i-1))

这里的reverse(x)返回反转的字符串x，而invert(x)翻转x中的所有位。

以下是四个这样的字符串的例子

S_1 = “0”
S_2 = “011”
S_3 = “0111001”
S_4 = “011100110110001”

我们必须找到S_n中的第k位。

因此，如果输入是n = 4 k = 10，则输出将为1，因为S_4 =“011100110110001”，因此第10位为1（第一位位于1的位置）。

要解决此问题，我们将遵循以下步骤-

如果k与1相同，则
- 返回0作为字符串
否则，
- arr：其元素为0的数组
- arr2：其元素为1的数组
- while k > arr的大小，do
  - 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))