{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cb\u003eNền tảng\u003c/b\u003e\r\u003cbr\u003eCharlie Darkbrown ngồi trong một bài học Khoa học Máy tính nhàm chán khác: Hiện tại, giáo viên đang giải thích vấn đề tháp Hà Nội tiêu chuẩn, điều này khiến Charlie chán chết!\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/b49f7faee4f57434cc9faca3dc837dd6?v\u003d1708185023\"\u003e\u003c/center\u003e\r\u003cbr\u003eGiáo viên chỉ vào bảng đen (Hình 4) và nói: \"Vì vậy đây là vấn đề:\r\u003cbr\u003e\u003cul\u003e\u003cli\u003eCó ba tháp: A, B và C.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eCó n đĩa. Số n là hằng số khi giải câu đố.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eTất cả các đĩa đều khác nhau về kích thước.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eCác đĩa được xếp ban đầu trên tháp A tăng dần về kích thước từ trên xuống dưới.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eMục tiêu của câu đố là chuyển tất cả các đĩa từ tháp A sang tháp C.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eMột đĩa mỗi lần có thể được di chuyển từ đỉnh của một tháp hoặc sang một tháp trống hoặc sang một tháp có đĩa lớn hơn ở trên.\u003c/li\u003e\u003c/ul\u003e\r\u003cbr\u003eVì vậy, nhiệm vụ của bạn là viết một chương trình tính số lần di chuyển đĩa nhỏ nhất cần thiết để chuyển tất cả các đĩa từ tháp A sang C.\"\r\u003cbr\u003eCharlie: \"Điều này cực kỳ chán—ai cũng biết rằng điều này có thể được giải quyết bằng đệ quy đơn giản. Tôi từ chối viết mã cho một cái gì đơn giản như thế này!\"\r\u003cbr\u003eGiáo viên thở dài: \"Vâng, Charlie, hãy nghĩ về một cái gì đó cho bạn làm: Đối với bạn, có một tháp thứ tư D. Tính số lần di chuyển đĩa nhỏ nhất để chuyển tất cả các đĩa từ tháp A sang tháp D bằng cách sử dụng cả bốn tháp.\"\r\u003cbr\u003eCharlie trông khó chịu: \"Ugh. . . Vâng, tôi không biết một thuật toán tối ưu cho bốn tháp. . . \"\r\u003cbr\u003e\u003cb\u003eVấn đề\u003c/b\u003e\r\u003cbr\u003eVấn đề thực sự là việc giải quyết vấn đề không phải là điều mà Charlie giỏi. Thực ra, điều duy nhất mà Charlie thực sự giỏi là \"ngồi bên cạnh người nào đó có thể làm việc\". Và bây giờ đoán xem — đúng vậy! Đó là bạn ngồi bên cạnh Charlie, và anh ấy đã nhìn chằm chằm vào bạn.\r\u003cbr\u003eMay mắn thay, bạn biết rằng thuật toán sau hoạt động cho n \u0026lt;\u003d 12: Ban đầu có k \u0026gt;\u003d 1 đĩa trên tháp A được cố định và n-k đĩa còn lại được di chuyển từ tháp A sang tháp B bằng cách sử dụng thuật toán cho bốn tháp. Sau đó, k đĩa còn lại từ tháp A được di chuyển sang tháp D bằng cách sử dụng thuật toán cho ba tháp. Cuối cùng, n - k đĩa từ tháp B được di chuyển sang tháp D lại bằng cách sử dụng thuật toán cho bốn tháp (và do đó không di chuyển bất kỳ trong số k đĩa đã có trên tháp D). Làm điều này cho tất cả k 2 ∈{1, .... , n} và tìm ra k với số lần di chuyển nhỏ nhất.\r\u003cbr\u003eVì vậy, với n \u003d 3 và k \u003d 2, bạn sẽ đầu tiên di chuyển 1 (3-2) đĩa từ tháp A sang tháp B bằng cách sử dụng thuật toán cho bốn tháp (một lần di chuyển). Sau đó, bạn sẽ di chuyển hai đĩa còn lại từ tháp A sang tháp D bằng cách sử dụng thuật toán cho ba tháp (ba lần di chuyển). Và bước cuối cùng sẽ là di chuyển đĩa từ tháp B sang tháp D bằng cách sử dụng lại thuật toán cho bốn tháp (một lần di chuyển khác). Do đó, giải pháp cho n \u003d 3 và k \u003d 2 là 5 lần di chuyển. Để chắc chắn rằng đây thực sự là giải pháp tốt nhất cho n \u003d 3, bạn cần kiểm tra các giá trị khả thi khác là 1 và 3 cho k. (Nhưng, theo đúng cách, 5 là tối ưu. . . )"}},{"title":"Nhập","value":{"format":"HTML","content":"Không có dữ liệu vào."}},{"title":"Đầu ra","value":{"format":"HTML","content":"Đối với mỗi n (1 \u0026lt;\u003d n \u0026lt;\u003d 12), in ra một dòng duy nhất chứa số lần di chuyển tối thiểu để giải quyết vấn đề cho bốn tháp và n đĩa."}},{"title":"Ví dụ","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eNo input.\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eREFER TO OUTPUT.\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}