Python에서 k 수의 병합 정렬 호출로 배열 찾기

두 개의 숫자 a와 b가 있다고 가정하고 [1, a] 범위의 값을 포함하는 배열을 찾아야 하고 재귀 병합 정렬 함수의 호출이 정확히 b개 필요합니다.

따라서 입력이 a =10, b =15인 경우 출력은 [3,1,4,6,2,8,5,9,10,7]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve() 함수를 정의합니다. 왼쪽, 오른쪽, 배열, b
• b <1 또는 왼쪽 + 1이 오른쪽과 같으면
  • 반환
• b :=b - 2
• 중간 :=(왼쪽 + 오른쪽) / 2
• temp :=배열[중간 - 1]
• 배열[중간-1] :=배열[중간]
• 배열[mid] :=임시
• 해결(왼쪽, 중간, 배열, b)
• 해결(중간, 오른쪽, 배열, b)
• 메인 방법에서 다음을 수행하십시오 -
• b mod 2가 0과 같으면
  • "없음" 표시
  • 반환
• array :=n + 1 크기의 배열, 0으로 채움
• 배열[0] :=1
• 범위 1에서 i에 대해
  • 배열[i] :=i + 1
• b :=b - 1
• 해결(0, 배열, b)
• 반환 배열,

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(left,right,array,b):
   if (b < 1 or left + 1 == right):
      return
   b -= 2
   mid = (left + right) // 2
   temp = array[mid - 1]
   array[mid-1] = array[mid]
   array[mid] = temp
   solve(left, mid, array, b)
   solve(mid, right, array, b)
def find_arr(a,b):
   if (b % 2 == 0):
      print("None")
      return
   array = [0 for i in range(a + 2)]
   array[0] = 1
   for i in range(1, a):
      array[i] = i + 1
   b -=1
   solve(0, a, array, b)
return array, a
a = 10
b = 15
array, size = find_arr(a, b)
print(array[:size])

입력

10,15

출력

[3, 1, 4, 6, 2, 8, 5, 9, 10, 7]