สมมติว่าเรามีอาร์เรย์เข้ารหัส มีระดับการใช้งานอาร์เรย์ที่เป็นการเรียงสับเปลี่ยนของจำนวนเต็มบวก n(คี่) ตัวแรก รายการนี้จะถูกเข้ารหัสเป็นอาร์เรย์ enc ที่มีความยาว n-1 ดังนั้น enc[i] =perm[i] XOR perm[i+1] เราต้องหาค่าปรับอาเรย์เดิม
ดังนั้น หากอินพุตเป็นเหมือน enc =[2,5,6,3] ผลลัพธ์จะเป็น [7, 5, 0, 6, 5] ที่นี่ [7 XOR 5 XOR 0 XOR 6 XOR 5] =[ 2, 5, 6, 3]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ enc
- ผลลัพธ์ :=อาร์เรย์ขนาด (n+1) และเติม 0
- x :=0
- สำหรับ i ในช่วง 1 ถึง n+1 ให้ทำ
- x :=x XOR ฉัน
- ผลลัพธ์[0] :=x
- สำหรับฉันในช่วง 1 ถึง n เพิ่มขึ้น 2 ทำ
- ผลลัพธ์[0] :=ผลลัพธ์[0] XOR enc[i]
- สำหรับฉันในช่วง 1 ถึง n ทำ
- ผลลัพธ์[i] :=ผลลัพธ์[i-1] XOR enc[i-1]
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
[2,5,6,3]
ผลลัพธ์
[7, 5, 0, 6, 5]
