Đếm số miền

**batigoal** · 14-11-2014, 06:35 AM

Đếm số miền trong đa giác $n$ cạnh được chia bởi các đường chéo của đa giác mà không có ba đường chéo nào đồng quy.

thiendienduong · 14-11-2014, 07:46 PM

Trích:

Nguyên văn bởi batigoal

Đếm số miền trong đa giác $n$ cạnh được chia bởi các đường chéo của đa giác mà không có ba đường chéo nào đồng quy.

Nếu là đa giác lồi thì bài này theo mình truy hồi được.
Giả sử tính được với n-giác n.
Đỉnh mới thêm vào sẽ tạo ra (n+1)-giác với n - 1 đường chéo gồm n - 2 đường chéo mới và 1 đường chéo từ cạnh cũ.
Ta quan tâm tới n - 2 đường chéo mới.
Với mỗi đường chéo ta tính xem nó cắt bao nhiêu đường chéo khác.
Để ý là nếu nó cắt k đường chéo thì nõ góp k + 1 miền vào đáp số ở trường hợp n-giác.
Từ đó ta có công thức truy hồi dựa trên tổng số miền mà n - 2 đường chéo trên đã góp vào.

14-11-2014, 06:35 AM	#1
batigoal Super Moderator Tham gia ngày: Jul 2010 Đến từ: Hà Nội Bài gởi: 2,895 Thanks: 382 Thanked 2,968 Times in 1,295 Posts	Đếm số miền Đếm số miền trong đa giác $n$ cạnh được chia bởi các đường chéo của đa giác mà không có ba đường chéo nào đồng quy. __________________ “ Sức mạnh của tri thức là sự chia sẻ tri thức” Ghét lắm cơ, anh chàng ngồi cạnh Thích người ta mà cứ vờ lặng thinh Cây thước rơi hữu ý hay vô tình Tay chạm tay, mắt chạm vào nỗi nhớ Cứ lặng im, không gian ngừng thở Xốn xao lòng, bối rối con tim Ngây thơ lắm - Mối tình mực tím Phút yêu đầu, quá đỗi ngu ngơ! [Only registered and activated users can see links. ]