使用 Python 在第 n 个二进制字符串中查找第 K 位的程序

Z时代
2024-01-10
分类：综合

假设我们有两个正值 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 中的所有位。

这些是四个这样的字符串的例子

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

否则，

templast := arr 的副本
temp2last := arr2 的副本
arr := templast 连接 1 连接 temp2last
arr2 := templast 连接 0 连接 temp2last
arr := 单个元素为 0 的数组
arr2 := 具有单个元素 1 的数组
而 k > arr 的大小，做

从 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))