Nội dung bài viết

    Xem thêm

    Hãy chứng minh công thức H(n) = 2^n - 1 bằng quy nạp toán học. Hãy tính H(64)

    Lời giải Vận dụng 1 trang 24 Chuyên đề Tin học 11 sách Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời các câu hỏi & làm bài tập.

    1 210 20/08/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 4: Tháp Hà Nội

    Vận dụng 1 trang 24 Chuyên đề Tin học 11: Hãy chứng minh công thức

    H(n) = 2n - 1 bằng quy nạp toán học. Hãy tính H(64) và so sánh với con số các bước đã được đưa ra trong tờ quảng cáo của trò chơi vào năm 1883.

    Lời giải:

    - Nếu chỉ có một đĩa (n=1), H(n) = 1.

    - Nếu có n đĩa, để chuyển tất cả các đĩa từ tháp ban đầu sang tháp đích, ta phải thực hiện các bước sau:

    Chuyển n-1 đĩa từ tháp ban đầu sang tháp trung gian.

    Chuyển đĩa cuối cùng (đĩa lớn nhất) từ tháp ban đầu sang tháp đích.

    Chuyển n-1 đĩa từ tháp trung gian sang tháp đích.

    Số bước chuyển tất cả các đĩa là H(n) = 2 * H(n-1) + 1.

    - Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán học:

    Bước 1: Giả sử công thức đúng với n-1, tức là H(n-1) = 2^(n-1) - 1

    Bước 2: Chứng minh công thức đúng với n, tức là H(n) = 2^n - 1

    Ta có:

    H(n) = 2 * H(n-1) + 1 (theo công thức đề bài)

    = 2 * (2^(n-1) - 1) + 1 (theo giả sử ở bước 1)

    = 2^n - 2 + 1

    = 2^n - 1

    Vậy ta đã chứng minh được công thức đúng với mọi n.

    Để tính H(64), ta áp dụng công thức đã chứng minh:

    H(64) = 2^64 - 1

    = 18446744073709551615

    Vậy H(64) = 18446744073709551615 trùng với con số ở trên bài báo

    Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:

    Khởi động trang 19 Chuyên đề Tin học 11: Năm 1883, tại một số tỉnh thành của Việt Nam và tại Pháp xuất hiện một trò chơi

    Hoạt động 1 trang 19 Chuyên đề Tin học 11: Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ

    Câu hỏi 1 trang 21 Chuyên đề Tin học 11: Mô tả lời giải bài toán với trường hợp n = 1, 2, 3 ở trên (không dùng hình vẽ mô tả)

    Câu hỏi 2 trang 21 Chuyên đề Tin học 11: Mô tả lời giải bài toán với n = 1, 2, 3 nếu yêu cầu là di chuyển các đĩa từ cọc 1 sang cọc 2 (cọc 3 là cọc trung gian).

    Hoạt động 2 trang 21 Chuyên đề Tin học 11: Đọc, trao đổi để hiểu được ý tưởng thiết kế đệ quy cho lời giải bài toán Tháp Hà Nội

    Câu hỏi trang 22 Chuyên đề Tin học 11: Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4)

    Hoạt động 3 trang 23 Chuyên đề Tin học 11: Gọi Hanoi(n, i, j, k) là bài toán yêu cầu chuyển n đĩa đang xếp ở cọc i sang cọc j

    Câu hỏi 1 trang 24 Chuyên đề Tin học 11: Tính các giá trị H(2), H(3), H(4), H(5) của bài toán Tháp Hà Nội

    Câu hỏi 2 trang 24 Chuyên đề Tin học 11: Viết chương trình đệ quy để tính giá trị H(n) của bài toán Tháp Hà Nội

    Luyện tập 1 trang 24 Chuyên đề Tin học 11: Viết chương trình giải bài toán Tháp Hà Nội nhưng với tên các cọc là A, B, C

    Luyện tập 2 trang 24 Chuyên đề Tin học 11: Viết chương trình rút gọn của hàm Hanoi(n, i, j, k) như sau và kiểm tra kết quả

    Vận dụng 1 trang 24 Chuyên đề Tin học 11: Hãy chứng minh công thức

    Vận dụng 2 trang 24 Chuyên đề Tin học 11: Giả sử cần lưu dãy các bước chuyển của bài toán Tháp Hà Nội vào một danh sách

    Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:

    Bài 3: Thiết kế thuật toán đệ quy

    Bài 5: Thực hành thiết kế thuật toán theo kĩ thuật đệ quy

    Bài 6: Ý tưởng và kĩ thuật chia để trị

    Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị

    Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

    Tham khảo các loạt bài Tin học 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 210 20/08/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: