ND
9
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Các câu hỏi dưới đây có thể giống với câu hỏi trên
PL
1
PH
4
C0
8
B
25 tháng 7 2016
Ta đặt tên các đỉnh như hình vẽ sau:
ABCDEFGHIJKMNOPQRSTU
Ta có nhận xét sau:
1) Số đường đi hợp lệ từ A đến các đỉnh nằm trên cạnh phía trên của lưới ô vuông C, D, E, F luôn là 1 (ví dụ từ A đến D chỉ có đường duy nhất là A-->C-->D)
2) Số đường đi hợp lệ từ A đến các đỉnh nằm trên cạnh bên trái của lưới ô vuông G, M, R cũng là 1 (Ví dụ từ A đến R chỉ có đúng 1 đường duy nhất là A-->G-->M-->R)
Ta ghi số cách đi hợp lệ từ A đến một đỉnh bằng số màu đỏ như hình vẽ dưới.
ABCDEFGHIJKMNOPQRSTU11111111
3) Ta tính số đường đi từ A đến các đỉnh còn lại theo qui tắc đệ qui (hoặc qui nạp) như sau:
- Đỉnh H: có 3 cách đi: A-->C-->H ; A-->H ; A -->G-->H
- Đỉnh I: Các đường đi từ A đến I được phân thành 3 loại:
+ đi qua đoạn DI: từ là từ A đến D rồi đến DI
+ đi qua đoạn CI: từ A đến C rồi đoạn CI
+ đi qua đoạn HI: từ A đến H rồi đoạn HI
Như vậy
[số đường đi từ A đến I] = [số đường đi từ A đến D] + [số đường đi từ A đến C] + [số đường đi từ A đến H]
= 1 + 1 + 3
= 5
(xem hình vẽ minh hoạ bên dưới)
ABCDEFGHIJKMNOPQRSTU1111111135
- Đỉnh J: Tương tự như cách tính đỉnh I:
[số đường đi từ A đến J] = [số đường đi từ A đến E] + [số đường đi từ A đến D] + [số đường đi từ A đến I]
= 1 + 1 + 5
= 7
(xem hình vẽ minh hoạ bên dưới)
ABCDEFGHIJKMNOPQRSTU11111111357
Cứ lặp lại tính như vậy cho các đỉnh còn lại. Ta sẽ điền được số đường đi hợp lệ từ A đến các đỉnh khác nhau như hình dưới đây:
AB111111113579513254172563129
Số đường đi hợp lệ từ A đến B là 129 đường.
ui ja lạy thánh bố mày cũng ko đếm đc
Chắc là 40, đếm không kĩ đâu