Giả sử chúng ta có hai số a và b, chúng ta phải tìm một mảng chứa giá trị trong phạm vi [1, a] và yêu cầu chính xác b lần gọi hàm merge sort đệ quy.
Ví dụ, nếu a = 10, b = 15, thì đầu ra sẽ là [3,1,4,6,2,8,5,9,10,7].
Giải pháp:
- Định nghĩa hàm solve(left, right, array, b)
- Nếu b < 1 hoặc left+1 == right: return
- b := b - 2
- mid := (left + right) // 2
- Hoán đổi array[mid-1] và array[mid]
- Gọi đệ quy solve(left, mid, array, b) và solve(mid, right, array, b)
- Từ main: nếu b chẵn thì in "None"
- Khởi tạo mảng size n+1, fill 0, array[0]=1
- for i in 1..a-1: array[i] = i+1
- b := b - 1
- Gọi solve(0, a, array, b)
- Trả về array[:a]
Ví dụ
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])
Đầu vào
10,15
Đầu ra
[3, 1, 4, 6, 2, 8, 5, 9, 10, 7]