hanoiTower
Trong bài toán Tháp Hà Nội, có n đĩa theo thứ tự từ nhỏ đến lớn đang nằm ở cột A như hình bên dưới.
Cần chuyển n đĩa trên từ cột A sang cột B (lấy C làm cột trung gian) theo quy tắc:
– Mỗi lần chỉ chuyển 1 đĩa.
– Đĩa nhỏ phải nằm trên đĩa lớn tại bất kỳ thời điểm nào trong quá trình chuyển.
Để giải bài toán trên, người ta dùng giải thuật đệ quy. Giải thuật này cho kết quả là 2n-1 bước chuyển, là số bước chuyển ít nhất cần thực hiện.
Sau khi học xong giải thuật đệ quy trên tại trường Đại học ở HCM, vị thần trong cây đèn của Aladin lập tức bay ra Hà Nội để chuyển đĩa thử. Tuy nhiên mới chỉ thực hiện được k bước chuyển (1 ≤ k ≤ 2n-1) thì vị thần đói bụng quá nên tạm nghỉ để đi ăn. Bạn hãy tính xem tại lúc này, số đĩa hiện có trên mỗi cột là bao nhiêu.
Ví Dụ:
- Với
n = 3 , k = 1thì hanoiTower(n,k) = [2,1,0]
ban đầu cột A có 3 đĩa sau k =1 lần chuyển thì được như hình bên dưới.
Đầu vào/Đầu ra:
- [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java, C#, 4s với Python, Js, Go
- [Đầu vào] Interger n
1 ≤ n ≤ 20 - [Đầu vào] Interger k
1 ≤ k ≤ 2n-1 - [Đầu ra]Array.Interger
Mảng chứa ba số nguyêna, b, cthể hiện số đĩa trên các cộtA, B, Csaukbước chuyển.
Post Comment