Python을 사용하여 n 번째 바이너리 문자열에서 K 번째 비트를 찾는 프로그램

두 개의 양수 값 n과 k가 있다고 가정하고 이제 다음 규칙을 사용하여 이진 문자열 S_n을 만들 수 있습니다. -

• S_1 =0

• S_i =S_i-1 연결 "1" 연결 역(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 연결 1 temp2last 연결

    • arr2 :=templast 연결 0 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