Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Tháp Hà Nội bốn cọc (Frame-Stewart)

    Bài toán Tháp Hà Nội với 4 cọc: số bước tối thiểu để chuyển nnn đĩa tuân theo công thức Frame–Stewart

    H(n)=min⁡1≤k<n(2H(k)+2 n−k−1),H(0)=0.H(n)=\min_{1\le k< n}\big(2H(k)+2^{\,n-k}-1\big),\quad H(0)=0.H(n)=min1≤k<n​(2H(k)+2n−k−1),H(0)=0.

    Ý tưởng: chuyển kkk đĩa trên cùng sang cọc phụ (dùng cả 4 cọc), chuyển n−kn-kn−k đĩa còn lại bằng 3 cọc, rồi chuyển kkk đĩa trở lại. Cho nnn, in H(n)H(n)H(n) (kết quả vừa số nguyên lớn, không modulo).

    • Định dạng đầu vào:

      Một dòng chứa số nguyên nnn.

    • Ràng buộc đầu vào:

      0≤n≤600 \le n \le 600≤n≤60.

    • Định dạng đầu ra:

      Một dòng: số bước tối thiểu H(n)H(n)H(n).

    Ví dụ:

    Đầu vào:

    3

    Đầu ra:

    5

    Giải thích:

    Với 3 đĩa và 4 cọc, tối ưu $k=1$: $2H(1)+2^2-1=2+3=5$ bước.

    Đang tải editor...