Hai mô tả sau đây chỉ ra phương pháp hiệu quả giải quyết bài toán bổ và đếm số hạt dưa

Giải Chuyên đề Tin học 11 Cánh diều Bài 1: Ý tưởng chia để trị

Hoạt động 1 trang 24 Chuyên đề Tin học 11: Hai mô tả sau đây chỉ ra phương pháp hiệu quả giải quyết bài toán bổ và đếm số hạt dưa bằng ý tưởng kĩ thuật chia để trị. Em hãy tìm hiểu bài toán sau đây và rút ra ý tưởng chủ đạo của kĩ thuật chia để trị để giải quyết bài toán.

Lời giải:

Cách giải quyết bài toán trên thể hiện ý tưởng chia đề trị, bao gồm 3 bước:

1. Chia: Chia bài toán bạn đầu (phức tạp) thành hai hoặc nhiều bài toán con (đơn gián hơn). Tiếp tục chia mỗi bài toán con thành các bài toán con đơn gian hơn nữa và cứ như thể cho đến khi đạt được các bài toán con đủ đơn giản mà chúng được giải quyết một cách dễ dàng

2 Trị: Giải quyết các bài toán cơn (một cách đệ quy). kết quả là các lời giải cua các bài toán con.

3. Kết hợp: Kết hợp eắc lời giải của các bài toán con để có được lời giải của bài toán ban đầu.