Con kiến
Xem dạng PDF
Gửi bài giải
Điểm:
5,00
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++
Cho một mảng kích thước n x m. Bắt đầu tại vị trí (1, 1) con kiến chỉ có thể đi xuống hoặc đi ngang sang phải. Hỏi để đến vị trí n x m có bao nhiêu cách đi?
INPUT : Hai số nguyên dương n,m.
OUTPUT: In ra số cách đi.
|
1 |
1 |
1 |
1 |
|
1
|
2 |
3 |
4
|
|
1 |
3 |
6 |
10 |
Công thức đệ quy như sau:
Tại vị trí i, j sẽ bằng số cách đi tổng i, j-1 và i-1, j
Tại i hoặc j = 0 thì số cách đi là 1.
Đến khi nào i=j=1 thì dừng lại.(Mỏ neo)
Để tối ưu:
Ta dùng mảng 2 chiều đi lưu lại đường đi của nó.
Bình luận