galaxylee 寫到:
一般解決圖形上的分割問題,我們會嘗試找出遞迴關係,再求解
假設圓內接2n邊形的拼圖數為F(n)
n=0,F(0)=1(這應該沒有意義,但為了配合公式,這是不得已的規定)
n=1,F(1)=1(理由同上)
n=2,F(2)=2
因為圓上兩點A、B能夠相連成一條弦,且滿足條件
其充要條件為此弦必須將其它點分割成左右兩側都是偶數個頂點
設AB線段左側頂點數為2s,AB線段右側頂點數為2n-2s-2=2(n-s-1)
所以原2n邊形分成一個2s邊形及一個2(n-s-1)邊形
而2s邊形的拼圖數為F(s),2(n-s-1)邊形的拼圖數為F(n-s-1)
所以屬於此種類型的拼圖數為F(s)*F(n-s-1)
所以F(n)=F(0)*F(n-1)+F(1)*F(n-2)+....+F(n-1)F(0)上式遞迴式的解為F(n)=[1/(n+1)]*C(2n,n)
(證明在此略)
所以,20邊形,n=10,F(10)=(1/11)*C(20,10)=16796
其實我有找到紅色之遞迴式
但因沒找到棕色的一般解而造成加錯的情況
可請galxylee兄撥空post一下遞迴式得解之過程嗎?
感激不盡