Có cọc A, B, C và có chiếc đĩa đánh số từ đến có kích thước tương ứng là . Trạng thái ban đầu cả chiếc đĩa đều ở cọc A, và đĩa to luôn ở dưới đĩa nhỏ. Xét phương pháp chuyển đĩa sau để chuyển đĩa từ cọc A sang cọc C sao cho các đĩa to luôn luôn ở dưới các đĩa nhỏ:
gọi thủ tục Chuyen( N , A, B, C).
Trong đó:
void Chuyen(n , c1, c2, c3){
if (n == 1) {
chuyển đĩa nằm trên cùng c1 sang c3;
} else {
Chuyen(n-1, c1, c3, c2);
Chuyen( 1, c1, c2, c3);
Chuyen(n-1, c2, c1, c3);
}
}
có nghĩa là ta chuyển đĩa trên cùng của cột c1 sang cột c3 thông qua c2.
Số bước chuyển đĩa là (rất lớn), do đó sẽ có lần gọi hàm Chuyen. Vậy ta có hai bài toán sau để giải quyết:
Cho trước một số . Hỏi sau lần gọi thứ thì trạng thái của đĩa như thế nào?
Cho trước một trạng thái của đĩa, bạn hãy xét xem trạng thái đó có xuất hiện trong quá trình chuyển đĩa từ A sang C theo phương pháp trên hay không? Nếu có xuất hiện thì đó là sau lần gọi hàm Chuyen thứ bao nhiêu? (Giả sử là số ).
Dữ liệu:
Dòng đầu ghi số ;
Dòng thứ hai ghi số (nên nhớ có thể bằng );
Dòng thứ ba ghi một xâu gồm ký tự chỉ gồm A,B,C là trạng thái của các đĩa (tất nhiên các đĩa to luôn luôn ở dưới các đĩa nhỏ).
Kết quả:
Dòng đầu ghi một xâu gồm ký tự là trạng thái đĩa sau lần gọi thứ ;
Dòng sau là số ( nếu trạng thái đó không xuất hiện).
