Giả sử chúng ta có một mã mảng. Có một hoán vị mảng là hoán vị của n số nguyên dương (lẻ) đầu tiên. Danh sách này sẽ được mã hóa thành mảng mã hóa có độ dài n-1, sao cho enc [i] =perm [i] XOR perm [i + 1]. Chúng ta phải tìm hoán vị mảng ban đầu.
Vì vậy, nếu đầu vào giống như enc =[2,5,6,3], thì đầu ra sẽ là [7, 5, 0, 6, 5], ở đây [7 XOR 5 XOR 0 XOR 6 XOR 5] =[ 2, 5, 6, 3]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của enc
- kết quả:=một mảng có kích thước (n + 1) và điền bằng 0
- x:=0
- đối với tôi trong phạm vi từ 1 đến n + 1, hãy thực hiện
- x:=x XOR tôi
- kết quả [0]:=x
- đối với tôi trong phạm vi từ 1 đến n, tăng thêm 2, thực hiện
- kết quả [0]:=kết quả [0] XOR enc [i]
- đối với tôi trong phạm vi từ 1 đến n, thực hiện
- result [i]:=result [i-1] XOR enc [i-1]
- trả về kết quả
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(enc): n = len(enc) result = [0] * (n+1) x = 0 for i in range(1, n+2): x ^= i result[0] = x for i in range(1, n+1, 2): result[0] ^= enc[i] for i in range(1, n+1): result[i] = result[i-1] ^ enc[i-1] return result enc = [2,5,6,3] print(solve(enc))
Đầu vào
[2,5,6,3]
Đầu ra
[7, 5, 0, 6, 5]