lập chương trình đệ quy giải bài toán:

Có ba cọc trên vòng tròn, được đánh số theo thứ tự chiều kim đồng hồ là 1, 2, 3.Có N đĩa kích thước từ lớn đến nhỏ, được sắp xếp chồng đĩa nhỏ nằm trên đĩa lớn tại cọc 1.

Yêu cầu: Cần chuyển N đĩa từ cọc 1 sang cọc 3 theo các quy tắc:

- Mỗi bước chỉ chuyển được một đĩa.

- Trong quá trình chuyển đĩa, chỉ cho phép đĩa nhỏ đặt lên trên đĩa lớn.

Dữ liệu Một số nguyên duy nhất N (0<N <=15)

Kết quả gồm nhiều dòng, trong đó mỗi dòng mô tả một bước chuyển đĩa gồm bắt đầu là số liệu cọc xuất phát, tiếp theo là số hiệu cọc chuyển đến, ghi cách nhau ít nhất một dấu trắng.

Ví dụ

input

2

output

1 21 32 3

lưu ý:code bài này chỉ dành cho HSG và có thể dùng bất cứ NNLT nào tuỳ thích. UwU

lập chương trình đệ quy giải bài toán:

Có ba cọc trên vòng tròn, được đánh số theo thứ tự chiều kim đồng hồ là 1, 2, 3.Có N đĩa kích thước từ lớn đến nhỏ, được sắp xếp chồng đĩa nhỏ nằm trên đĩa lớn tại cọc 1.

Yêu cầu: Cần chuyển N đĩa từ cọc 1 sang cọc 3 theo các quy tắc:

- Mỗi bước chỉ chuyển được một đĩa.

- Trong quá trình chuyển đĩa, chỉ cho phép đĩa nhỏ đặt lên trên đĩa lớn.

Dữ liệu Một số nguyên duy nhất N (0<N <=15)

Kết quả gồm nhiều dòng, trong đó mỗi dòng mô tả một bước chuyển đĩa gồm bắt đầu là số liệu cọc xuất phát, tiếp theo là số hiệu cọc chuyển đến, ghi cách nhau ít nhất một dấu trắng.

Ví dụ

input

2

output

1 21 32 3

lưu ý:code bài này chỉ dành cho HSG và có thể dùng bất cứ NNLT nào tuỳ thích. UwU

Bài toán tháp Hà Nội

 Có 3 cái cọc A,B,C và 6 cái đĩa đục lỗ. Ban đầu có 6 cái đĩa ở cọc A, đĩa to ở dưới, đĩa nhỏ ở trên. Mỗi lần thực hiện cho phép lấy 1 đĩa và chuyển sang 1 cọc khác với điều kiện: đĩa to không được xếp trên đĩa nhỏ. Mục tiêu của ta là chuyển tất cả 6 đĩa từ A sang C. Hỏi cần ít nhất bao nhiêu lần để làm được điều này?

Trong bài toán 6, thực ra số đĩa cần chuyển không phải là 3 đĩa, mà Vị Hoàng đế đã không cho biết số đĩa trên tháp A ban đầu là bao nhiêu. Toán đố tuần này yêu cầu bạn phải đưa ra lời giải khi muốn chuyển 4 đĩa từ trục A sang trục C như hình vẽ dưới đây, trong đó được phép sử dụng trục B làm trục trung chuyển. Bài toán cụ thể như sau:



Có 4 đĩa có lỗ ở giữa đang ở trục A, hãy tìm cách chuyển tất cả 4 đĩa từ trục A sang trục C sao cho:

Mỗi lần chỉ được chuyển 1 đĩa từ một trục sang một hai trục còn lại
Trên mỗi trục, đĩa bé phải nằm trên đĩa to
Lời giải của các bạn trình bày vào ô Bình luận phía dưới và có dạng sau: Lần 1 chuyển đĩa 1 từ A sang B; Lần 2 chuyển đĩa 2 từ A sang C; v.v.; đến khi nào tất cả các đĩa đều nằm trên trục C.

Tương truyền rằng ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời, Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư. Bài toán của Hoàng đế là: cho 3 cái đĩa và ba cái tháp (trục): A là trục nguồn, C là trục đích, và B là trục trung chuyển. Ba cái đĩa có kích cỡ khác nhau (đánh số 1, 2, 3 như Hình vẽ) và có lỗ ở giữa để có thể lồng vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên, những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục C, với điều kiện mỗi lần chỉ chuyển được một cái và luôn phải đảm bảo quy định "nhỏ trên lớn dưới", biết rằng trục B được phép sử dụng làm trục trung chuyển; đĩa chỉ có thể đặt vào ba trục, không được đặt ra ngoài.

Bạn hãy đưa ra lời giải cho bài toán tháp Hà Nội ở trên với số lần chuyển ít nhất. Lời giải của bạn trình bày vào ô Bình luận phía dưới và có dạng như sau: Lần 1 chuyển đĩa 3 từ trục A sang trục C; Lần 2 chuyển đĩa .. từ trục ... sang trục ...

Bài toán 6

Tương truyền rằng ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời, Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư. Bài toán của Hoàng đế là: cho 3 cái đĩa và ba cái tháp (trục): A là trục nguồn, C là trục đích, và B là trục trung chuyển. Ba cái đĩa có kích cỡ khác nhau (đánh số 1, 2, 3 như Hình vẽ) và có lỗ ở giữa để có thể lồng vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên, những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục C, với điều kiện mỗi lần chỉ chuyển được một cái và luôn phải đảm bảo quy định "nhỏ trên lớn dưới", biết rằng trục B được phép sử dụng làm trục trung chuyển; đĩa chỉ có thể đặt vào ba trục, không được đặt ra ngoài.

Bạn hãy đưa ra lời giải cho bài toán tháp Hà Nội ở trên với số lần chuyển ít nhất. Lời giải của bạn trình bày vào ô Bình luận phía dưới và có dạng như sau: Lần 1 chuyển đĩa 3 từ trục A sang trục C; Lần 2 chuyển đĩa .. từ trục ... sang trục ...