Trong phòng họp có người, mỗi người bắt tay lần lượt n - 1 người còn lại, giữa hai người bất kì chỉ
188
05/09/2023
Vận dụng trang 9 Chuyên đề Tin học 11: Trong phòng họp có người, mỗi người bắt tay lần lượt n - 1 người còn lại, giữa hai người bất kì chỉ bắt tay nhau đúng một lần. Em hãy:
a) Xác định số lượng cái bắt tay diễn ra trong phòng khi n = 0, 1, 2, 3, 4.
b) Đưa ra định nghĩa đệ quy cho hàm h(n) tính số lượng cái bắt tay đã diễn ra trong phòng có n người.
Gợi ý: Để xây dựng phân đệ quy cho h(n), em hãy xác định lời giải của bài toán khi có 0 người trong phòng từ lời giải của bài toán khi có n - 1 người trong phòng.
Trả lời
Để xây dựng phân đệ quy cho h(n), em hãy xác định lời giải của bài toán khi có 0 người trong phòng từ lời giải của bài toán khi có n - 1 người trong phòng.
a) Trước hết ta nhận thấy rằng nếu có 2 người A và B bắt tay nhau tức là A đã bắt tay B và ngược lại B cũng bắt tay A.
Vì có 10 người nên mỗi người sẽ bắt tay với 10 – 1 = 9 người còn lại.
Tổng số lượt bắt tay của tất cả 10 người là: 10 x 9 = 90.
Do A bắt tay B thì B cũng bắt tay A nên số lần bắt tay ở trên đã được tính 2 lần.
=> Có 90 : 2 = 45 cái bắt tay.
b) Đệ quy là một phương pháp giải quyết vấn đề, trong đó nó sử dụng các trường hợp ví dụ đơn giản hơn của vấn đề để truy hồi, từ đó có thể giải quyết các vấn đề phức tạp hơn.
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Cánh diều hay, chi tiết khác:
Bài 1: Khái niệm đệ quy và ví dụ
Bài 2: Thuật toán đệ quy
Bài 3: Thực hành thiết kế thuật toán đệ quy
Bài 4: Thực hành tổng hợp thiết kế thuật toán đệ quy
Bài 1: Ý tưởng chia để trị
Bài 2: Kĩ thuật đệ quy trong chia để trị
