Giả sử chúng ta có hai số a và b, chúng ta phải tìm một mảng chứa các giá trị trong phạm vi [1, a] và yêu cầu chính xác b số lệnh gọi của hàm sắp xếp hợp nhất đệ quy.
Vì vậy, nếu đầu vào là a =10, b =15, thì đầu ra sẽ là [3,1,4,6,2,8,5,9,10,7]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm giải quyết (). Thao tác này sẽ chuyển sang trái, phải, mảng, b
- nếu b <1 hoặc left + 1 giống với phải thì
- trở lại
- b:=b - 2
- giữa:=(trái + phải) / 2
- temp:=array [mid - 1]
- array [mid-1]:=array [giữa]
- array [mid]:=temp
- giải quyết (trái, giữa, mảng, b)
- giải quyết (giữa, phải, mảng, b)
- Từ phương thức chính, hãy làm như sau -
- nếu b mod 2 giống 0, thì
- hiển thị "Không có"
- trở lại
- array:=một mảng có kích thước n + 1 và điền bằng 0
- mảng [0]:=1
- đối với tôi trong phạm vi từ 1 đến a, thực hiện
- mảng [i]:=i + 1
- b:=b - 1
- giải quyết (0, a, mảng, b)
- trả về mảng, a
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]